[C++] 연결리스트 (feat.바킹독)

연결 리스트의 정의

연결 리스트란, 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.

 

연결 리스트의 성질

• k 번째 원소를 확인/변경하기 위해 O(k)가 필요 (배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문)
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) ⭐️
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

 

연결 리스트의 종류

• 단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트
• 이중 연결 리스트: 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘다 들고 있다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데,  이중 연결 리스트에서는 알 수 있다. 다만, 원소가 가지고 있어야하는 정보가 1개 더 추가되어 메모리가 더 쓰인다는 단점이 있다. ( STL list는 이중 연결 리스트이다.) 
• 원형 연결 리스트: 끝과 처음이 연결되어 있다. 

 

배열 vs 연결 리스트

둘다 선형 자료구조이다. (트리, 그래프, 해쉬 등은 비선형 자료구조)
구술 면접에서 배열과 리스트를 비교하는 문제가 자주 출제되니 둘의 차이에 대해서 정확하게 알아두자!

 

야매 연결 리스트 구현

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void insert(int addr, int num){
    dat[unused]=num; //새로운 원소 생성
    pre[unused]=addr; //새 원소의 pre 값에 삽입할 위치의 주소를 대입
    nxt[unused]=nxt[addr]; //새 원소의 nxt 값에 삽입할 위치의 nxt값을 대입
    //삽입할 위치의 nxt값이 -1이 아니라면, 삽입할 위치의 다음 원소의 pre값을 새 원소의 주소로 변경
    if(nxt[addr] != -1) pre[nxt[addr]]=unused; 
    //삽입할 위치의 nxt값을 새원소의 주소값으로 변경
    nxt[addr]=unused;
    
    unused++;
}

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

 

STL list 사용 예시

• STL list에서 push_back, pop_back, push_front, pop_front는 모두 O(1)
• iterator가 주소 역할(auto t = L.begin())
• erase는 제거한 다음 원소의 위치를 반환
• L.begin()은 제일 앞에 있는 원소를 가리키지만 L.end()는 제일 뒤에 있는 원소의 한 칸 뒤를 가리킨다

 

예시 문제

BOJ 1406번 : 에디터

 BOJ 1406번: 에디터 문제 참고

풀이 (더보기를 클릭해주세요👇🏻👇🏻👇🏻)

#include <iostream>
#include <list>
using namespace std;

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

    list<char> L;

    string w;
    cin >>w;

    for(auto c: w){
        L.push_back(c);
    }
    auto t = L.end();//커서

    int m;
    cin >> m;
    
    for(int i=0; i<m; i++){
        char b;
        cin >>b;
        if(b=='P'){
            char c;
            cin >> c;
            L.insert(t,c);
        }
        else if(b=='L'){
            if(t!= L.begin()){
                t--;
            }
        }
        else if(b=='D'){
            if(t!=L.end()){
                t++;
            }
        }
        else if(b=='B'){
            if(t != L.begin()){
                t--;
                t = L.erase(t);
            }
        }
    }

    for(auto i : L) cout <<i;
    cout<<'\n';

    return 0;

}

명령과 글자가 다 char 1글자여서 char 자료형에 cin을 받도록 했고, 이렇게 하면 알아서 공백과 줄바꿈은 무시한다.

런타임에러가 뜰 수 있는데, 이는 이미 cursor가 가리키는 곳이 이미 지워졌는데 그 곳에 insert를 시킨다거나, cursor가 L.begin()인데 cursor--;를 시킨다거나 하는 이유일 수 있다.

 

BOJ 5397번 : 키로거

 BOJ 5397번: 키로거 문제 참고

풀이 (더보기를 클릭해주세요👇🏻👇🏻👇🏻)

#include <iostream>
#include <list>
using namespace std;

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

    int tc;
    cin >>tc;

    for(int i=0; i<tc; i++){
        list<char> R; 

        string w;
        cin >>w;

        auto t = R.begin(); //커서

        for(auto c : w){
            if(c=='<' && t!=R.begin()){
                t--;
            }
            else if(c=='>' && t!=R.end()){
                t++;
            }
            else if(int(c)>47 && int(c)<58){//숫자일때
                R.insert(t, c);
            }
            else if(int(c)>64 && int(c)<91){//대문자일때
                R.insert(t, c);
            }
            else if(int(c)>96 && int(c)<123){//소문자일때
                R.insert(t, c);
            }
            else if(c=='-' && t!=R.begin()){//백스페이스일때
                t--;
                t = R.erase(t);
            }
        }
        
        for(auto i : R) cout <<i;
        cout<<'\n';
    }

    return 0;
}

 

BOJ 1158번 : 요세푸스 문제

 BOJ 1158번: 요세푸스 문제 참고

풀이 (더보기를 클릭해주세요👇🏻👇🏻👇🏻)

ing

 

<틈새>손코딩 문제!!

문제1 : 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법은? (정답은 더보기 클릭!) 

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

 

문제2 : 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법은? (정답은 더보기 클릭!)

정답 : 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함. 그 후 다시 두 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날 때 까지 두 시작점을 동시에 한칸씩 전진시키면 된다.

공간 복잡도 O(1), 시간복잡도 O(A+B) 

=> 지나가면서 스치는 모든 노드를 저장하지 않고, 먼저 둘의 길이 차이를 구한 다음에 더 긴 쪽을 차이만큼 이동시켜 놓으면 이제는 둘을 동시에 한 칸씩 당겼을 때 만나는 지점을 구할 수 있게 된다.

 

문제3 : 주어진 연결 리스트 안에 사이클이 있는지 판단하라 (정답은 더보기 클릭!)

정답 : Floyd's cycle-finding algorithm 이용. 공간복잡도 O(1), 시간복잡도 O(N)

 

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