[바킹독 실전 알고리즘 0x04] 연결 리스트

연결 리스트의 성질

• k번째 원소를 확인/변경하기 위해 O(k)가 필요하다.
• 임의의 위치에 원소를 추가/제거는 O(1)의 시간복잡도를 가진다.
• 원소들이 메모리 상에 연속해있지 않아 cache hit rate가 낮지만 할당이 다소 쉽다.(코테에서는 몰라도 됨)

 

연결 리스트의 종류

• 단일 연결 리스트
• 이중 연결 리스트(이전+이후 원소의 주소 저장. 단일 연결 리스트보다 메모리를 많이 씀.)
• 원형 연결 리스트

배열과 연결 리스트는 둘 다 선형 구조라서 둘의 차이를 비교하는 문제가 면접 등에서 빈출된다.

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

연결리스트는 다음 원소 혹은 이전+ 다음 원소의 주소값을 저장할 추가적인 메모리 공간이 필요하다.

그래서 32비트 컴퓨터는 주소값이 32비트 단위이니 4n 단위로, 64비트 컴퓨터는 주소값이 64비트 단위이니 8n 단위로 메모리가 추가적으로 필요하다. 

 

기능과 구현

임의의 위치에 있는 원소를 확인/변경하기 위해서는 그 위치에 도달하기까지 원소들을 순차적으로 방문해야 한다. 연결 리스트의 특성에 따르면, 우리는 모든 원소들 중 첫번째 원소의 주소만 알고 있다. 4번째 원소의 값을 알고 싶다면 1->2->3->4 순으로 방문해야 한다. k번째 원소를 보기 위해서는 k만큼의 시간이 필요하고, 전체 N개의 원소에 대해서는 평균적으로 N/2만큼의 시간이 필요할테니 전체 시간복잡도는 O(N)이다. 

 

추가하고 싶은 원소의 주소를 알고 있다고 가정할 때, 임의의 위치에 원소를 추가하는 연산은 O(1)의 시간복잡도를 가진다. 어떤 원소 뒤에 새 원소를 추가하고싶은지만 알면 이전 원소에 새 원소의 주솟값을 대입하면 되기 때문이다.

 

임의의 위치의 원소를 제거하는 것도 추가하는 과정과 마찬가지로 O(1)의 시간복잡도를 가진다.

 

연결리스트가 응용되는 대표적인 곳은 메모장과 같은 텍스트 에디터이다. 글자를 지우고 쓰는 과정을 계속해서 반복해야 하는데, 연결 리스트를 사용하면 O(1)의 시간복잡도를 가지고 임의의 위치에 원소를 추가/제거하는 연산을 수행할 수 있기 때문이다. 

 

구현

연결리스트를 직접 구현하는 것은 면접 빈출 주제이기 때문에 구현하는 방법을 미리 익혀둬야 한다. 

그치만 제한시간이 있는 코딩테스트에서는 직접 구현하기보다는 STL을 사용하는 것이 좋다.

레퍼런스: http://www.cplusplus.com/reference/list/list/  

https://cplusplus.com/reference/list/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=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 << ' ';
}

 

STL을 허용하지 않는 코딩 테스트의 경우, 야매 구현법을 사용해보자. 이 구현방법은 원소를 배열로 관리하고, pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장하는 방식이다. (메모리 누수 때문에 실무에서는 사용 불가)

pre[i]는 이전 원소의 인덱스, nxt[i]는 다음 원소의 인덱스이다. pre나 nxt의 값이 -1이면 비어있는 것이다. 

insert함수

1)idea

1. 새로운 원소를 생성

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

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

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

5. unused 1 증가

2)code

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

erase함수

1)idea

1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경

2. 다음 위치의 pre를 삭제할 위치의 pre로 변경

2)code

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