[Seoul National Univ: Data Science] Lecture 4. Arrays & Linked Lists

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://youtu.be/647aZztdsb0?si=YLRU39A9zVc_lvRp

 

 

1. Array

 

메모리 구조

• 데이터가 연속된 메모리에 저장됨
• A[0], A[1], ... A[n-1]

장점

• Random access: O(1) 내에서 임의의 위치에 접근할 수 있다.

단점

• 중간에 삽입 및 삭제하면 뒤 원소들을 전부 한 칸씩 밀거나 당겨야 해서 O(N)이 된다.
• 불필요한 메모리 공간이 사용된다.

 

2. Singly Linked List

 

메모리 구조

• 각 노드가 메모리 공간 내에 흩어져 있고 포인터 변수 "next"로 이어진다.
• 보통 head 포인터 하나로 시작 노드를 가리킨다.

장점

• 필요할 때마다 동적으로 메모리를 할당하여 노드를 연결하면 된다.
• 노드의 위치를 알고 있을 때 삽입 및 삭제 연산은 O(1)이 된다.
• 중간에 삽입 및 삭제를 할 때 모든 노드를 변화시키지 않아도 된다.

단점

• 포인터 변수를 저장하기 위해 추가적인 공간을 할당해야 한다.
• Random access: 임의의 위치에 접근하려면 이전 노드까지 순회를 해야한다.

 

 

3. Doubly Linked List 

 

메모리 구조

• 각 노드가 메모리 공간 내에 흩어져 있고 포인터 변수 "next"로 이어진다.
• 보통 header / trailer 더미 노드를 두고 구현한다.

장점

• 필요할 때마다 동적으로 메모리를 할당하여 노드를 연결하면 된다.
• 노드의 위치를 알고 있을 때 삽입 및 삭제 연산은 O(1)이 된다.
• 앞 뒤 양쪽으로 순회가 가능하다.
• 중간에 삽입 및 삭제를 할 때 모든 노드를 변화시키지 않아도 된다.

단점

• 노드마다 2개의 포인터 변수를 저장해야 하므로 Singly Linked List보다 메모리 오버헤드가 더 크다.
• Random access: 임의의 위치에 접근하려면 이전 노드까지 순회를 해야한다.

 

4. Applications of Linked Lists

 

1. 단일 연결 리스트의 중간 노드 찾기 (연결 리스트의 size가 제공되지 않는 경우)

• 한 칸씩 이동하는 slow와 두 칸씩 이동하는 fast를 구현
• 만약 fast가 끝 또는 직전에 도달하면 slow의 위치가 가운데가 된다.

 

2. 단일 연결 리스트 뒤집기

• 3개의 포인터 사용: prev, next, curr
• 초기 값: prev = NULL, curr = head로 시작
• 연결 방향 뒤집기: curr->next = prev
• 한 칸 이동: prev = curr, curr = next
• curr = NULL이 될 때까지 반복
• 마지막에 prev가 새로운 head

 

3. 연결 리스트에 사이클이 있는지 검사

• 한 칸씩 이동하는 slow와 두 칸씩 이동하는 fast 구현
• 만약 연결 리스트에 사이클이 없다면 fast는 언젠가 NULL에 도달한다. → cycle 존재 X
• 만약 사이클이 존재한다면 fast는 언젠가 slow와 만나게 된다. → cycle 존재