Back to Blog
알고리즘연결리스트자료구조STL list

0x04. 연결 리스트 - 노드 기반 자료구조

연결 리스트의 정의와 성질, 배열과의 비교, Insert/Erase 구현, STL list 사용법을 정리한다.

0x04 연결 리스트

0x00 정의와 성질

정의

연결 리스트 : 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조 ( 원소들은 이곳저곳에 흩어져있다 )

성질

  1. k번째 원소를 확인 / 변경하기 위해 **O(k)**가 필요함 ( 배열과 다르게 원소들이 연속해서 위치하고 있지 않아서 )
  2. 임의의 위치에 원소를 추가 / 제거는 O(1) → 연결 리스트의 큰 장점!!
  3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만, 할당이 다소 쉬움

연결 리스트의 종류

  1. 단일 연결 리스트 ( Singly Linked List )
단일 연결 리스트
  1. 이중 연결 리스트 ( Doubly Linked List )
이중 연결 리스트
  1. 원형 연결 리스트 ( Circular Linked List )
원형 연결 리스트

배열 vs 연결 리스트

원소들 사이의 선후 관계가 일대일로 정의, 따라서 배열과 연결 리스트는 선형 자료구조라고 부른다. ( 나중에 배울 트리, 그래프, 해쉬 등은 비선형 자료구조의 예시 )

배열 vs 연결 리스트

연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 한다.

그래서 32비트 컴퓨터면 주소값이 32비트(4바이트) 단위이니 4N 바이트가 추가로 필요하고, 64비트 컴퓨터라면 주소값이 64비트(8바이트) 단위이니 8N 바이트가 추가로 필요하게 된다.

즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.

0x01 기능과 구현

기능

임의의 위치에 있는 원소를 확인 / 변경 = O(N) 임의의 위치에 원소를 추가 / 제거 = O(1) → 임의의 위치에서 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결 리스트의 사용을 고려 ( like 텍스트 에디터 )

구현

Insert 함수

void insert(int addr, int num){
    // 1. 새로운 원소 생성
    dat[unused] = num;

    // 2. 새 원소의 pre값에 삽입할 위치의 주소 대입
    pre[unused] = addr;

    // 3. 새 원소의 nxt값에 삽입할 위치의 nxt값을 대입
    nxt[unused] = nxt[addr];

    // 4. 삽입할 위치의 nxt값과 삽입할 위치의 다음 원소의 pre값을 새 원소로 변경
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;

    // 5. unused 증가
    unused++;
}

Erase 함수

void erase(int addr){
    // 1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경
    nxt[pre[addr]] = nxt[addr];

    // 2. 다음 위치의 pre를 삭제할 위치의 pre로 변경
    if(nxt[ addr] != -1) pre[nxt[addr]] = pre[addr];
}

0x02 STL list

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

int main(void) {
    list<int> L = {1,2}; // 1 2

    // cpp11이상 부터는 auto t = L.begin() 가능
    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를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
    t= L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                    // 10 6 1 5, t가 가리키는 값은 5
    cout << *t << '\n'; // 5

    // traverse cpp11이상
    for(auto i : L) cout << i << ' ';
    cout << '\n';

    // traverse cpp11미만
    for(list<int>::iterator it = L.begin(); it != L.end(); it++)
      cout << *it << ' ';
}

→ erase는 제거한 다음 원소의 위치를 반환

0x03 연습문제

BOJ 1406 : 에디터 ( 한 줄로 된 간단한 에디터 구현 )

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    list<char> L;
    string s;

    cin >> s;
    for(auto c : s) L.push_back(c);
    auto cursor = L.end();

    int n;
    cin >> n;
    while(n--) {
        char buffer;
        cin >> buffer;
        if(buffer == 'L' && cursor != L.begin()) cursor--;
        else if(buffer == 'D' && cursor != L.end()) cursor++;
        else if(buffer == 'P') {
            char dat;
            cin >> dat;
            L.insert(cursor, dat);
        } else if(buffer == 'B' && cursor != L.begin()) {
            cursor--;
            cursor = L.erase(cursor);
        }
    }

    for(auto i : L) cout << i;
    cout << "\n";
}
// Array linked list
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(pre, pre+MX, -1);
    fill(nxt, nxt+MX, -1);

    string s;
    int cursor = 0;

    cin >> s;
    for(auto c : s) {
        insert(cursor, c);
        cursor++;
    }

    int n;
    cin >> n;
    while(n--) {
        char buffer;
        cin >> buffer;
        if(buffer == 'L' && pre[cursor] != -1) cursor = pre[cursor];
        else if(buffer == 'D' && nxt[cursor] != -1) cursor = nxt[cursor];
        else if(buffer == 'B' && pre[cursor] != -1) {
            erase(cursor);
            cursor = pre[cursor];
        }
        else if(buffer == 'P') {
            char dat;
            cin >> dat;
            insert(cursor, dat);
            cursor = nxt[cursor];
        }
    }

    traverse();
}

손코딩 문제 1

문제 : 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 떄 해당 List의 길이를 효율적으로 구하는 방법?

정답 : 동일한 노드가 나올 때 까지 계속 다음 노드로 가면 된다, 공간복잡도 O(1), 시간복잡도 O(N)

손코딩 문제 2

문제 : 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법

정답 : 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구한 다음, 그 후 다시 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날 때 까지 두 시작점을 동시에 한칸 씩 전진. 공간복잡도 O(1), 시간복잡도 O(A+B)

손코딩 문제 3

문제 : 주어진 연결 리스트 안에 사이클이 있는지 판단

정답 : Floyd's cycle-finding algorithm, 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발 시키면 사이클이 있을 경우 두 커서는 반드시 만나게 된다. 공간복잡도 O(1), 시간복잡도 O(N)

문제 풀이

이번 강의에 해당하는 문제는 총 2개였다. 하나는 연습문제와 비슷한 문제였고 나머지 하나는 Circular Linked List를 활용해서 푸는 요세푸스 문제였다.

Note_ 5397번 : 연습문제와 비슷한 유형의 문제였으나 insert 후에 cursor를 ++해주는 실수를 해서 자꾸 에러가 났던 문제 ,,

14158번 : 또 다른 유형을 마주했다. 문제를 읽고 Circular Linked List 문제라는 것을 알았으나 STL list로 풀다가 실패하였고 야매 리스트로 다시 시도해서 맞출 수 있었다.

리뷰

Linked list는 작년 자료구조 시간에 충분히 배우고 연습을 했다고 생각했는데 시간이 지난 후에 마주하니 또 낯설고 어려웠다.

다시 한번 리마인드할 수 있었던 기회라고 생각한다.

연습문제에서 손코딩 2, 3번은 정말 생각이 나지 않아 나에게 실망하였지만 이게 또 원동력이 될것이라 생각한다.

강의를 본 후에 바로 문제를 풀지 못하고 다음 날에 풀어보니 또 다른 느낌이다.

역시 강의를 본 후에 바로바로 문제를 풀면서 복습하는 것이 중요한 것 같다.

다음은 0x05강 스택으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편