[0x04] 연결리스트

정의와 성질

성질

1. 임의의 위치에 있는 원소를 확인/변경 : O(N) (불연속이기 때문에 그 원소까지 찾아가야 함)
2. 임의의 위치에 원소를 추가/제거 : O(1)
3. 원소들이 메모리 상에 연결되어 있지 않아 cache hit rate가 낮지만 할당이 다소 쉬움

종류

1. 단일 연결 리스트 single linked list
2. 이중 연결 리스트 doubly linked list
3. 원형 연결 리스트 circular linked list

배열 vs 연결 리스트

• overhead : 앞, 뒤 원소의 주소값을 가지고 있어야 한다 (2^n byte이면 n만큼 추가로 필요)

구현

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

야매 연결리스트

const int MAX = 1000005;
int data[MAX], pre[MAX], next[MAX]; // pre next : 이전/다음 원소의 주소
int unused = -1; // 새로운 원소가 들어갈 수 있는 인덱스, 원소 시작 시 1씩 증가
// 길이가 필요하면 len 변수를 두면 된다

// 0번째는 연결리스트의 시작, 즉 dummy node (삽입, 삭제 시 예외처리 줄이기 위해)
fill(pre, pre+MAX, -1);
fill(next, next+MAX, -1);

traverse 함수

void traverse() {
	int cur = next[0];
	while(cur != -1){
		cout << data[cur] << ' ';
		cur = next[cur];
	}
	cout << "\\n\\n";
}

insert와 erase 함수

void insert(int addr, int num) { // 인자 : 삽입할 위치, 삽입할 값
	// 1. 새로운 원소 생성
	data[unused] = num;
	pre[unused] = addr;
	next[unused] = next[addr]

	// 2. 삽입할 위치의 next, 삽입할 위치의 다음 원소의 pre 값 변경
	if (next[addr] != -1) pre[next[addr]] = unused; // 맨 마지막이 아닐 경우
	next[addr] = unused;

	// 3. unused 증가
	unused++;
}

void erase(int addr) {
	// 1. 이전 위치의 next를 삭제할 위치의 next로 변경 (dummy node로 인해 -1 아님 보장)
	next[prev[addr]] = next[addr];
	// 2. 다음 위치의 pre를 삭제할 위치의 pre로 변경
	if (next[addr] != -1) prev[next[addr]] = prev[addr];
}

STL list

• insert (idx, val) : idx 앞에 val을 삽입
• erase (idx) : idx를 제거하고 그 다음 위치의 val을 반환

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  list<int> L = {1,2}; // 1 2
  list<int>::iterator t = L.begin(); // t는 1을 가리키는 중
  L.push_front(10); // 10 1 2
  cout << *t << '\\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 [앞에] 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 5
  cout << *t << '\\n'; // 5
  for(auto i : L) cout << i << ' ';
  cout << '\\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

면접 문제

1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?

→ 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다

→ 공간복잡도 O(1), 시간복잡도 O(N)

 

2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법?→ 그 후 다시 두 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동⇒ 공간복잡도 O(1), 시간복잡도 O(A+B)

→ 두 지점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진

→ 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함

 

3. 주어진 연결 리스트 안에 사이클이 있는지 판단?

→ Floyd’s Cycle-finding algorithm

한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면

사이클이 있을 경우 두 커서는 무조건 만남

없을 경우 두 커서는 연결 리스트의 끝에 도달

⇒ 공간복잡도 O(1), 시간복잡도 O(N)