Skip to content

List

陣列如果要從中間插入一個元素，需要將其後面所有元素搬移一格，需耗費 ，連結串列（ linklist ）能只花 完成插入。

1
2
3
4
5
struct Node
{
    int v;
    Node *next = nullptr, *prev = nullptr;
};

可以利用陣列取代指標來實作 linklist 。 C++ 提供 list 函式庫實作雙向串列。

  • 標頭檔： <list>
  • 建構式： list <T> L
  • L.size() ：回傳元素個數，複雜度
  • L.empty() ：回傳是否為空，複雜度
  • L.push_front(T a),L.push_back(T a) ：插入頂端/尾端元素，複雜度
  • L.pop_front(),L.pop_back() ：刪除頂端/尾端元素，複雜度
  • L.insert(iterator it,size_type n,T a) ：在 it 指的那項的前面插入 n 個 a 並回傳指向 a 的迭代器。複雜度 。
  • L.erase(iterator first,iterator last) ：把 指到的東西全部刪掉，回傳 last。複雜度與砍掉的數量呈線性關係，如果沒有指定 last, 那會自動視為只刪除 first 那項。
  • L.splice(iterator it,list &x,iterator first,iterator last) ：first 和 last 是 x 的迭代器。此函式會把 指到的東西從 x 中剪下並加到 it 所指的那項的前面。x 會因為這項函式而改變。若未指定 last, 那只會將 first 所指的東西移到 it 前方。複雜度與轉移個數呈線性關係。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// adapt from cppreference
#include <iostream>
#include <list>

int main()
{
    std::list<char> letters{'o', 'm', 'g', 'w', 't', 'f'};

    if (!letters.empty())
    {
        cout << letters.front() << '\n';
        cout << letters.back() << '\n';
    }
}

/*
o
f
*/
  • 最近更新:
  • 本文貢獻者: allem40306,