Unity 내일배움캠프 TIL 1116 | 연결리스트 | STL list

[바킹독의 실전 알고리즘] 0x04강 - 연결 리스트

💡 연결 리스트

🌻 정의

• 원소를 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조

🌼 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요
   • 배열과 다르게 원소들이 메모리 공간에 연속적으로 위치하지 않기 때문
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬운 편

🌷 종류

• 단일 연결 리스트 (Singly Linked List) : 각 원소가 자신의 다음 원소의 주소를 저장
• 이중 연결 리스트 (Doubly Linked List) : 각 원소가 자신의 이전 원소와 다음 원소의 주소를 저장
  • 메모리를 더 사용하게 됨
  • STL list는 이중 연결 리스트
• 원형 연결 리스트 (Circular Linked List) : 끝이 처음과 연결되어 있음

🌹 배열 vs 연결 리스트

• 선형 자료구조

	배열	연결 리스트
k번째 원소에 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(overhead)	-	O(N)

🌲 구현

• 정석 구현

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

• 코딩 테스트에서는 STL list를 사용하면 됨
  • 만약 STL을 지원하지 않는다면 직접 구현

🌴 배열을 사용한 연결 리스트

• 원소를 배열로 관리
• pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장
• unused : 새로운 원소가 들어갈 수 있는 인덱스
• 0번지는 값이 저장되지 않고 시작 지점만 나타내는 dummy node

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

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

• 순회

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

• 원소의 삽입/삭제

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

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

// addr은 연결 리스트 상의 주소가 아닌 해당 원소의 주소를 의미
void insert(int addr, int num) {
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	// 마지막 위치에 원소 삽입 시 예외 처리 필요
	if (nxt[addr] != -1) pre[nxt[addr]] = unused;
	nxt[addr] = unused;
	unused++;
}

void erase(int addr) {
	nxt[pre[addr]] = nxt[addr];
	// 마지막 위치의 원소 삭제 시 예외 처리 필요
	if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

🍀 STL list

int main(void) {
	list<int> L = {1, 2};  // 1, 2

	// C++ 11 이상이라면 auto t = L.begin(); 으로 작성 가능
	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를 반환
	cout << *t << '\n';    // 5
}

🍂 list 순회

• C++ 11 이상

for (auto i : L) cout << i << ' ';

• C++ 11 미만

for (list<int>::iterator it = L.begin(); it != L.end(); it++)
		cout << *it << ' ';

끗..