연결리스트

연결 리스트란 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 이곳저곳에 흩어져있다. 

 

연결 리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함 - 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않아서 원소를 순서대로 탐색해야 한다. 

2. 임의의 위치에 원소를 추가/제거는 O(1) - 이 성질이 배열과 비교했을 때 큰 차이가있는 성질이고, 연결 리스트의 큰 장점이다. 

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

 

연결 리스트의 종류

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

 

2. 이중 연결 리스트

• 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있다.
• 단인 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있다.
• 다만 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점이 있다.
• STL에 연결리스트가 있는데, 이 컨테이너의 이름은 list이고 구조는 이중 연결 리스트이다.

3. 원형 연결 리스트 - 끝이 처음과 연결되어 있다. 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 된다. 

 

배열과 연결 리스트는 메모리 상에 원소를 놓는 방법은 달라도 원소들 사이의 선후 관계가 일대일로 정의된다. 즉, 원소들 사이에서 첫 번째, 두 번째, 이런 순서 개념이 존재한다는 것이다. 

 

그래서 배열과 연결 리스트는 선형 자료구조이다. 

 

배열 vs 연결 리스트

배열은 데이터만 딱딱 저장하면 될 뿐 딱히 추가적으로 필요한 공간이 없다. 하지만 연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소 값을 가지고 있어야 하므로 32비트 컴퓨터에서는 주소 값이 32비트(4바이트) 단위이므로 4N바이트가 추가로 필요하고 64비트 컴퓨터라면 주소 값이 64비트(8바이트) 단위이므로 8N바이트가 추가로 필요하게 된다. 즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다. 

 

임의의 위치에 원소를 추가하는 연산이 O(1)에 가능한 조건은 추가하고 싶은 위치의 주소를 알고 있을 때만 해당한다. 만약 앞의 원소의 주소를 주지 않고 그냥 84라는 원소를 세번째 원소 뒤에 추가하라는 명령의 경우에는 세 번째 원소까지 찾아가야 하는 시간이 추가로 걸려서 O(1)이라고 말할 수 없다. 

 

임의의 위치의 원소를 제거하는 연산도 O(1)에 가능하다. 

 

정리하자면 

• 임의의 위치에 있는 원소를 확인/변경 = O(N)
• 임의의 위치에 원소를 추가/제거 = O(1)

따라서 임의의 위치에서 원소를 추가하거나 임의의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결 리스트의 사용을 고려해보면 좋다.

 

코딩테스트에서는 그냥 STL list를 활용하면 된다. STL list가 이중 연결 리스트 구조를 가지고 있기 때문에 그냥 가져다 쓰면 된다. 만약 STL을 허용하지 않는 코딩 테스트라면 직접 연결 리스트를 구현해야 한다. (드물긴 하다..) 

 

야매 연결리스트

야매로 구현하면 정석적인 방법보다 난이도가 크게 높지 않으니 이 방법도 익혀두자. 해당 방법은 메모리 누수의 문제로 실무에서는 절대 쓸 수 없는 방식이지만 코딩 테스트에서는 구현 난이도가 일반적인 연결 리스트보다 낮고 시간 복잡도도 동일하기 때문에 애용하면 된다. 

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

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

위의 코드는 원소를 배열로 관리하고 pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장하는 방식으로 구현한 연결 리스트이다. 

dat [i]는 i번지 원소의 값, pre[i]는 i번지 원소에 대해 이전 원소의 인덱스, nxt[i]는 다음 원소의 인덱스이다. pre나 nxt의 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미이다. 

unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스이고 원소가 추가된 이후에는 1씩 증가될 것이다. 그리고 특별히 0번지는 연결 리스트의 시작 원소로 고정되어 있다. 달리 말하면 0번지는 값이 들어가지 않고 단지 시작점을 나타내기 위한 dummy node이다. 현재의 코드 상에는 별도로 길이 정보를 두지 않았지만 길이가 필요하다면 따로 len변수를 두고 원소가 추가될 때 1 증가시키고 제거 시 1 감소시키면 된다. 

 

주어진 연결 리스트는 13,65,21,17이라는 값을 가지고 있다.

이들은 각각 배열에서 2번지, 1번지, 4번지, 5번지에 저장되어 있다고 생각. 이 위치들은 임의로 정한 위치이고 실제로는 1번지부터 unused가 가리키고 있는 위치 한 칸 전까지 사이 아무 곳에 위치하게 된다.

 

그리고 특별히 0번지는 연결 리스트의 시작 원소로 고정되어 있다.

즉, 실제로 값이 들어있는 것은 아니지만 관념적으로 연결 리스트의 제일 앞에 원소 하나가 있다고 생각한다.

그 이유는 dummy node를 두지 않으면 나중에 삽입과 삭제 등의 기능을 구현할 때 원소가 아예 없는 경우에 대한 예외처리를 해야 하는데, 관념적으로 dummy node를 두면 예외처리가 덜 번거로워져서 그렇다. 새로운 노드를 추가할때 첫번째 노드인지 확인할 필요가 없다. 

 

일단 0번지의 dat, pre, nxt를 보면 dummy node라 dat는 의미가 없으니 -1로 두고 pre는 해당 원소의 이전 원소가 존재하지 않으니 -1이고 nxt는 13이 들어있는 주소인 2번지의 2가 된다. 그다음으로 13이 들어있는 2번지의 dat, pre, nxt는 13,0,1 이 된다. pre는 이전 원소의 주소인 0, nxt는 다음 원소의 주소인 1, dat는 13. 

 

기능 구현

 

이제 각 기능을 구현해보는 시간을 가질 텐데, traverse 함수를 먼저 구현해보겠다. traverse함수에서는 연결 리스트의 모든 원소들을 출력할 것이다. 

 

0번지에서 출발해 nxt에 적힌 값을 보고 계속 넘어가면서 dat를 출력하는 방식으로 구현해야 한다. 코드를 보면 cur라는 변수에 각 원소들의 주소가 담겨서 이동하는 방식이다. 

 

1. 원소 출력

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

 

2. 원소 삽입

 

원소 삽입은 다음과 같은 과정을 따라 구현을 한다. 

1. 새로운 원소를 생성
2. 새 원소의 pre 값에 삽입할 위치의 주소를 대입
3. 새 원소의 nxt 값에 삽입할 위치의 nxt 값을 대입
4. 삽입할 위치의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경
5. unused 1 증가

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

 

 

3. 원소 삭제 

 

원소 삭제는 다음과 같은 과정을 따라 구현한다. 

1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경
2. 다음 위치의 pre를 삭제할 위치의 pre로 변경

위의 과정에서 삭제할 위치인 1번지에서는 dat, pre, nxt는 전혀 건드리지 않고 내버려 두는데 이러한 구현 방법 때문에 이 야매 연결 리스트에서 제거된 원소가 프로그램이 종료될 때까지 메모리를 점유하고 있고 그렇기 때문에 실무에서는 사용할 수 없는 구현 방식이다. 하지만.. 알고리즘 문제에서는 insert의 횟수가 제한이 있고 그럴 때에는 그냥 배열을 넉넉히 잡고 이 야매 연결 리스트를 사용하면 된다. 

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

위의 코드에서 if(nxt [addr]!= -1)이라는 처리가 있는데 왜 pre [addr]이 -1인지는 체크를 하지 않아도 되는데 nxt [addr]이 -1인지는 체크를 해야 하는지 답해봐라. 

그 이유는 dummy node의 존재로 인해 그 어떤 원소를 지우더라도 pre [addr]는 -1이 아님이 보장되지만 nxt [addr]는 제일 마지막 원소를 지우는 상황에서 값이 -1일 수 있기 때문에 그렇다. 

 

전체 코드

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

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

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

void traverse(){
  int cur = nxt[0];
  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();
}

int main(void) {
  fill(pre, pre+MX, -1);
  fill(nxt, nxt+MX, -1);
  insert_test();
  erase_test();
}

---

STL list

#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을 출력  - *t로 접근한다.
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5 - (iterator,값)을 인자로 받음
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환 -(iterator)을 인자로 받음
                  // 10 6 1 5, t가 가리키는 값은 5
  cout << *t << '\n'; // 5
  //C++11 이상
  for(auto i : L) cout << i << ' ';
  cout << '\n';
  //다른 방법
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

stl을 사용할 수 있는 상황이면 연결 리스트를 직접 구현하는 것보다 그냥 stl을 쓰는 게 훨씬 더 편하니 STL list의 사용법을 익혀두자.  

 

push_back, pop_back, push_front, pop_front는 모두 O(1)이고, iterator가 주소 역할을 한다. 

 

03번째 줄에서 list::iterator라는 type을 치기가 귀찮으면 C++11 이상일 때 auto t = L.begin()으로 써도 된다. 

 

erase는 제거한 다음 원소의 위치를 반환한다. 

 

마지막으로 순회를 할 때에는 C++11 이상이라면 12번째 줄과 같이 편하게 할 수 있지만, C++11 미만이라면 14, 15번째 줄과 같이 아주 불편하게 할 수밖에 없다.