연결 리스트 (Linked List)

출처 : 파이썬 알고리즘 인터뷰

연결 리스트는 자료를 저장하는 자료구조 중 하나로, 물리적인 순서와 논리적인 순서가 일치하지 않을 때 사용됩니다. 선형 자료 구조로서, 요소들이 일렬로 연결되어 있는 형태로 구성됩니다. 또한, 노드(node)들로 구성되며 각 노드는 자신이 저장하고 있는 값(data)과 다음 노드를 가리키는 포인터(pointer)로 이뤄져 있습니다.

 

첫 번째 노드를 가리키는 포인터를 헤드(head)라고 하며, 마지막 노드를 가리키는 포인터는 NULL값으로 설정됩니다. 연결 리스트의 가장 큰 특징은 요소들이 물리적으로 연속적인 공간에 저장되지 않는다는 것입니다. 즉, 연결 리스트에서 각 요소들은 메모리상에서 임의의 위치에 저장될 수 있으며, 각 요소들은 자신의 다음 요소를 가리키는 포인터를 가지고 있습니다.

 

연결리스트는 다음과 같은 장단점이 있습니다:

 

장점

• 배열에서 요소를 삽입하거나 삭제하는 경우, 다른 요소들의 위치를 모두 조정해야 하지만, 연결 리스트에서는 단순히 포인터를 수정하면 되므로 더 빠른 시간 내에 작업을 완료할 수 있습니다.
• 메모리 공간을 동적으로 할당하므로, 배열보다 유연합니다.
• 배열과 달리 요소의 개수를 미리 정하지 않아도 됩니다.

단점

• 연결 리스트에서 특정 요소에 접근하려면 헤드부터 시작해서 원하는 요소를 찾을 때까지 포인터를 따라가야 하므로, 배열에 비해 접근 속도가 느립니다.
• 포인터를 사용하기 때문에 배열보다 메모리 사용량이 더 많습니다.
• 연결 리스트의 구현이 배열보다 복잡합니다.

연결 리스트는 일반적으로 다음과 같은 상황에서 유용하게 사용됩니다:

• 요소의 개수가 미리 예측되지 않는 경우
• 요소의 삽입과 삭제가 빈번하게 일어나는 경우
• 크기가 제한된 메모리를 사용해야 하는 경우

대표적인 연결 리스트 구현체로는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)등이 있습니다.