[바킹독 알고리즘]0x04강 - 연결 리스트

0x00 정의와 성질

연결리스트의 정의

원소들을 저장할때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

 

 

연결리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

Cache hit rate란?

다음에 사이트를 재방문할 때 해당 콘텐츠가 훨씬 빠르게 표시 되도록 웹 사이트의 데이터와 콘텐츠를

임시로 저장하는 고속 메모리.

 

 

 

연결리스트의 종류

• 단일 연결 리스트 : 단일 연결 리스트는 각 원소가 자신의 다음 원소의 주소를 들고 있다

 

• 이중 연결 리스트 : 이중 연결 리스트에서는 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있다. 다만 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점이 있다. 참고로 STL에 연결 리스트가 있는데, 이 컨테이너의 이름은 list이고 구조는 이중 연결 리스트입니다.

 

• 원형 연결 리스트 : 원형 연결 리스트에서는 끝이 처음과 연결되어 있다. 그림의 예시는 단일 연결 리스트로 표현했지만 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관이 없다.

 

 

배열 vs 연결 리스트

 

 

 

 

 

 

 

 

 

0x01 기능과 구현

4번째 원소를 찾아보자

 

연결 리스트에서 제공되는 연산들을 하나씩 살펴보겠다.

첫 번째로 임의의 위치에 있는 원소를 확인/변경하는 연산인데, 계속 언급했듯이 배열과는 다르게 임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때 까지 첫 번째부터 순차적으로 방문을 해야 한다.

 

이건 연결 리스트의 구조 상 어쩔 수 없는건데, 분명 모든 원소들은 메모리 어딘가에 있을테지만, 우리는 그 중에서 첫 번째 원소의 주소만 알고 있다. 그러면 우리가 네 번째 원소의 값을 확인하고 싶다고 할 때, 우리는 첫 번째 원소에 기록된 주소를 보고 두 번째 원소로 넘어가고, 두 번째 원소에 기록된 주소를 보고 세 번째 원소로 넘어가고, 세 번째 원소에 기록된 주소를 보고 네 번째 원소로 넘어가서 드디어 도착했다.

 

그렇기 때문에 k번째 원소를 보기 위해서는 O(k)의 시간이 필요하고, 전체에 N개의 원소가 있다고 하면 평균적으로 N/2의 시간이 걸릴테니 O(N)이라고 생각하면 된다.

 

 

 

추가하고 싶은 위치의 주소를 알고 있을 경우에만 O(1)

 

 

 

제거할 원소의 앞 원소에게 자신의 뒷주소를 넘겨주고 메모리상에서 지우면 된다.

 

 

결론

• 임의의 위치에 있는 원소를 확인/변경 = O(N)
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(1)

 

 

0x02 STL list

 

STL에는 list가 있다. 대부분 코테에서는 STL을 사용할 수 있는 상황이니 연결 리스트를 꾸역꾸역 구현하는 것 보다 그냥 STL을 쓰는게 훨씬 더 편하다.

 

STL list에서 push_back, pop_back, push_front, pop_front는 모두 O(1)이고, 우리가 이전 구현에서 '번지'라는 개념을 사용했듯 여기서는 iterator가 주소 역할을 한다. 03번째 줄에서 list::iterator라는 type을 치기가 귀찮으면 C++11 이상일 때 auto t = L.begin()으로 써도 된다.

 

그리고 erase는 제거한 다음 원소의 위치를 반환합니다. 마지막으로 순회를 할 때에는 C++11 이상이라면 12번째 줄과 같이 편하게 할 수 있지만, C++11 미만이라면 14, 15번째 줄과 같이 아주 불편하다.

 

 

 

 

0x03 연습 문제

BOJ 1406번:에디터

 

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string box;
    cin >> box;
    list<char> L;
    for(auto c : box) L.push_back(c);
    auto cursor = L.end();
    int m;
    cin >> m;
    while(m--){
        char on;
        cin >> on;
        if ( on == 'P'){ 
            char add;
            cin >> add;
            L.insert(cursor, add);
        }
        else if ( on == 'L'){
            if( cursor != L.begin()) cursor--;
        }
        else if ( on == 'D'){
            if( cursor != L.end()) cursor++;
        }
        else{
            if( cursor != L.begin()){
                cursor--;
                cursor = L.erase(cursor);
            }
        } 
    }
    for(auto c : L) cout << c;
}

 

list.insert() 와 list.erase() 사용법을 확인해보자

 

 

 

 

손 코딩 문제

 

 

 

 

 

 

 

 

 

문제 3번은 Floyd's cycle-finding algorithm이라는 이름이 붙어있는 알고리즘으로 해결이 가능한데, 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있을 경우 두 커서는 반드시 만나게 된다. 반대로 만약 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달한다.