연결 리스트(Linked List)

자료구조 특징

각 노드가 데이터와 포인터를 가지고 연결되어 있는 자료구조이다.

 

시간복잡도

접근(검색)	탐색	삽입	삭제
\(O(N)\)	\(O(N)\)	\(O(1)\)	\(O(1)\)

• 배열과는 달리 임의접근(Random Access)이 불가하기 때문에 특정 노드에 접근하기 위해선 \(O(N)\)의 시간복잡도를 가진다.
• 삽입, 삭제 로직 자체는 포인터 필드의 참조만 수정하면 되기에 \(O(1)\)의 시간복잡도를 갖지만, 삽입할 위치 혹은 삭제할 노드까지 찾아가는 데만 \(O(N)\)의 시간복잡도를 갖기 때문에 특정 요소를 찾아서 삽입/삭제를 수행하는 경우 실질적은 시간복잡도는 \(O(N)\)이 된다.

 

종류

싱글 연결 리스트

• 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성되어 있다.
• 마지막 노드의 포인터 필드가 가리키는 노드는 존재하지 않으므로 \(null\)을 참조한다.

이중 연결 리스트 

이중 연결 리스트

• 데이터 필드와 다음 노드를 가리키는 포인터 필드, 이전 노드를 가리키는 포인터 필드로 구성되어 있다.
• 첫 노드의 이전 노드, 마지막 노드의 다음 노드는 존재하지 않으므로 각 포인터는 null을 참조한다.
• head노드에 가까운 노드는 head부터, tail노드에 가까운 노드는 tail부터 탐색을 시작한다. 실질적인 시간 복잡도는 \(\frac{1}{2}O(N)\)

원형 이중 연결 리스트

원형 이중 연결 리스트

• 데이터 필드와 다음 노드를 가리키는 포인터 필드, 이전 노드를 가리키는 포인터 필드로 구성되어 있다.
• 이중 연결 리스트와 거의 동일하나 마지막 노드가 null이 아닌 첫 노드를 가리킨다는 점에서 순환 구조를 갖는다는 차이점이 있다.
• 이중 연결 리스트와 마찬가지로 head노드에 가까운 노드는 head부터, tail노드에 가까운 노드는 tail부터 탐색을 시작한다. 실질적인 시간 복잡도는 \(\frac{1}{2}O(N)\)

 

참고

자바로 연결 리스트를 구현하면서 포인터 필드의 참조를 끊을 때 생긴 의문점에 대한 정리 글이다.

 -  https://brotherstone.tistory.com/179

Java Garbage Collector의 수집 대상이 되기 위해 참조만 끊으면 되는 걸까?