[바킹독]4. 연결 리스트

강의/[C++]바킹독의 실전 알고리즘

[바킹독]4. 연결 리스트

개발의 피 2024. 8. 1. 21:32

https://youtu.be/C6MX5u7r72E?si=z4qj8E5HXtGTojKZ

https://blog.encrypted.gg/932

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

안녕하세요, 바킹독이에요. 배열은 복습 잘 하셨나요? 이번 시간에는 연결 리스트라는 것을 같이 배워보겠습니다. 배열에서 한 것 처럼 연결 리스트가 무엇인지 알아보고, 같이 구현해볼 것입니

blog.encrypted.gg

1. 정의와 성질
2. 기능과 구현
3. STL list
4. 연습 문제

1. 정의

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

원소들은 이곳 저곳에 흩어져있음

2. 성질

1) k번째 원소를 확인/변경하기 위해 O(k)가 필요

2) 임의의 위치에 원소를 추가/임의 위치의 원소 제거 : O(1)

3) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

3. 연결 리스트의 종류

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

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

단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있음

단점 : 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 씀

STL 연결 리스트 : list / 이중 연결 리스트 (구조)

원형 연결 리스트 : 끝이 처음과 연결되어 있음

각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관 x

4. 배열 vs. 연결 리스트

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

5. 기능

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

2) 임이의 위치에 원소를 추가/임의 위치의 원소 제거 : O(1)

6. 구현

1) Node 구조체

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

2) 배열 (야매 연결 리스트)

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

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

3) traverse 함수

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

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

4) insert 함수

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++;
}

1. 새로운 원소를 생성

2. 새 원소의 pre 값에 삽입할 위치의 주소를 대입

3. 새 원소의 nxt 값에 삽입할 위치의 nxt 값을 대입

4. 삽입할 위치의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경

5. unused 1 증가

5) erase 함수

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) 
    	pre[nxt[addr]] = pre[addr];
}

7. STL list

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 << ' ';
}

iterator(반복자) : 컨테이너의 요소를 가리키고 순회하는 데 사용되는 객체, 포인터와 유사한 개념, 컨테이너의 요소에 접근하고 조작할 수 있게 함