[Data Structure] 연결 리스트(Linked List)

연결 리스트(Linked List)란?

연결 리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

연결 리스트(Linked List)의 종류

단순 연결 리스트(Singly linked list)

단일 연결 리스트(Singly linked list)는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트(Doubly linked list)

단순 연결 리스트(Singly Linked List)는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없습니다. 이러한 단점을 해결하기 위해 노드에 앞 노드의 메모리 주소를 보관하는 포인터 prev를 만들어준 형태를 이중 연결 리스트(Doubly Linked List) 입니다.

원형 연결 리스트(Circular linked list)

원형 연결 리스트(Circle linked List)란 단순 연결 리스트(Singly Linked List)의 마지막 노드의 포인터가 NULL이 아닌 헤드를 가리키는 형태의 리스트 입니다. 따라서 리스트의 끝이 존재하지 않습니다.

 

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

접근(Access) 시간 복잡도: O(n)

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

탐색(Find) 시간 복잡도: O(n)

• 배열을 탐색할 때와 같은 방법으로 구한다.
• 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 데이터를 찾는다. 이를 선형 탐색이라고 한다.
• 링크드 리스트안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막 노드에 있는 경우 n개의 노드를 다 봐야한다.
• 최악의 경우 시간 복잡도 : O(n)

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

• 삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 된다.
• 따라서 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정하다.
• 시간 복잡도 : O(1)

현실적으로는 삽입, 삭제할 노드를 탐색하는 과정이 필요하기 때문에 최악의 경우 O(n)의 시간 복잡도가 필요하다. 하지만 연결 리스트의 맨 앞에 삽입하는 경우는 이미 Head를 알고 있기 때문에 O(1)의 시간 복잡도를 가진다. 또한 Tail을 알고 있다면, 맨 뒤에 삽입하는 경우 O(1)의 시간 복잡도를 가진다. (Tail을 모른다면 맨 마지막 노드까지 탐색해야 해서 O(n)의 시간 복잡도를 가진다.)

 

연결 리스트(Linked List) vs 배열(Array)

차이점 1. 시간 복잡도

비교를 위해 배열(Array)의 시간 복잡도를 살펴보자.

접근(Access) 시간 복잡도: O(1)

• 인덱스 x에 곧바로 접근할 수 있다.

탐색(Find) 시간 복잡도: O(n)

• 0번째 인덱스부터 마지막 인덱스까지 접근하면서 원하는 데이터를 찾는다.
• 배열 안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막에 있는 경우 n개의 데이터를 살펴봐야 한다.
• 최악의 경우 시간 복잡도 : O(n)

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

• 특정 인덱스에 데이터를 삽입, 삭제하기 위해 기존의 데이터를 옮기는 작업이 필요하다.
• 0번째 인덱스에 데이터를 삽입하기 위해서는 현재 배열의 0번째 인덱스부터 마지막 인덱스까지의 데이터들을 모두 한 인덱스 뒤로 옮겨야한다.
• 최악의 경우 시간 복잡도 : O(n)

하지만 배열의 마지막에 데이터를 삽입하거나 삭제하는 경우에는 O(1)의 시간 복잡도를 가진다.

 

차이점 2. 메모리 사용

시간 복잡도 외에도 메모리를 사용하는 것에 차이가 있다.

• 배열은 사용하기 전 배열의 크기를 미리 선언해야 하고, 크기의 수정이 불가능하기 때문에 메모리 사용이 비효율적이다. (정적 할당)
• 연결 리스트는 필요할 때마다 노드를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용할 수 있다. (동적 할당)

• 배열은 메모리 공간에 연속적으로 저장되어 있는 자료구조이다. 이러한 특징때문에 인덱스를 통한 접근이 용이하고, 데이터 외에 다른 정보를 저장할 필요가 없다.
• 연결 리스트는 데이터를 저장할 공간 뿐만 아니라, 다음 노드의 주소를 저장하는 공간이 추가적으로 필요하다.

 

📗 참고

• 위키백과, 연결 리스트
• 자료구조 : 연결리스트 (Linked list)
• 연결 리스트(Linked list) 개념정리
• [자료구조]싱글 링크드 리스트(단순 연결 리스트)의 시간 복잡도
• 배열과 연결리스트 (Array & LinkedList)