1.2.2 연결된 자료 구조

연결된 자료 구조(linked data structures)는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장됩니다. 다음은 연결된 자료 구조에 데이터가 저장되는 방법을 나타내는 다이어그램입니다.

▲ 그림 1-2 연결된 자료 구조

그림 1-2와 같은 형태로 구성된 자료 구조를 연결 리스트(linked list)라고 합니다. 연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지고 있습니다. 맨 마지막 노드에서는 다음 노드의 포인터 대신 자료 구조의 끝을 나타내는 NULL을 가집니다. 연결 리스트에서 특정 원소에 접근하려면 리스트의 시작 부분, 즉 헤드(head) 부분부터 시작하여 원하는 원소에 도달할 때까지 next 포인터를 따라 이동해야 합니다. 그러므로 i번째 원소에 접근하려면 연결 리스트 내부를 i번 이동하는 작업이 필요합니다. 그러므로 원소 접근 시간은 노드 개수에 비례하며, 시간 복잡도로 표현하면 O(n)입니다.

배열과 달리 연결 리스트는 포인터를 이용하여 원소의 삽입 또는 삭제를 매우 빠르게 수행할 수 있습니다. 연결 리스트에 새로운 원소를 추가하는 방법을 살펴보겠습니다. 그림 1-3은 연결 리스트 중간에 새로운 원소를 삽입하는 동작을 나타내는 다이어그램입니다.

▲ 그림 1-3 연결 리스트에 새 원소 추가하기