[바킹독의 실전 알고리즘] 0x04 연결리스트 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

(이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...)

바킹독의 실전 알고리즘 0x04강 링크

 

강의내용 복습

연결리스트의 정의와 성질

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

 

연결리스트의 성질

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

     배열과 달리 공간에 원소들이 연속해서 위치하고 있지 않기 때문

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

     연결리스트의 굉장히 큰 장점!

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

 

연결리스트의 종류

단일 연결 리스트(Singly Linked List) : 각 원소가자신의 다음 원소의 주소를 들고 있음

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

원형 연결 리스트(Circular Linked List) : 처음과 끝이 연결

cf. STL에 연결 리스트가 있는데, 이 컨테이너의 이름은 list고, 구조는 이중 연결리스트

 

배열 vs 연결리스트

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

*연결리스트에서, a번째 원소 뒤에 새 원소를 추가하는 상황은 엄밀히 말하면 a번째 원소까지 찾아간 뒤에 O(1)에 추가가 가능한 것임

**연결리스트는 각 원소가 다음원소 or 이전원소/다음원소의 주소값을 가지고 있어야 하기 때문에 추가공간 필요

cf.

선형 자료구조 : 배열, 연결리스트 등

비선형 자료구조 : 트리, 그래프, 해쉬 등

 

연결리스트의 기능과 구현

O(N)

임의의 위치에 있는 원소를 확인/변경

(임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때까지 첫 번째부터 순차적으로 방문해야하기 때문)

 

O(1)

1. 임의의 위치에 원소를 추가

    ->배열과 달리 추가하고 싶은 위치 뒤의 원소들을 옮길 필요X, 주소만 변경해주면 됨

    ->단, 추가하고 싶은 위치의 주소를 알고 있을 경우만 O(1)

2. 임의 위치의 원소를 제거

 

 

연결리스트의 정석적인 구현 - NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당 하는 방식

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

 

코딩테스트용 구현 - STL list 사용

 

하지만, STL을 허용하지 않는 코딩테스트의 경우(극히 드묾) 야매 연결리스트를 직접 구현한다.

아래는 원소를 배열로 관리하고, pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장하는 방식으로 구현되었다. (실무에서는 사용X)

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

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

dat[i] : i번지 원소의 값

pre[i] : i번지 원소 이전 원소의 인덱스, 값이 -1이면 이전 원소 존재X

nxt[i] : i번지 원소 다음 원소의 인덱스, 값이 -1이면 다음 원소 존재X

unused : 현재 사용되지 않는, 즉 새로운 원소가 들어갈 수 있는 인덱스, 원소가 추가되며 1씩 증가

0번지는 값이 들어가지 않고 시작점만을 나타내기 위한 dummy node로 고정

길이정보가 필요할 경우 len 변수 추가

 

cf. 변수이름을 data가 아닌 dat, next가 아닌 nxt라고 쓴 이유는 using namespace std; 안에 data, next 변수가 이미 있기 때문에 변수이름을 겹쳐쓰면 오류가 나기 때문..

 

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

void insert(int addr, int num);
void erase(int addr);
void traverse();
void insert_test();
void erase_test();

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

int main(void) {
  fill(pre, pre+MX, -1); //pre부터 pre+MX-1까지 -1로 채움
  fill(nxt, nxt+MX, -1); //next부터 next+MX-1까지 -1로 채움
  insert_test();
  erase_test();
}

//addr은 각 원소의 *주소*를 의미(=배열상에서 몇번지인가?), 연결리스트에서 몇번째인지를 의미하는것이 아님!!
void insert(int addr, int num){ //삽입하는 함수
    dat[unused] = num; //새로운 원소를 생성
    pre[unused] = addr; //새 원소의 pre값에 삽입할 위치의 주소를 대입
    nxt[unused] = nxt[addr]; //새 원소의 next 값에 삽입할 위치의 next 값을 대입
    if(nxt[addr] != -1) pre[nxt[unused]] = unused; //삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경
    nxt[addr] = unused; //삽입할 위치의 next 값을 새 원소로 변경
    unused++;
}

void erase(int addr){ //제거하는 함수
    nxt[pre[addr]] = nxt[addr]; //이전 위치의 nxt를 삭제할 위치의 nxt로 변경
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; //다음 위치의 pre를 삭제할 위치의 pre로 변경
}

void traverse(){ //연결리스트의 모든 원소를 출력하는 함수
  int cur = nxt[0]; //cur에는 다음으로 출력해야할 원소의 주소가 담긴다
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\n\n";
}

void insert_test(){
  cout << "****** insert_test *****\n";
  insert(0, 10); // 10(address=1)
  traverse();
  insert(0, 30); // 30(address=2) 10
  traverse();
  insert(2, 40); // 30 40(address=3) 10
  traverse();
  insert(1, 20); // 30 40 10 20(address=4)
  traverse();
  insert(4, 70); // 30 40 10 20 70(address=5)
  traverse();
}

void erase_test(){
  cout << "****** erase_test *****\n";
  erase(1); // 30 40 20 70
  traverse();
  erase(2); // 40 20 70
  traverse();
  erase(4); // 40 70
  traverse();
  erase(5); // 40
  traverse();
}

이대로라면 연결리스트의 제일 마지막 원소는 O(N)에 확인하게 된다.

코드를 조금만 바꿔서 O(1)로 구현하는 방법도 있는데 도전해보자!

(내생각엔 아마 연결리스트의 제일 마지막 원소의 위치를 저장하는 변수를 하나 만들거나, 연결리스트의 제일 끝에 dummy node를 하나 만들면 될것같은데...)

 

STL list

iterator가 주소역할

list::iterator라는 type을 치기 귀찮다면 auto=L.begin()사용 가능(C++ 11 이상)

#include <list> 헤더파일 포함

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

int main(void) {
  list<int> L = {3,2}; // 3 2
  list<int>::iterator t = L.begin(); // t는 3을 가리키는 중
  L.push_front(10); // 10 3 2
  cout << *t << '\n'; // t가 가리키는 값 = 3을 출력
  t = L.begin(); //t가 가리키는값 10으로 변경
  cout << *t << '\n'; // 10 출력
  L.push_back(5); // 10 3 2 5

  t++; //t가 가리키는 값 3으로 변경
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 3 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 3 5, t가 가리키는 값은 5
  cout << *t << '\n'; // 5

  //C++11 이상 순회
  for(auto i : L) cout << i << ' ';
  cout << '\n';

  //C++11 미만 순회
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

 

연습문제 복습(C++)

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

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

A. 시작점을 저장해두고 동일한 노드가 나올때까지 그냥 전진하면됨(공간복잡도 O(1), 시간복잡도 O(N)

 

Q. 중간에 만나는 두 연결리스트의 시작점드이 주어졌을 때 만나는 지점을 구하는 방법?

A. 먼저 두 리스트의 길이 차이를 구한 후, 다시 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 이동시켜놓은 다음에, 두 시작점이 만날때까지 동시에 한칸씩 전진시킴(공간복잡도 O(1), 시간복잡도(A+B))

 

Q. 주어진 연결리스트에 사이클이 있는지 판단하는법?

A. Floyd's cycle-finding algorithm이용. 한칸씩 가는 커서와 두칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있을 경우 두 커서는 반드시 만나게 된다. 사이클이 없으면 두 커서가 만나지 못하고 연결리스트의 끝에 도달한다.(공간복잡도O(1), 시간복잡도 O(N))

 

end()

끝주소 + 1

 

|를 커서라고 할 때,

연결리스트 삭제하는 상황

ABCD|EFG -> ABC|EFG

현재 iterator 위치가 E이므로 iterator--한 후(iterator위치를 C로 바꾼 후) erase(iterator)하면 다시 E가 반환됨

 

연결리스트에 삽입하는 상황

ABC|EFG -> ABCD|EFG

현재 iterator 위치가 E이므로 insert(iterator, D)