강의

https://www.youtube.com/watch?v=C6MX5u7r72E&t=56

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x04.md

특징

연결리스트에서 탐색에 필요한 시간복잡도는 O(n)
임의의 위치에 원소를 추가/제거 시 O(1)
원소들이 메모리상에 연속있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움
배열과 연결리스트는 둘 다 선형자료구조이다.

종류

단일연결리스트
이중연결리스트
원형연결리스트

구현

정석

struct NODE {
	struct NODE *prev, *next;
	int data;
};

야매버전

원소저장할 dat 배열, 이전 노드 다음 노드 가리킬 pre, nxt 배열 생성

const int MX = 10000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);

traversal

void traversal() {
	int cur = nxt[0];
	while (cur != -1) {
		cout << dat[cur] << ' ';
		cur = nxt[cur];
	}
	cout << "\n\n";
}

insert

void insert(int addr, int num) {
	// 원소 삽입
	dat[unused] = num;
	// 삽입한 원소의 pre와 nxt 변경
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	// 삽입될 다음 노드의 pre 변경
	if (nxt[addr] != -1) pre[nxt[addr]] = unused;
	// 삽입될 잉전 노드의 nxt 변경
	nxt[addr] = unused;
	unused++;
}

erase

void erase(int addr) {
	// 이전 원소의 nxt 변경
	nxt[pre[addr]] = nxt[addr];
	// 다음 원소의  pre 변경
	if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

연습문제

손코딩 2

Q. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 법
A. 두 연결 리스트의 길이를 구하고 더 긴 쪽을 차이만큼 앞으로 앞당김.
차이만큼 앞 당기기 전에서는 절대 만나는 지점이 나올 수가 없음. 그러니까 일단 앞당겨 놓고 동시에 다음 노드로 진전시키면 만나는 지점을 구할 수 있음

손코딩 3

Q. 주어진 연결 리스트 안에 사이클이 있는지 판단하라
A. Floyd's cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
-> 속도가 다른 두 이터레이터는 사이클이 있는 경우 결국 만나게 된다. 한 쪽이 NULL을 만나게 되면 그건 사이클이 없다는 뜻이다.