0x04강 - 연결리스트

목차 

0x00  정의와 성질 

0x01 기능과 구현 

0x02 STL list

0x03 연습문제 

---

0x00  정의와 성질 

배열과 연결리스트 비교

연결리스트의 성질 

• k번째 원소를 조회/변경하기 위해 O(k)가 필요함 
• 임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 할때 O(1) 필요함
• 배열과 달리 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결리스트의 종류

• 단일 연결 리스트 : 원소가 ‘다음’원소의 주소를 알고 있다.
• 이중 연결 리스트 :  원소가 ‘이전’원소의 주소와 ‘다음’원소의 주소를 둘 다 알고 있다. 
• 원형 연결 리스트 : 마지막 원소가 가장 처음원소의 주소를 알고 있다. 

배열과 연결리스트 비교

배열은 원소의 값만 저장한다. 반면에 연결리스트는 '다음 원소의 주소'도 저장하므로 메모리를 더 필요로 한다. 

연결리스트를의 시간복잡도를 정리하면, 

임의의 위치에 있는 원소를 확인하거나 변경 = O(N)
임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 = O(1)
(추가할 주소를 알고 있는 경우, O(1)에 가능하다는 의미다. )

배열에 비해, ‘다음 주소’만큼의 메모리를 소모한다. 

그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하다.
64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하게 된다. 
즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다. 

---

0x01 기능과 구현 

기능

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

어디에 연결리스트가 어디에 활용될까 ?

메모장! 을 예로 들 수 있다.
커서를 옮기고, 글자를 지우고 이러한 변경 연산이 많다. 
이렇게 추가 제거 연산이 자주 발생하는 경우 연결리스트 사용을 고려해보자. 

구현

STL에서 제공하는 list를 쓰자. 
STL에 연결리스트가 있는데, 이 컨테이너의 이름은 list이고  내부적으로 Double Linked List로 구현되어 있다. 
면접에서의 손코딩을 대비할 때 STL list를 이용해서 끄적이며 연습하자. 

 

정석적인 구현

NODE 구조체나 클래스를 만들어서 원소가 할당될 때마다 동적할당을 하고, 노드를 삭제하면 메모리를 해제하는 식으로 구현한다. 

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

야매 연결 리스트

STL의 list가 제공되지 않는 경우에 임시로 쓰는 연결리스트 형태를 배운다 .
메모리 할당 및 해제를 생략하고 배열만을 이용한다. 
메모리 누수 문제 때문에 실무에서는 절대 쓸 수 없다. 
구현 난이도가 일반적인 연결리스트보다 낮고, 시간복잡도도 동일하므로 코테에서만 애용하면 된다. 

메모리 할당 및 해제를 생략한 형태

야매 연결리스트는 원소를 배열로 관리한다. 

이전/다음 원소 주소를 가리키는 대신, 배열 인덱스를 저장하는 방식으로 구현한 연결리스트다. 

dat 배열 : 데이터 저장 
pre 배열 : 이전 노드의 주소 저장
nxt 배열 : 다음 노드의 주소 저장  
unused: 새로운 원소가 들어갈 수 있는 인덱스. 원소가 추가되면 1씩 증가한다. 
0번지: 시작점을 나타내기 위한 dummy node. 실제로 값을 저장하지 않는다. 

pre 값이나 nxt 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미다. 

모든 노드를 순회하여 출력하는 traverse() 함수 

0번지 (dummy node)에서 시작한다. 

더미노드가 가리키는 nxt는 2 인덱스를 가리킨다. 

따라서 더미노드 다음 노드는 2번지 노드다. 

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

insert() 함수 직접 구현해보기 

erase() 함수 직접 구현해보기 

 

전체 코드 바킹독 github 

#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]; // 새 원소의 nxt값에 삽입할 위치 nxt 값을 대입
  if(nxt[addr] != -1) pre[nxt[addr]] = unused; // 맨 마지막 원소에 데이터를 추가할 때를 처리.
  nxt[addr] = unused; // 삽입한 인덱스의 다음은 unused 
  unused++; // 새로 할당할 수 있는 인덱스 증가시키기 
}

void erase(int addr){
  nxt[pre[addr]] = nxt[addr]; // 이전 노드의 nxt에 삭제할 노드의 nxt할당. 
  if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; // 삭제할 노드가 마지막이 아닌 경우 처리. 
}

 

왜 pre[addr]이 -1인지는 체크를 하지 않아도 되는데 nxt[addr]이 -1인지는 체크를 해야 할까?

더미노드가 존재하니까 pre[addr]는 항상 -1이 아니다. 
맨 마지막 원소일 경우 nxt[addr]가   -1일 수 있기 때문이다. 

---

0x02 STL list

vector와 비슷한 것이 많다. 

push_back, pop_back, push_front, pop_front는 모두 O(1)의 시간복잡도다. 

iterator가 주소 역할을 한다! 매우 유용함.

int main(void) {

    ios_base::sync_with_stdio(0);
    cin.ignore(0);

    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을 가리키니까, 1이 출력된다. 
    
    L.push_back(5); // 10, 1, 2, 5
    L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입한다. 10, 6, 1, 2, 5
    t++; // t를 한 칸 뒤쪽으로 보낸다. t는 2를 가리킨다. 
    
    t = L.erase(t); // t가 가리키는 값을 제거하고, 그 다음 원소의 위치를 반환한다. 
    // 2를 제거하고 t는 5를 가리키게 된다. 10, 6, 1, 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 << ' ';
    
    return 0;

}

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

---

0x03 연습문제

연습문제를 풀어보고, 손코딩 문제는 잠시 생각해보고 답해보자. 

BOJ 1406번 에디터

BOJ 5397번 키로거 

BOJ 1158번 요세푸스 문제 

 

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

 

정답
동일한 노드가 나올때 까지 계속 다음 노드로 가면 됨. 
공간복잡도 O(1)
시간복잡도 O(N)

손코딩문제 2 
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은? 

 

정답 
일단 각 리스트의 길이를 구한다. 
더 긴 리스트에서 둘의 길이 차이 만큼 앞으로 이동시켜 놓는다. 
두 시작점이 만날 때 까지 두 시작점을 동시에 한 칸씩 전진 시키면 된다. 

 

손코딩문제 3 
주어진 연결 리스트 안에 사이클이 있는지 판단하라. 

 

정답 
Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시킨다. 
사이클이 없으면, 두 커서가 만나지 못하고 연결리스트의 끝에 도달한다. 
사이클이 있으면, 두 커서는 반드시 만나게 된다. 
거치는 모든 노드를 저장할 필요가 없다.  

---

다음 시간에는 스택을 공부한다. 

공부 내용 출처 : 바킹독 알고리즘 연결 리스트