연결 리스트

연결 리스트는 무엇일까? 말 그대로 연결되어 있는 리스트를 의미한다. 각 점으로 연결되어 있어서 서로 연관성을 가지고 있는 리스트다. 다시 말해, 노드의 모음으로 구성된 자료구조를 의미한다.

노드 (node) 는 저장하고자 하는 데이터와 다음 노드의 위치를 포함한다. 특정 노드에 접근할 수 있으면 다음 노드의 위치를 알 수 있기 때문에, 꼬리에 꼬리를 무는 형태로 구성되어 있다.

따라서 연결 리스트의 첫 번째 노드는 헤드, 두 번째 노드는 꼬리 라고 부른다. 연결 리스트는 꼬리에 꼬리를 무는 형태로 보인다고 언급했다. 즉, 연결 리스트를 구성하는 모든 노드는 반드시 메모리에 순차적으로 저장되어 있을 필요는 없다. 그렇기에

연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용하게 사용이 가능하다.

접근

연결 리스트는 배열과는 다르다. 배열은 요소에 접근할 때 $O(1)$이 필요하고, 일정하였다. 그렇다면 연결 리스트는 몇 번째 노드에 데이터가 있는지 안다면 $O(1)$에 접근이 과연 가능할까?

정답은 그렇지 않다. 연결 리스트는 특정 요소에 접근할 때 계속 꼬리를 물면서 접근해야 한다. 즉, 몇 번째 노드에 데이터가 있다고 한 들, 앞에서부터 순차적으로 접근할 수 밖에 없기에 $O(n)$이 소요될 수 밖에 없다.

• 연결 리스트 내 요소에 접근: $O(n)$

추가 및 삭제

연결 리스트는 배열과는 다르게 요소를 추가 하거나 삭제 하는데 강점이 있다. 배열은 추가하거나 삭제할 때 다시 인덱스 정렬을 위해서 $O(n)$의 시간 복잡도가 필요하였다. 하지만 연결 리스트는 해당 노드의 위치만 변경하면 된다. 따라서 $O(1)$ 만 걸린다는 장점이 있다.

• 연결 리스트 내 요소를 추가 및 삭제: $O(1)$

싱글 연결 리스트

헤드부터 시작해서 꼬리끼리 연결되어 최종 노드까지 가는 연결 리스트는 싱글 연결 리스트라고 한다. 하지만 이는 여러가지 단점이 있는데, 다음과 같다.

특정 노드를 통해 다음 노드의 위치만 알 수 있고, 이전 노드위치를 알 수 없다.

즉, 이러한 연결 리스트는 단방향 탐색만 가능하다는 특징을 갖는다.

이중 연결 리스트

싱글 연결 리스트를 보완하기 위핸 연결 리스트의 변형이다. 노드가 조금 다른데, 이전 노드 위치를 포함하는 것이다.

그렇기 때문에 다음 노드의 위치와 이전 노드의 위치가 연결되어 있기 때문에 쉽게 이동이 가능하다. 하지만 모든 것에는 단점이 존재하는데,

이전 노드의 위치 정보 (메모리 주소)를 저장해야 하므로 저장 공간이 더욱 많이 필요하다.

환영 연결 리스트

마지막은 싱글 연결 리스트에서 약간의 변형이 된, 마지막 꼬리가 최초의 헤드를 무는 형태를 띄어 원형을 보이는 특징을 갖는다. 이중 연결 리스트로도 가능하다.

참고자료

※ 이 글은 『이것이 컴퓨터 과학이다』 책을 기반으로, 다양한 자료를 참고해 작성했습니다.