연결 리스트 (Linked List) 정의

 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 연결 리스트의 종류로는 단순 연결 리스트, 이중 연결 리스트 등이 있다.

 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.
(참고 : http://ko.wikipedia.org/wiki/%EB%A7%81%ED%81%AC%EB%93%9C_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 

 프로그래밍을 하는데에 있어서 대다수의 프로그래머가 자료구조라 하면 제일 먼저 생각하는 것을 꼽으면, 스택, 큐, 리스트 등을 들 수 있다. 그 중에서 리스트는 이론적으로, 논리적으로 생각했을 때에 이해하기가 쉽고, 이해하기 쉬운만큼 구현상에 어려움이 적다.

 메모리를 위의 그림과 같은 "노드" 라는 단위로 나누어 사용하게 되는데, 노드는 데이터를 가지고 있는 메모리와 다음 노드를 가리키는 포인터로 구성되게 된다. 정적으로 메모리를 할당하여 사용하는 방식과 다르게, 저장할 데이터가 동적으로 생성되어야 하는 경우에 리스트를 이용하면 손 쉽게 구현할 수 있다.

 저장되어야 하는 데이터가 있을 때 마다, 노드를 하나씩 메모리에 할당하여, 데이터를 저장하고, 생성된 노드들을 하나의 묶음으로 보관하게 된다.

 위의 위키백과에서 설명한 자료의 추가와 삭제가 O(1) 의 시간에 가능하다는 점은, 예를 들어, 위의 그림에서 링크드 리스트의 가장 앞에 데이터를 추가하려고 한다면, 추가적인 연산없이 바로 메모리를 할당하여 추가하면 된다는 것이다.

 특정 위치의 데이터를 검색해 내는데에 O(n) 의 시간이 걸리는 단점은, 예를 들어, 위의 그림에서 데이터 "3" 을 찾고 싶다면, 데이터 "1", "2" 를 가진 노드를 거쳐서 3번의 탐색을 해야 데이터 "3" 을 찾을 수 있으며, 이와 같이 최악의 경우의 링크드 리스트의 가장 마지막 노드까지 탐색을 하게 되어, 노드의 갯수인 n 번의 탐색이 필요하다는 것이다.

 

 링크드 리스트는 자료구조의 가장 기본이라고 볼 수 있는 만큼, 확실히 이해하고, 자유자재로 구현을 할 수 있도록 하여야 한다. 이후에 이야기하게 될 대다수의 자료구조는 링크드 리스트를 이용하여 구현을 하게 된다.

 연결 리스트 (Linked-List) 에서는 "리스트의 기본 연산들" 다룬 후, "단순 연결 리스트(Single Linked-List)", "이중 연결 리스트(Double Linked-List)", "원형 연결 리스트(Circular Linked-List)" 에 대하여 다루어 보도록 하겠다.