리스트

게시 2023.11.29 업데이트 2024.05.18

By 고양이 사서 19 분읽는 시간

개요

헤더 파일
- <list>: 이중 연결 리스트(doubly linked list)
- <forward_list>: 단일 연결 리스트(singly linked list)
STL 시퀀스 컨테이너 (sequence container): 노드(Node)기반 연결형 선형 자료구조
탐색 시간: $O(N)$
요소 추가/삭제: $O(1)$

리스트(List)는 데이터 요소의 순차적인 모음을 의미합니다. 리스트는 데이터를 순서대로 저장하고 관리하는 데 사용되며, 다양한 형태와 구현 방식이 있습니다.

리스트는 크게 배열 기반 리스트(Array List) 혹은 순차 리스트(Sequential List)와 연결형 리스트(Linked List)가 있습니다.

연결형 리스트는 또한 단일 연결 리스트(Singly Linked List), 원형 연결 리스트(Circular Linked List), 이중 연결 리스트(Doubly Linked List), 이중 원형 연결 리스트(Doubly Circular Linked List)로 나눌 수 있습니다.

배열 기반 리스트(Array List) / 순차 리스트(Sequential List)

배열 기반 리스트 혹은 순차 리스트는 내부적으로 배열을 사용하여 데이터를 물리적으로 연속적인 메모리 공간에 저장합니다.

이는 배열과 유사하지만, 동적으로 크기가 조정될 수 있는 특성을 가지고 있습니다. 즉, 요소가 추가되거나 제거될 때 내부적으로 메모리를 재할당하여 리스트의 크기를 조정할 수 있습니다.

이 정의를 보면, vector가 생각나실 겁니다.

맞습니다. 자료구조상으로 배열 기반 리스트(Array List) / 순차 리스트(Sequential List)와 벡터(vector) 사이에는 본질적인 차이가 거의 없습니다.

라이브러리에 따라 두 자료구조의 구현상의 차이가 생길 수 있어도 이론적인 관점에서 기본적인 개념은 동일합니다.

좀 더 자세한 내용을 원하신다면, vector 글을 참조해주시길 바랍니다.

연결형 리스트(Linked List)

연결형 리스트는 논리적으로 연속적이지만 물리적으로 연속적일 필요는 없는 자료구조입니다.

Linked List는 이름에서 알 수 있듯이 Link를 사용합니다. C++에서는 포인터로 다음에 올 데이터를 가리키게 되고, 각 데이터 혹은 데이터 구성 요소를 노드(Node)라고 부릅니다.

즉, 물리적으로 연속적일 필요는 없지만, 각 노드(Node)를 연결(Link)해서 논리적으로 연속적인 자료구조를 연결형 리스트(Linked List)라고 합니다.

이중 연결 리스트 예시 이미지

특징

연결형 리스트의 특징은 이렇게 정리할 수 있을 것 같습니다.

1.메모리 재할당 없이 동적 크기 조정이 가능합니다.

즉, 정해진 메모리 공간이 없어서, 원하는 노드(Node)의 메모리만 추가하거나 삭제하는 것으로 매우 동적인 크기 조정이 가능해집니다.

2.요소의 삽입과 삭제가 용이합니다.

연결형 리스트는 각 노드(Node)를 가리키는 포인터만 변경하는 것으로 리스트의 순서를 바꾸기 매우 좋습니다.

예를 들어, 30이라는 노드를 삭제하려고 하면, 물리적으로 연속적인 메모리 공간에서는 각 데이터를 한칸씩 옮기는 $O(N)$의 작업이 필요했다면, 연결형 리스트에서는 30 앞 뒤의 노드에서 각각 가리키던 포인터의 주소만 바꾸는 것으로 $O(1)$의 시간으로 삭제할 수 있습니다.

포인터를 대체하는 것으로 요소를 간단하게 제거하는 모습

3.인덱스를 통한 빠른 접근이 불가능합니다.

만약, 연속된 메모리였다면, 메모리 주소 연산을 통해 매우 빠르게 중간 요소에 접근할 수 있겠지만,

연결 리스트는 어떤 위치에 어떤 노드(Node)가 있을지 예측할 수 없습니다.

따라서 중간 요소에 접근하기 위해서는 순차적인 접근이 필요하고, $O(N)$의 시간으로 탐색해야 합니다.

단일 연결 리스트(Singly Linked List)

단일 연결 리스트는 연결(Link)하는 포인터가 다음 노드(Node)만을 가리키는 자료구조입니다.

단순 순차 탐색만 사용할 예정이고 데이터가 앞에서만 추가될 예정이고, 앞/뒤로 이동할 필요가 없다면, 단일 연결 리스트가 좋은 선택일 수 있습니다.

단일 연결 리스트는 이중 연결 리스트에 비해 가볍고 구현이 더 간단하기 때문에 성능에 약간 더 이점을 가질 수 있습니다.

(단순히 생각해서도 이전 노드를 가리키는 포인터가 없기 때문에 이전 노드에 대한 참조를 관리할 필요가 없고, 따라서 조금 더 가벼울 수 있습니다.)

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트는 연결(Link)하는 포인터가 이전 노드(Node)와 다음 노드(Node)를 모두 가리키는 자료구조 입니다.

만약, 요소를 순차적으로 저장해야 하고, 중간에 자주 삽입/삭제 될 예정이면서 요소의 앞/뒤로 탐색할 필요가 있다면 이중 연결 리스트를 사용해야 할지도 모릅니다.

이중 연결 리스트는 양방향 탐색이 가능하다는 것이 중요한 장점입니다.

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

원형 연결 리스트 혹은 이중 원형 연결 리스트는 선형으로 연결되어 있던 리스트의 마지막 노드(Node)가 첫 번째 노드(Node)를 가리키도록 하여 순환 탐색을 할 수 있게 한 자료구조입니다.

원형 연결 리스트의 장점을 설명하기 전에, 먼저 위에 그린 그림은 C++ 기준 자료구조 입니다.

원래는 다음과 같은 형태가 원래 자료구조의 형태입니다.

시작 위치를 head 포인터가 가리키고 각 노드에 단일 혹은 이중으로 포인터를 가집니다.

이러한 형태의 아쉬운점은 마지막 위치에 노드를 추가/삭제 하려면 $O(N)$의 탐색시간을 가진 후에나 추가된다는 점입니다. 즉, 삽입/삭제의 장점인 $O(1)$이 무색하게도 총 $O(N)$의 시간이 걸리게 됩니다.

이 단점을 보완하고자 하는 구조가 원형 연결 리스트입니다.

원형 연결 리스트는 head가 마지막에 있기 때문에 맨 앞이나 맨 끝에 접근하기 쉽다.

원형 연결 리스트에서 head 포인터는 마지막 요소를 가리키게 됩니다.

이렇게 구조가 변경되면, head 포인터는 마지막 노드(End Node)를 가리키고, 마지막 노드(End Node)의 다음 연결(Link)은 첫 번째 노드(Begin Node)를 가리키므로 마지막 위치와 첫 위치를 계산하기 편해집니다.

즉, 순환 구조를 가지기 때문에 첫 번째 위치에 삽입하던 마지막 위치에 삽입하던 head가 가리키는 다음 위치에 삽입하고, 그게 첫 번째 노드라면 head는 그대로 두고, 마지막 노드라면 head가 가리키는 노드만 바꾸면 되는 구조가 되는 겁니다.

이중 원형 연결 리스트는 이 구조에서 각 노드(Node)만 이중 포인터를 가지는 구조입니다.

특징

리스트의 특징은 연결형 리스트(Linked List)를 기준으로 하겠습니다.

연결형 자료구조: 연결형 리스트는 각 요소를 가리키는 포인터로 노드(Node)끼리 연결(Link)하여 순서를 보장하는 선형 자료구조입니다.
동적 크기 조정: 메모리 재할당 없이 노드를 추가하거나 삭제하는 것만으로 매우 동적인 크기 조정이 가능해집니다.
요소의 삽입/삭제가 용이: 포인터로 노드를 가리키는 형태라 메모리가 연속적일 필요가 없어, 중간에 요소를 삽입/삭제하기 매우 용이합니다.
컨테이너 특성: 리스트는 STL 시퀀스 컨테이너이며, STL의 이터레이터와 다양한 알고리즘을 사용할 수 있습니다.

장단점

장점

동적 크기 선형 자료구조: 정해진 크기와 공간 없이 데이터를 가지는 노드를 추가/삭제하는 것으로 동적인 자료구조를 가집니다.
중간 삽입/삭제: 삽입/삭제가 빈번한 상황에서 삽입/삭제 될 위치만 미리 가지고 있다면 vector보다 매우 빠르게 요소를 삽입/삭제 할 수 있습니다.
- 다만, 특정 요소를 찾아야 한다면, 탐색 시간이 $O(N)$이 걸리게 됩니다.
메모리 효율: 필요할 때마다 노드만 추가하기 때문에 미리 공간을 할당하는 vector에 비해 효율적입니다.

단점

임의 접근 불가: 연속된 메모리였다면, 메모리 주소 연산을 통해 매우 빠르게 중간 요소에 접근할 수 있겠지만, 연결 리스트는 어떤 위치에 어떤 노드(Node)가 있을지 예측할 수 없기 때문에 임의 접근이 불가능합니다. (탐색 시간: $O(N)$)
약간의 메모리 비효율: 각 노드에는 포인터를 추가로 저장해야 하므로 데이터만 저장하는 형태에 비해 비효율적일 수 있습니다.
- 만약, 정해진 메모리 공간만 사용하는 array나, vector에서 예약 공간을 효율적으로 예약할 수만 있다면, array나 vector에 비해 더 많은 메모리를 사용할 수 있습니다.
캐시 효율성 저하: 메모리가 연속적인 array나 vector에 비해 공간 지역성(Spatial Locality)이 떨어져 캐시 효율성이 낮습니다.
메모리 단편화: 자주 메모리를 할당/해제하면서 작은 메모리 조각들이 흩어져 메모리 단편화를 증가시킬 수 있습니다.

사용법

생성자

C++ STL의 <list>와 <forward_list>는 각각 이중 연결 리스트와 단일 연결 리스트를 구현합니다.

  
std::list<typename _Ty> l(); // 기본 생성자
std::list<typename _Ty> l(size_t _Count, _Ty& _Val); // 특정 값으로 정해진 갯수만큼 생성
std::list<typename _Ty> l(std::list<typename _Ty> _Right); // 다른 리스트의 복사본을 생성

std::forward_list<typename _Ty> fl(); // 기본 생성자
std::forward_list<typename _Ty> fl(size_t _Count, _Ty& _Val); // 특정 값으로 정해진 갯수만큼 생성
std::forward_list<typename _Ty> fl(std::forward_list<typename _Ty> _Right); // 다른 리스트의 복사본을 생성

멤버 함수

함수	list	forward_list	설명
list.assign(n, x)	O	O	x 값으로 n개의 요소를 할당합니다.
list.size()	O		리스트에 있는 요소의 수를 반환합니다.
list.push_front(x) / list.pop_front()	O	O	리스트의 시작에 요소 x를 추가/제거합니다.
list.push_back(x) / list.pop_back()	O		리스트의 끝에 요소 x를 추가/제거합니다.
list.front()	O	O	첫 번째 요소에 대한 참조를 반환합니다.
list.back()	O		마지막 요소에 대한 참조를 반환합니다.
list.sort()	O	O	요소를 정렬합니다.
list.reverse()	O	O	요소의 순서를 뒤집습니다.
list.swap(other_list)	O		other_list와 내용을 교환합니다.
list.clear()	O	O	모든 요소를 제거합니다.
list.remove(x)	O	O	x와 일치하는 모든 요소를 제거합니다.
list.remove_if(pred)	O	O	조건에 따라 요소를 제거합니다.
list.unique()	O		중복된 요소를 제거합니다.
list.merge(other_list)	O	O	other_list와 합병합니다.
list.begin() / list.end()	O	O	컨테이너의 시작과 끝을 가리키는 이터레이터를 반환합니다.
list.rbegin() / list.rend()	O		컨테이너의 시작과 끝을 가리키는 역방향 이터레이터를 반환합니다.
list.insert(iter, x)	O		iter가 가리키는 위치에 요소 x를 삽입합니다.
list.erase(iter)	O		iter가 가리키는 위치의 요소를 제거합니다.
list.splice(iter, other_list)	O		other_list의 요소를 iter가 가리키는 위치로 이동합니다.
flist.before_begin()		O	첫 번째 요소 이전을 가리키는 반복자를 반환합니다.
flist.insert_after(iter, x)		O	iter가 가리키는 위치 뒤에 요소 x를 삽입합니다.
flist.emplace_front(iter, x),
flist.emplace_after(iter, x)		O	iter가 가리키는 위치 뒤에 새 요소 x를 직접 생성합니다.
flist.erase_after(iter)		O	iter가 가리키는 위치 뒤의 요소를 제거합니다.

컴퓨터 공학, 자료구조