2.4.2 연결 리스트

연결 리스트(linked-list)는 포인터를 통해 여러 노드(node)가 연결돼 있는 자료구조입니다. 각 노드는 데이터를 저장하는 공간과 다음 노드를 가리키는 포인터 공간으로 구성됩니다. 이러한 구조 덕분에 연결 리스트는 삽입이나 삭제에 걸리는 시간이 O(1)로 빠른 편입니다. 노드를 삽입하려면 새 노드를 만들어 노드 사이에 포인터로 연결하고, 노드를 삭제하려면 바로 앞의 포인터만 바꾸면 되기 때문입니다.

그림 2-32 연결 리스트

다음 그림에서 세 번째 노드를 삭제하는 경우, 만약 배열이라면 그 뒤의 노드를 전부 한 칸씩 이동해야 하지만 연결 리스트에서는 바로 앞에 있는 노드의 포인터가 네 번째 노드를 가리키도록 수정하면 됩니다.