[자료구조] Linked List(연결리스트)의 특징

[자료구조]

 

 

살펴볼 주요 개념:

- Linked List의 정의

- 한 방향 연결리스트 vs 양 방향 연결리스트

 

1. Linked List(연결리스트)의 정의

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

 

 

여기서 하나의 박스가 노드라고 보면된다. 박스의 옆부분이 링크 부분이며 각 노드 안에는 key값 또는 key값 value값 쌍이 들어간다. 다음 노드를 계속 가리키면서 하나의 줄줄이 소세지 같은 모습을 한다.

 

연결 리스트의 종류로는 한 방향 연결 리스트, 양 방향 연결 리스트 등이 있다.

 

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다.

아래에 코드를 쓸 것인데, 다음 노드를 가리키는 next 값(포인터)만을 바꾸면 되기 때문이다.

 

다만 몇 번째 노드인지 모르고 key값만 알고 있을 경우, 그 위치를 탐색해야 하는데, 그 데이터를 검색해내는데 O(n)시간이 걸린다.

배열은 인덱스를 가지고 데이터에 접근하지만, 연결 리스트의 경우 순차적으로 head부터 탐색을 해야하기 때문이다. 이러한 점이 단점으로 거론되기도 한다.

 

 

2. 한 방향 연결리스트 vs 양 방향 연결리스트

(1) 움직일 수 있는 방향의 차이

 

한 방향 연결리스트(Singly Linked List)와 양 방향 연결리스트(Double Linked List)의 가장 큰 차이는 움직일 수 있는 방향이다.

 

한 방향 연결리스트는 다음 노드로 밖에 이동하지 못한다.

양 방향 연결리스트는 다음 노드로도 갈 수 있고 이전 노드로도 움직일 수 있다.

 

이 차이는 tail 노드(맨 마지막 노드)를 지우고 싶을 때 시간복잡도의 차이로 작용한다.

만약 한 방향 연결리스트의 맨 마지막 노드를 모른다면, head pointer부터 순차적으로 탐색하여 next 노드가 없는 부분까지 탐색을 이어나가야 한다. 즉,  O(N) 시간이 걸리게 된다.

그러나 양 방향 연결리스트의 경우, 마지막 노드를 모른다 하더라도, 헤드 포인터가 가리키고 있는 이전 노드가 맨 마지막 노드이다. 따라서 O(1) 시간 복잡도로 맨 마지막 노드 삭제 연산을 진행할 수 있다.

 

방향의 차이로 인해 각종 삽입, 삭제, 탐색 연산의 시간 차이가 발생할 수 있다.

 

 

(2) 링크의 개수

 

한 방향 연결리스트는 방향을 가리키는 링크가 다음 노드로만 이어져있고,

양 방향 연결리스트는 당연히 방향을 가리키는 링크가 다음 노드로도 이어져있고, 이전 노드로도 이어져있다. 

 

양 방향 연결리스트는 링크 변수를 조금 더 신경써줘야 한다.

따라서 구현의 난이도에서 차이가 난다.

 

 

 

++ 배열과의 차이

 

배열은 insert 연산에 O(n)시간이 걸린다.

만약 A = [3, 9, 1, 2] 라는 배열이 있으면, 세 번째에 5를 넣고 싶다면, 새로운 배열을 만들고, 3, 9, 5, 1, 2를 만들어야 하기 때문이다.

 

그러나 Linked List의 경우, a노드와 b노드 사이에 x 노드를 넣고 싶다면, a가 가리키는 다음 노드와 x가 가리키는 다음 노드만 변경해주면 되기 때문에 2번의 연산 즉 O(1) 시간 복잡도로 삽입 연산을 해결할 수 있다.