[알고리즘/C++] 연결 리스트

- 연결 리스트 : 각 데이터를 포인터를 이용해 다음 자료를 가리키도록 연결해둔 형태의 자료구조

	배열	연결 리스트
임의 원소 탐색	O(1)	O(n)
임의 위치에 추가/제거	O(n)	O(1) (위치 주소를 아는 경우) O(n) (위치 주소를 모르는 경우)
메모리 배치	연속	불연속
Cache hit rate	높음	낮음

- 연결 리스트의 종류
  - 단일 연결 리스트 : 각 원소가 다음 원소를 가리킴
  - 이중 연결 리스트 : 각 원소가 이전/다음 원소를 가리킴 (STL의 list 자료형이 이중 연결 리스트)
  - 원형 연결 리스트 : 끝 원소가 다음 원소로 처음 원소를 가리킴

- 연결 리스트의 구현

//구조체를 이용한 구현
struct node{
	struct node *prev, *next;
    int data;
}

- 배열을 이용한 연결리스트의 구현

//배열을 이용한 연결리스트 구현
#include <algorithm>
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX]; //dat : 데이터, pre/nxt : 이전/다음 원소 위치
int unused = 1; // 사용되지 않은 원소 인덱스
fill(pre, pre + MX, -1);
fill(nxt, nxt + MX, -1);

//모든 원소 순회
void traverse(){
	int cur = nxt[0];
    while(cur != -1){
    	cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
}

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

void erase(int addr){
	nxt[pre[addr]] = nxt[addr];
    pre[nxt[addr]] = pre[addr];
}

  - 메모리 문제가 있어 실제로는 쓰기 그렇고, 코테에서만 사용할 것

- STL list를 사용한 구현

#include <list>
int main(void){
  list<int> L = {1, 2};
  list<int>::iterator t = L.begin(); // list 원소를 가리키는 변수
  L.push_front(10); // 앞에 데이터 추가 O(1)
  L.push_back(10); // 뒤에 데이터 추가 O(1)
  L.insert(t, 6); // t가 가리키는 곳 앞에 6 삽입
  t = L.erase(t); // t가 가리키는 곳을 지우고, 다음 주소를 반환
  
  //연결리스트 순회
 	for(t = L.begin();t != L.end() ; t++){
		cout << *t;
	}
    
  // C++11 이상
   for(auto i : L) cout << i;
}