[Section 3] 연결 리스트의 종류와 개념 이해하기

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

선형 자료구조는 자료를 순차적으로 구성하였기 때문에 그 정보에 접근하기 위한 알고리즘은 역시 순차적이다. 이러한 선형 자료구조의 종류에는  리스트, 스택 그리고 큐 존재한다. 만약 연결 리스트의 알고리즘 개념에 기반하여 자료 구조를 이해했다면, 지금 부터는 그 종류와 개념만으로 스스로 구현해 볼 수 있을 것이다. 이번 시간에는 리스트의 종류와 그 개념을 이해해 보도록 한다.

1. 연결 리스트의 종류와 개념 _ 단 방향, 양 방향, 원형 연결 리스트

먼저, 단 방향 연결 리스트와 양 방향 연결 리스트(Doubly Linked List)의 자료구조를 다음과 같이 비교해보자.

 

단 방향과 양 방향 연결리스트의 차이 _ 좌측은 단 방향, 우측은 양방향 연결리스트

 

위의 그림에서 보이는 바와 같이, 헤드라는 포인터에 어떤 노드가 연결되느냐에 따라 단 방향이냐, 양 방향이냐가 결정된다.  결정적 차이는 양 방향 연결 리스트의 노드에는 포인터를 지정할 수 있는 공간이 두 개나 있기 때문에, 지정된 노드의 앞 노드와 뒷 노드를 선택할 수 있다는 장점을 가지고 있다. 다음의 그림을 참고하자.

 

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

 

데이터 수가 많아질수록 메모리 공간 측면에서는 효율이 조금 떨어질지는 몰라도 데이터 탐색 등의 측면에서 더 효율적이라는 장점을 가지고 있다. 그렇다면, 원형 연결 리스트(Circular Linked List)는 어떤 구조일까?  다음 그림을 참고하자.

 

원형 연결 리스트(Circular Linked List)의 구조 _ 우측 그림은 연결된 상태일 때의 구조를 보여준다.

 

재미있게도, 원형 연결리스트는 꼬리 노드가 존재하지 않는다. 꼬리 노드의 포인터는 가장 앞 노드와 연결되기 때문에 낭비되는 데이터가 존재하지 않는다는 특징을 가지고 있다. 물론 기호에 따라서 양 방향 원형 연결 리스트를 만들 수도 있겠다.

 

* 언급된 연결 리스트외에도 배열 리스트, 언롤 연결 리스트(Unrolled Linked List) 등 많은 종류의 연결 리스트가 존재하므로 참고하도록 하자.

2.  연결리스트의 ADT와 장단점 정리

연결 리스트의 주 ADT는 삽입과 삭제를 바탕으로 구현된다. 그리고 보조 ADT는 초기화 기능, 길이 카운트, 그리고 n번째 노드를 선택하는 기능이 일반적인 특징이라고 할 수 있겠다.

 

연결 리스트 자료구조를 만드는 가장 근본적인 이유는 배열 리스트의 단점을 보완하기 위해서이다. 배열 리스트의 경우 저장된 데이터에 인덱스가 붙기 때문에 자료에 접근하는데 더 빠르다는 장점을 가지고 있지만, 전체적인 사이즈가 고정되어있다는 단점을 가지고 있다. 물론 배열 리스트도 자료를 추가할 수 있지만, 특정 인덱스의 정보에 새로운 데이터를 삽입해야 하는 경우 고정된 사이즈를 늘리고 삽입될 자리에 저장된 자료를 한 자리씩 모두 옮겨주어야 한다. 즉, 삽입 측면에서 연결 리스트의 자료구조가 더 효율적이다.

 

하지만, 연결 리스트라고 무조건 장점만 있는 것은 아니다. 가장 치명적인 단점은 데이터가 많아질 수록 데이터에 접근하는 시간이 더 증가한다. 시간 복잡도로 기술하자면, 배열 리스트의 경우 접근 시간의 복잡도는 O(1)인 반면에, 연결 리스트의 시간 복잡도는 O(n)이다. 추가로 공간 복잡도 측면에서도 배열 리스트가 더 효율적이다.  

 

* 연결 리스트와 배열의 시간 복잡도를 비교하면 다음의 표와 같다.

비교 목록	배열 리스트	연결 리스트
데이터 접근	O(1)	O(n)
데이터 첫&끝 삽입 혹은 삭제	데이터의 존재 유/무에 따라 다르다	O(1)
데이터 중간 삽입 혹은 삭제	O(n)	O(n)
메모리 공간의 낭비	없다	O(n)