메모리상에 선형으로 나열된 배열과 달리 연결 리스트는 요소들이 참조로 이어져 있습니다. 각 요소는 노드라는 틀에 담겨 있는데, 노드는 데이터를 담는 부분과 다음 노드를 가리키는 참조로 구성되어 있습니다.

그림으로 살펴봅시다.

▲ 그림 4-1 노드

그림 4-1은 노드를 나타낸 것입니다. data는 실제 저장하려는 데이터고, link는 다음 노드를 가리킵니다. 이렇게 참조로 데이터와 데이터를 연결(link)해 두었기 때문에 연결 리스트라고 하지요. 연결 리스트는 참조가 하나 있느냐 둘이 있느냐에 따라 단순 연결 리스트(single linked list)와 이중 연결 리스트(double linked list)로 나눕니다. 단순 연결 리스트는 다음 노드를 가리키는 참조 하나만 가지고 있는 반면, 이중 연결 리스트는 앞 노드를 가리키는 참조와 뒤 노드를 가리키는 참조를 모두 가지고 있습니다.

단순 연결 리스트를 다룬 예제로 연결 리스트가 가지는 삽입·삭제·탐색 연산의 특징을 알아보겠습니다.