[ 알고리즘 ] 연결리스트, STL list

연결리스트

원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조

 

특징

k 번째 원소를 확인하기 위해 O(k)가 필요하다

임의의 위치에 원소를 추가,제거는 O(1)

 

종류

단일 연결리스트

이중 연결리스트

원형 연결리스트

출처 바킹독

배열 vs 연결리스트

출처 바킹독

 

// 연결리스트에 원소를 넣었다가 뺏다하는 함수

#include <bits/stdc++.h>
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;
    nxt[unused] = nxt[addr];
    if(nxt[addr]!=-1) // 맨 끝에 삽입하는게 아니라면
        pre[nxt[addr]] = unused; // 앞원소의 다음주소를 따라가 그 원소의 전원소를 삽입할 원소의 주소로 채운다.
    nxt[addr] = unused; // 앞원소의 다음원소에 삽입할 원소의 주소를 넣는다.
    unused++;
}

void erase(int addr) {
   
    nxt[pre[addr]] = nxt[addr]; // 삭제할원소의 다음주소 전 원소 다음주소에 넣기 
    if (nxt[addr] != -1) // 만약 위에 원소가 -1이면 (뒤에 원소가 있으면)
        pre[nxt[addr]] = pre[addr]; // 원소의 앞주소를 뒤의 원소의 앞주소로 이동
   
}

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

void insert_test() {
    cout << "****** insert_test *****\n";
    insert(0, 10); // 10(address=1)
    traverse();
    insert(0, 30); // 30(address=2) 10
    traverse();
    insert(2, 40); // 30 40(address=3) 10
    traverse();
    insert(1, 20); // 30 40 10 20(address=4)
    traverse();
    insert(4, 70); // 30 40 10 20 70(address=5)
    traverse();
}

void erase_test() {
    cout << "****** erase_test *****\n";
    erase(1); // 30 40 20 70
    traverse();
    erase(2); // 40 20 70
    traverse();
    erase(4); // 40 70
    traverse();
    erase(5); // 40
    traverse();
}

int main(void) {
    fill(pre, pre + MX, -1);
    fill(nxt, nxt + MX, -1);
    insert_test();
    erase_test();
}

 

STL list

 

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

int main(void) {
  list<int> L = {1,2}; // 1 2
  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
  for(auto i : L) cout << i << ' ';
  cout << '\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}