[실전 알고리즘] 연결 리스트

연결 리스트가 무엇인지 알아보고, 구현도 해볼 것이다.

 

1. 정의와 성질

연결 리스트 정의

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

원소들은 배열과는 다르게 이곳 저곳 흩어져있다.

연결 리스트 성질

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

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

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

- 배열과 비교앴을 때 큰 차이가 있는 성질이고, 연결 리스트의 큰 장점이다.

 

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

- 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할당이 쉽다.

연결 리스트 종류

1. 단일 연결 리스트

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

 

2. 이중 연결 리스트

- 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있다. STL에 연결 리스트의 구조 또한 이중 연결 리스트이다.

 

3. 원형 연결 리스트

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

 

배열 VS 연결 리스트

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

 

배열과 연결 리스트는 메모리 상에 원소를 놓는 밥법은 다르다고 해도 어찌됐든 원소들 사이의 선후 관계가 일대일로 정의된다.

 

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

 

표의 마지막에 추가적으로 필요한 공간, 즉 overhead를 생각해보면 배열은 데이터만 딱딱 저장하면 될 뿐

딱히 추가적으로 필요한 공간이 없다. 굳이 따지면 길이 정보를 저장할 int 1개가 필요할 수 있지만 이건 너무 미미하니

신경을 쓸 필요가 없다. 그런데 연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 한다. 그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하고,

64비트이면 8N 바이트가 추가로 필요하다. 즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.

 

임의의 위치에 원소를 추가하는 연산은 O(1)에 가능하다. 왜냐하면 배열과는 다르게 주소만 변경 해주면 되기 때문이다.

단, 착각하면 안되는게 있다. 추가하고 싶은 위치의 추소를 알고 있을 경우에만 O(1)이다.

임의 위치의 원소를 제거하는 연산이고 이것 또한 O(1)에 가능하다. 물론 다음에 메모리 누수를 막기 위해 메모리에서 없애야 한다.

 

연결 리스트가 쓰이는 대표적인 상황이 바로 메모장과 같은 텍스트 에디터이다. 물론 실제 텍스트 에디터는 매 순간순간마다

화면에 결과를 출력해야 하니 아마도 그냥 배열로 구현을 할 것 같다.

 

그러나 예를 들어 커서를 옮기고 글자를 지우는 것과 같은 연산들이 다양하게 주어진 후 최종 결과를 출력하라는 문제라고 한다면

우리는 커서가 가리키는 위치에 글자를 추가하거나 글자를 지우는 명령을 계속 수행해야 한다.

 

그러니까 임의 위치에 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결리스트를 고려해도 좋다.

---

2. 기능과 구현

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

원래 연결 리스트의 정석적인 구현은 위의 코드 처럼 NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당을 하는 방식이다.

 

그런데 이 구현은 긴박한 코딩테스트에서 쓰기는 별로 좋지가 않다. 코딩 테스트에서는 그냥 STL list를 활용하면 된다.

그런데 코딩테스트에서 STL을 허용하지 않는다면 직접 연결 리스트를 구현해야 한다. 물론 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 이다.

traverse 함수

연결 리스트의 모든 원소들을 출력하는 함수

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

배열에서 모든 원소들을 출력할 때에는 그냥 arr[0], arr[1], ...을 출력하면 됐는데 이 야매 연결리스트에서는 다르다.

0번지에서 출발해 nxt에 적힌 값을 보고 계속 넘어가면서 dat을 출력하는 방식으로 구현해야 한다.

 

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 증가

 

erase 함수

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

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

---

3. STL List

int main(void){
	list<int> L = {1,2};
    list<int>::iterator t = L.begin();
    L.push_front(10);
    cout << *t << '\n';
    L.push_back(5);
    L.insert(t,6); // t가 가리키는 곳 앞에 6을 삽입
    t++;
    t = L.erase(t)
}

야매 연결 리스트에서는 0번지, 즉 제일 앞의 원소를 더미 노드로 사용하지만 STL list에서는 제일 뒤의 원소가 더미 노드입니다. 그래서 L.begin()은 제일 앞에 있는 원소를 가리키지만 L.end()는 제일 뒤에 있는 원소의 한 칸 뒤를 가리킨다는 점에 주의해야 한다.