바킹독 알고리즘 0x04강 연결 리스트 요약본

1. 배열에 비해서 cache hit rate 가 낮지만, 할당이 쉽다는 장점이 있다!

2. 배열과 연결 리스트의 차이를 잘 알아두자! 둘 다 선형 자료구조~@

연결 리스트에서 추가적으로 필요한 공간은, 다음 요소의 주소를 저장하는 공간을 의미한다.

3. 텍스트 에디터가 연결 리스트를 쓰는 대표적인 경우!

4. 실무에서는 쓸 수 없으나 코테에서는 유리한 야매 연결 리스트!! (메모리 누수 때문에 현업에선 절대 사용 불가) (STL list 가 허용되지 않아 직접 구현해야 하는 경우에만 씀.)

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX]; // dat[i] 는 i 번지(번째 아님 주의) 원소의 값. pre[i] 는 i 번지 원소의 이전 원소의 인덱스
int unused = 1; // 현재 사용되지 않는 인덱스, 새로운 원소가 들어갈 수 있는 인덱스

fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);
// pre 나 nxt 의 값이 -1 이면 해당 원소의 이전, 다음 원소가 존재하지 않는다는 뜻.
//0번지에는 값이 들어 있지 않다. 단지 시작하기 위한 dummy node 이다.

야매 연결 리스트의 순회 함수 (traverse)

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

5. STL list 를 사용할 수 있는 상황이라면,, 위 방법보단 이 방법을 적극 활용하자!

6. 백준에서 문제 풀다가 이슈 발생..

for (auto i : S) cout << i;

와

for (list<char>::iterator it = S.begin(); it != S.end(); it++) {
cout << *it;
}

는 서로 같은 결과를 반환하는데, 백준 채점기는 위에 것만 맞다고 채점한다... 미스테리 그자체..

7. 그리고 List.erase() 메소드의 경우, 인자로 받은 iterator 를 삭제해 버리고, 그 다음값을 리턴한다. 나는 '그 다음값을 리턴한다.' 를 간과하고, 다음값을 저장하지 않은 채로, t++; 로 연산하려고 했는데 그랬더니 segmentation fault 에러가 발생했다. 메모리 공간에 잘못 접근했을 때 나는 에러임을 알고 있어서, 아 내가 어디선가 메모리 접근을 잘못했구나 를 깨닫고, 디버깅했다. 해결은 간단하게, .erase 메소드가 반환하는 결과를 t 에 재대입해주면 되었다. t = List.erase(t) 와 같이!