[알고리즘] 연결리스트

연결리스트, Linked List 는
각 노드들이 한 줄로 연결되어 있는 방식으로 각 노드는 데이터와 포인터 (다음 노드의 정보)를 가지고 있다.
연결리스트는 일반적인 배열과 다르게 삽입과 삭제가 O(1)에 가능하다는 장점이 있다.
하지만 특정 n번 째 정보를 찾는 데에는 O(n)시간이 걸린다는 단점도 있다.

💡연결리스트 종류

 

단방향 연결 리스트(Singly Linked List)

단방향 연결 리스트는 가장 단순한 형태의 연결 리스트이다.
하나의 노드 안에는 사진과 같이 '데이터' 와 '포인터' 로 구성되어있다.

이 자료구조는 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우, 체인이 끊어진 것처럼 뒤쪽의 자료들과 연결이 끊기게 된다.
그러므로 안정적인 자료구조라고는 할 수 없을 것이다.
이를 보완하는 방법은 바로 다음에 설명할 양방향 연결 리스트이다.

양방향 연결 리스트(Doubly Linked List)

양방향 연결 리스트는 순차적으로 자신이 원하는 데이터까지 하나하나 다 훑고 가야 하는 단방향 연결 리스트의 단점을 보완한 연결 리스트이다.

양방향 연결 리스트는 '다음 데이터의 주소 값' 그리고 '이전 데이터의 주소 값'을 가지고 있는 연결 리스트이다.

이처럼 양방향 연결 리스트는 뒤로 탐색하는 속도 또한 빠르며, 다음 참조 주소가 끊기게 되어도 이전 노드를 참조하는 주소 또한 있기 때문에, 중간에 노드를 삭제하고 남아있는 노드끼리 연결하거나, 요소를 중간에 추가하기가 쉽다.

하지만, 참조가 2개나 있기 때문에 삽입이나 정렬할 경우 해야 할 작업이 더 많으며 자료구조의 크기가 단방향보다 조금 더 커진다는 단점이 있다.

 

원형 연결 리스트(Circular Linked List)

원형 연결 리스트는 단순히 마지막 원소가 처음 원소(Head)를 가리키는 연결 리스트이다. 따라서 리스트의 끝이 존재하지 않는다.

마지막 노드의 포인터가 첫 번째 노드를 가르킨다.

원형리스트는 하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐 자기 자신으로 되돌아오는 것이 가능하다.

⏰ 연결 리스트(Linked List)의 시간 복잡도

1. 접근(Access) : O(n)

인덱스 x에 있는 노드에 접근하려면 Head에서 다음 노드로 x번 가면 된다.
마지막 노드에 접근하려면 Head에서 다음 노드로 n-1번 가야된다.
최악의 경우 시간 복잡도 : O(n)
탐색 시간 복잡도: O(n)

2. 삽입/삭제(Insertion/Deletion) 시간 복잡도 : O(1)

삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 된다.
따라서 삽입, 삭제가 실행되는 항상 O(1)로 일정하다.
시간 복잡도 : O(1)
최악의 경우 시간 복잡도 : O(n)
(삽입, 삭제할 경우를 탐색해야 할 수도 있어서)