[C++] 연결 리스트

연결리스트

연결리스트는 배열처럼 순차적으로 메모리가 할당되어있는게 아니라 각 원소가 다음 원소의 주소를 가져 서로 이어지는 형태로 만들어진다.

따라서 다음과 같은 특징들이 생기는데

• k번째 원소를 변경/확인하기 위해서는 O(k)의 시간 필요
• 임의의 위치에 원소를 추가/제거하는 경우는 O(1)의 시간 필요

연결리스트 종류

• 단일 연결 리스트 : 원소가 다음 원소의 주소 가지고 있음
• 이중 연결 리스트: 원소가 다음 원소, 이전 원소의 주소를 가지고 있음, STL List가 이중 연결 리스트
• 원형 연결 리스트: 끝 원소가 처움 원소의 주소를 가지고 있음

배열과 연결리스트 차이

둘다 선형 자료구조이지만 차이점이 있다.

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

 

연결리스트 구현

만약 STL list를 코딩테스트에서 금지한다면 간단하게 이중 연결리스트를 구현할 수 있다.

pre: 현재 index에서의 이전 원소의 index 저장

nxt: 현재 index에서의 다음 원소의 index 저장

 

첫번째(0번 index)는 liist의 시작을 알려주는 노드이므로 데이터 저장을 목적으로 사용되지 않는다.

-1은 데이터가 없다, 다음/이전 원소가 없다는 뜻이다.

const int MAX = 100005;
int dat[MAX], pre[MAX], nxt[MAX];
int unused = 1;

fill(pre, pre+MAX, -1)
fill(nxt, nxt+MAX, -1)

travel 구현

void travel(){
	int cur = nxt[0];
    while(cur != -1){
    	cout << data[cur];
        cur = nxt[cur];
    }
}

insert 구현

void insert(int addr, int data){
    data[unused] = data;
    nxt[unused] = nxt[addr];
    pre[unused] = pre[addr];
    
    nxt[pre[addr]] = unused;
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    unused++;
}

erase 구현

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

STL List

https://cplusplus.com/reference/list/list/

https://cplusplus.com/reference/list/list/