[Algorithm] 0x04 연결 리스트

Donghun Ha·2022년 1월 23일

참조: https://blog.encrypted.gg/932?category=773649

본 게시글은 개인 공부를 위해 위 링크를 토대로 정리한 글입니다.

정의와 성질

정의

연결리스트란? 원소들을 저장할 때, 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

예시)

학급 학생 중에 영은, 현지, 재현, 상혁 4명을 술래로 정했고, 이 4명을 기억하고 싶을 때,
배열은 4칸 짜리 배열을 만들고 4명을 저장하면 되지만, 연결리스트의 관점에선 영은이가 현지를, 현지가 재현이를, 재현이가 상혁이를 기억하는 것이다.

그리고 4명 전체가 필요하다면 영은이를 통해 나머지 3명이 누구인지 알아낼 수 있다.

성질

N번째 원소를 확인/변경하기 위해 $O(N)$ 이 필요함

공간이 연속되지 않기 때문에, 이전 노드를 거쳐서 N번째 원소까지 가야하기 때문에
임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)

이 성질이 배열과 비교했을 때, 가장 큰 차이가 있는 성질(연결리스트의 큰 장점)
원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만, 할당이 다소 쉬움

종류

배열과는 달리 연결 리스트에는 몇 개의 종류가 있는데, 아래와 같다.

단일 연결 리스트

각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트
이중 연결 리스트

각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있는 연결 리스트
단일 연결 리스트와 달리 이전 원소까지 저장하면서 메모리를 더 쓴다는 단점이 있다.
STL에서 연결 리스트를 제공하는데, 해당 컨테이너의 이름은 list이고 이중 연결 리스트다.
원형 연결 리스트

끝이 처음과 연결되어있다.
예시는 단일 연결 리스트지만, 이중 연결 리스트로 구현해도 상관없다.

배열 vs 연결 리스트

배열과 연결 리스트는 메모리 상에 원소를 저장하는 방법이 달라고, 원소들 사이의 선후 관계를 1 : 1로 정의한다.
그래서 배열과 연결 리스트는 둘 다 선형 자료구조라고 부른다.

둘 다 선형 자료구조이기에, 면접에서 둘을 비교하는 구술 문제를 내기도 한다.
면접 대비가 아니더라도 둘의 차이를 잘 알아야 적재적소에 알맞는 자료구조를 쓸테니 둘의 차이를 알아보자.

N번째 원소의 접근이 배열은 $O(1)$ , 연결 리스트는 $O(N)$ 이다.
임의 위치에 원소 추가/제거는 배열의 경우 $O(N)$ , 연결 리스트의 경우 $O(1)$ 이다.
배열은 메모리 상의 배치가 연속적이고, 연결 리스트는 불연속하다.
배열은 각 위치에 원소 데이터만 저장되면 추가적으로 필요한 공간이 없지만,
연결 리스트는 다음 또는 이전과 다음 주소를 저장할 주소 값을 가지게 되어서 추가적인 메모리를 사용한다.
주소의 메모리 공간 * N만큼 사용하여 N에 비례하는 만큼의 메모리를 추가로 사용한다.

기능과 구현

기능

임의의 위치에 있는 원소를 확인/변경, $O(N)$

임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때까지 각 원소를 순차적으로 방문해야한다.
임의의 위치에 원소를 추가, $O(1)$

임의의 위치에 원소를 추가하는 연산은 상수 시간에 가능한데, 특정 위치에 원소를 추가하고 싶다면
그 뒤 원소를 모두 옮기는 배열과 달리 앞의 원소를 추가할 원소와 연결하고 추가할 원소와 다음 원소를 연결하면 되기 때문이다.

하지만, 추가할 위치를 알고 있는 경우에만 $O(1)$ 이고, 모르는 경우 해당 위치까지 찾아가야 하기에 상수 시간이 걸린다고 말할 수 없다.
임의의 위치의 원소 제거, $O(1)$

임의의 원소를 제거하는 연산은 단순하다.
제거할 원소 앞의 원소에게 그 다음 원소를 연결해주게 되면 끝이다.

물론 제거한 원소는 메모리 누수를 막기 위해 메모리에서 삭제해야 한다.

구현

연결 리스트의 구현
```
struct NODE {
	struct NODE *prev, *next;
	int data;
}
```
연결 리스트의 정석적인 구현은 위와 같이 원소가 생성될 때, 동적할당하는 방식
하지만, 이 구현은 긴박한 코딩테스트에서 쓰기는 좋지 않다.
(코테에선 그냥 STL list를 활용하자)
야매 연결 리스트
```
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);
```
위 방식은 메모리 누수의 문제 떄문에 실무에서는 절대 사용할 수 없지만, 코테에서는 구현 난이도가 일반적인 연결 리스트보다 낮고 시간 복잡도도 동일하기 때문에 애용하면 된다! 위 사진에서 연결 리스트는 13(2) → 65(1) → 21(4) → 17(5)이라는 값을 가지고 있다. 특별히 0번지는 연결 리스트의 시작 원소로 고정되어 있는데, 이는 실제로 값이 들어있는 건 아니지만 연결 리스트의 제일 앞에 원소가 하나 있다고 생각할 것이다. 이렇게 하면 삽입과 삭제등의 기능 구현 시 덜 번거롭게 진행할 수 있다.

traverse 함수 traverse 함수는 연결 리스트의 모든 원소를 출력하는 기능을 가진다.

void traverse() {
	int cur = nxt[0];
	while (cur != -1) {
		cout << dat[cur] << ' ';
		cur = nxt[cur];
	}
	cout << "\n\n";
}
// 0번지에서 출발해, nxt에 적힌 값을 보고 계속 넘어가면서 dat을 출력
// cur에 nxt[cur] = -1이 담기면 끝이니까, 반복문 탈출

insert 함수
1. 새로운 원소 생성
2. 새 원소의 pre 값에 삽입할 위치의 주소를 대입
3. 새 원소의 nxt 값에 갑입할 위치의 nxt 값 대입
4. 삽입할 위치의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경
5. unused 1 증가
```
void insert(int addr, int num) {
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	if (nxt[addr] != -1)
		pre[nxt[addr]] = unused;
	unused++;
}
```
erase 함수
1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경
2. 다음 위치의 pre를 삭제할 위치의 pre로 변경
```
void erase(int addr) {
	nxt[pre[addr]] = nxt[addr];
	if (nxt[addr] != -1) 
		pre[nxt[addr]] = pre[addr];
}
```

STL list

STL은 list를 제공한다!

STL을 사용할 수 있는 상황이라면, 연결 리스트를 구현하는 것 보다는 그냥 STL을 쓰는 게 훨씬 편하니 STL list의 사용법을 익혀두면 좋다!

int main() {
	list<int> L = {1, 2};
	list<int>::iterator t = L.begin() // t는 1을 가리키는 중
	// C++11 이상에서는 auto t = L.begin과 같이 사용할 수도 있음
	L.push_front(10); // {10, 1, 2}
	L.push_back(5); // {10, 1, 2, 5}
	L.insert(t, 6); // {10, 6, 1, 2, 5}
	t++; // t는 2를 가리키는 중
	t = L.erase(t); // t가 가리키는 값 제거 / 리턴 값은 그 다음 원소인 5의 위치

연습 문제

문제 번호	제목	링크
1406	에디터	https://www.acmicpc.net/problem/1406
5397	키로거	https://www.acmicpc.net/problem/5397
1158	요세푸스 문제	https://www.acmicpc.net/problem/1158