[선형구조] 리스트(List), 배열(Array), 연결 리스트(Linked List)

 

리스트는 선형적인(순서가 존재한다) 값을 가지고 있는 자료구조이다.

 

흔히 배열, 연결 리스트로 나눌 수 있는데,

 

배열(Array)

 

배열은 프로그래밍 언어에서 기본적으로 많이 쓰이는 자료구조이니, 설명은 생략하겠다.

 

Array

 

연결 리스트(Linked List)

 

Linked List

 

연결 리스트란 위의 그림처럼

 

각각의 Node가 존재하고,

 

Node는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.

 

그리고 첫 번째 Node를 HEAD라고 부르고,

 

마지막의 포인터가 가리키는 Node가 없다면 NULL 포인터가 되는 구조로 이루어져 있다.

 

연결 리스트의 삽입은 새로운 Node가 들어가고 포인터를 가리키는 식으로 이루어지고,

연결 리스트의 삭제는 기존의 Node가 빠지고, 포인터가 기존과 다른 Node를 가리키는 식으로 이루어진다.

 

그리고 순회(Iteration)는 단순히 매 노드를 반복문으로 순회해가며, 각 노드마다 특정한 연산을

해주는 방식으로 이루어진다.

 

 

배열과 연결 리스트의 차이점

 

연결 리스트의 장점: O(1) 시간으로 삽입, 삭제 가능

 

연결 리스트는 HEAD 포인터만 갖고 삽입 및 삭제를 할 때는 크기가 N일 때, O(N) 시간이 걸리지만

제일 앞의 노드를 추가하거나 삭제하는 경우에는 O(1) 시간으로 가능하다.

또한 Tail 포인터가 있다면, 제일 끝의 노드를 추가하거나 삭제하는 경우에도 O(1) 시간으로 가능하다.

 

즉, 특정 용도의 포인터가 있다면 그 근처에 노드를 추가하거나 삭제하는 경우 O(1) 시간으로 가능하다는 것이다.

 

그러나 일반적인 배열의 경우에는

새로운 값을 추가하거나 삭제할 경우, 모든 칸의 값을 한 칸씩 밀어줘야 하기 때문에, O(N) 시간이 걸린다.

(K번째 자리에 새로운 값을 추가할 경우, 그 뒤에 N-K의 값을 다 밀어줘야 하기 때문에 O(N-K) 시간)

 

배열의 장점: 랜덤 액세스

 

배열의 장점으로는 랜덤 액세스가 가능하다는 것이다.

 

랜덤 액세스는 특정 인덱스의 값을 O(1)만에 참조하는 것으로,

배열은 메모리상에서 값들이 일렬로 늘어져 있기에 가능하지만,

연결 리스트는 N번의 포인터를 다 탐색해야 하므로, O(N) 시간이 걸린다.