Array와 Linked List

Array ( 배열 )

메모리에 할당할 크기를 미리 정하고 사용하는 자료구조이다.

int arr[10];
// arr에 10개 미만의 데이터가 있을 시, 메모리 낭비 발생
// arr에 10개 초과의 데이터가 삽입될 때, 메모리 초과(부족) 발생

 

 

장점

배열을 사용하면 index가 존재하기 때문에 원하는 값을 빠르게 조회 가능하다

단점

값을 삽입하거나 삭제할 때 비효율적이다. 3번째 index위치에 값을 추가하려고 한다면, 기존에 있던 [3]부터 마지막 요소까지 한 칸씩 뒤로 이동해야 하는 연산이 수행되기 때문이다.

---

List ( 리스트 )

Array의 단점을 보완하고자 List가 등장했다.

List는 메모리에 할당할 크기를 미리 정하지 않아도 된다. 크기가 정해져있지 않기 때문에 메모리 초과 문제를 해결할 수 있다.

하지만, 값 삽입 시 발생하는 추가 연산과 메모리 낭비 문제는 여전히 남아있다.

---

Linked List ( 연결 리스트 )

Linked List는 배열과 다르게 메모리에 index를 기반으로 물리적인 배치를 하지 않고, 노드(Node)를 생성하고 각 노드마다 다음 노드를 가리키는 포인터가 존재한다.

이러한 방식을 사용하면서 데이터를 중간에 삽입할 경우에도 각 노드가 가리키는 다음 노드의 주소만 변경하면 되기 때문에 복잡도는 O(1)이다.

연결 리스트에도 단점이 있는데, index를 기반으로 값에 접근하는 것이 어렵다는 것이다.

---

연결 리스트를 사용하여 리스트의 중간 값을 구하고자 한다면 다음과 같은 방식을 사용할 수 있다.

1. 두 개의 포인터를 사용한다.
2. 하나는 한 칸씩 이동하고, 다른 하나는 두 칸씩 이동한다.
3. 두 칸씩 이동하는 포인터가 배열의 끝에 도착했을 때, 한 칸씩 이동한 포인터가 가리키는 위치가 연결 리스트의 중간 값이다.