すべての内容は以下の内容を参照して作成されています.

1.定義と性質

定義＃テイギ＃

エレメントを格納するときに、次のエレメントが存在する場所を含むように格納されるデータ構造.

気性

✔k個目の要素をチェック/変更する👉🏻 O(k)

たとえば、3->13->72->5を格納する接続リストがあります.ここで3番目の要素72を見つけるには、3〜13、13〜72を経なければならない.このように行かなければ、72がどこにあるか分からない.配列とは異なり、要素の空間内の位置は連続的ではありません.

要素の追加/削除👉🏻 O(1)

АААААААААААААА

種類

✔勘定科目単点接続リスト

各要素に次の要素のアドレスがある接続リスト.

✔勘定科目の二重接続リスト

各要素には、前の要素と次の要素のアドレスがあります.
しかし、欠点は、要素が持つべき情報を追加したため、より多くのメモリが消費されることです.
(STLにはlistという名前の接続リストがあり、二重接続リストとして構成されていることに注意してください.)

勘定科目の勘定科目のプロトタイプ接続のリスト

端点は最初の端点に関連付けられます.図の例は接続リストとして表示されますが、各要素には前の要素と次の要素のアドレスがあります.

アレイvs接続リスト

✔朕k次元素の接近

배열はO(1)であり、연결 리스트はO(k)である.

АААААААААААА

배열はO(N)であり、연결 리스트はO(1)である.
ただし、厳密には、接続リストにも3番目の要素の後に20という要素を追加したい場合は、まず3番目の要素を見つけてからO(1)に追加する必要があります.状況は少し異なります.これは実装セクションで詳しく説明します.

勘定科目の処理

배열は連続的であり、연결 리스트は不連続である.

✔▼余分なスペース(オーバーヘッド)

배열は、追加のスペースを必要とせずに、データを簡単に格納するだけです.計算をしなければならない場合は、intで長さ情報を格納する必要がありますが、これは小さすぎて、心配する必要はありません.
ただし、연결 리스트において、各要素は、以下の要素のアドレス値を有しなければならない.したがって、32ビットコンピュータの場合、アドレス値は32ビット(=4バイト)単位であるため、追加の4 Nバイトが必要であり、64ビットコンピュータの場合、追加の8 Nバイトが必要である.これは、Nに比例した追加メモリを使用することを意味します.

2.機能と実施

機能

✔朕は任意の位置の要素を検査/変更する👉🏻 O(N)

次に説明するように、配列とは異なる任意の位置の要素に到達するには、最初の位置から開始し、その位置に到達するまで順次アクセスする必要があります.
これは接続リストの構造上は仕方がありません.明らかにすべての要素がメモリのどこかにありますが、最初の要素のアドレスしか知りません.
したがって、k番目の要素を見るにはO(k)の時間が必要であり、要素全体がN個ある場合、平均してN/2の時間が必要であるため、O(N)とみなすことができる.

✔朕は任意の場所で元素を追加/削除する👉🏻 O(1)

追加

たとえば、a->cとaの後ろにbを追加する場合は、後ろのすべての要素を配列のように移動する必要はありません.aとbで次の要素のアドレスを変更するだけです.
(ただし、追加したいアドレスを知っている場合にのみO(1)となる点は間違いありません.コマンドがaアドレスではなくbという要素を3番目の要素の後に追加する場合、3番目の要素を見つけるには追加の時間がかかるため、O(1)とは言えません.

削除

たとえば、a->b->cでbを削除したい場合は、aの次のアドレスをcに変更してbのメモリを解放するだけです.

インプリメンテーション

#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) 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();
}

3. STL list

push_back, pop_back, push_front, pop_front 👉🏻 O(1)
iterator 👉🏻 アドレスロール

#include <iostream>
#include <list>

using namespace std;

int main(void) {
    list<int> L = {1,2};
    list<int>::iterator t = L.begin(); //t는 1을 가리키는중
    //c++11이상이면 auto t = L.begin(); 도 가능
    L.push_front(10); // 10,1,2
    cout << *t << '\n'; // 1
    L.push_back(5); //10,1,2,5
    L.insert(t, 6); //t가 가리키는 곳 앞에 삽입, 10,6,1,2,5
    t++; //t를 1칸 앞으로, t가 가리키는 값은 2
    t = L.erase(t); //t가 가리키는 값 제거, 그다움 원소 5 위치 반환
    cout << *t << '\n'; //5
    for(auto i: L) cout << i << ' '; //10,6,1,5
    cout << '\n';
    for(list<int>::iterator it=L.begin(); it != L.end(); it++)
        cout << *it << ' '; //10,6,1,5
}

4.練習問題

✔️ BOJ 1406号：編集

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

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

    string s;
    list<char> L;
    int M;
    
    cin >> s >> M;
    for(auto e: s) L.push_back(e);
    
    auto cursor = L.end();
    char cmd;
    for(int i = 0; i < M; i++) {
        cin >> cmd;
        switch (cmd)
        {
        case 'L':
            if(cursor != L.begin())
                cursor--;
            break;
        case 'D':
            if(cursor != L.end())
                cursor++;
            break;
        case 'B':
            if(cursor != L.begin()) {
                cursor--;
                cursor = L.erase(cursor);
            }
            break;
        default:
            char ch;
            cin >> ch;
            L.insert(cursor, ch);
            break;
        }
    }

    for(auto e: L) cout << e;
}