Linked List: Intro(簡介)

Posted by Chiu CC on 4 17, 2016


先備知識與注意事項

要了解Linked list,一定要先看懂pointer(指標),建議讀者可以先閱讀以下連結內容:

本篇文章介紹的是最基本的Singly linked list,其餘還有Doubly linked listCircular linked list,請參考:


目錄


簡介:Linked list

Linked list(連結串列)是一種常見的資料結構,其使用node(節點)來記錄、表示、儲存資料(data),並利用每個node中的pointer指向下一個node,藉此將多個node串連起來,形成Linked list,並以NULL來代表Linked list的終點,見圖一(a)。

cc

圖一(a)。

cc

圖一(b)。

若實際打開每個node的內部,至少會包含(1)data來代表資料,與(2)pointer指向下一個node,見圖一(b):

  • Node1:
    • int的data,記錄正整數\(7\)
    • 本身的記憶體位置為0x1001042f0
    • 以「node之pointer」,記錄(指向)下一個node之記憶體位置(0x100104300)。
  • Node2:
    • int的data,記錄正整數\(3\)
    • 本身的記憶體位置為0x100104300
      • 由於在Node1中的「node之pointer」指向了Node2之記憶體位置,因此,便能夠經由Node1「找到」Node2。
    • 以「node之pointer」,記錄(指向)下一個node之記憶體位置(0x100104310)。
  • Node3:
    • int的data,記錄正整數\(14\)
    • 本身的記憶體位置為0x100104310
      • 由於在Node2中的「node之pointer」指向了Node3之記憶體位置,因此,便能夠經由Node2「找到」Node3。
    • 以「node之pointer」,記錄(指向)NULL,表示Linked list的最後一個node。

通常在面對一個Linked list時,能夠公開存取(access)的node只有「第一個node」,以ListNode *first表示,不過因為node中有pointer記錄下一個node的記憶體位置,便能夠讀取下一個node的datapointer,換句話說,有了node中的pointer就可以在Linked list中「移動(traversal)」,更進一步,便能進行諸如「新增節點」、「刪除節點」、「印出Linked list」等等的資料處理,這些函式將在後續文章一一介紹。


以兩個class(類別)表示Linked list

若以C++的class(類別)來實作Linked list,可以利用兩個class,使得node的資料不會被任意更動(也就是封裝(Encapsulation)的概念)。
使用struct來代表node也是常見的做法,差別在於,struct的資料成員(data member)一定是公開的(public)

class ListNode的private data有兩項,一項代表著資料項目(在此以int示範),一項是「指向型別(type)為ListNode之指標」,以ListNode *next表示,用來記錄「下一個node」的記憶體位置。

class LinkedList的private data中,最基本一定會有代表「第一個node」的ListNode *first,其餘資料項目可以視情況增加,像是int size用來記錄Linked list的長度等等。

// C++ code
#include <iostream>
class LinkedList;    // 為了將class LinkedList設成class ListNode的friend,
                     // 需要先宣告
class ListNode{
private:
    int data;
    ListNode *next;
public:
    ListNode():data(0),next(0){};
    ListNode(int a):data(a),next(0){};

    friend class LinkedList;
};

class LinkedList{
private:
    // int size;                // size是用來記錄Linked list的長度, 非必要
    ListNode *first;            // list的第一個node
public:
    LinkedList():first(0){};
    void PrintList();           // 印出list的所有資料
    void Push_front(int x);     // 在list的開頭新增node
    void Push_back(int x);      // 在list的尾巴新增node
    void Delete(int x);         // 刪除list中的 int x
    void Clear();               // 把整串list刪除
    void Reverse();             // 將list反轉: 7->3->14 => 14->3->7
};


比較:Array與Linked list

Array(矩陣)也是常見的用來記錄一連串「具有相同形態的資料」的資料結構,以下便列舉Array與Linked list各自的優缺點,以及各自適合的問題情境。


Array

優點

  • random access:只要利用index即可在O(\(1\))時間對Array的資料做存取。
  • 較Linked list為節省記憶體空間:因為Linked list需要多一個pointer來記錄下一個node的記憶體位置。
    • 假設node之data項目為\(1\)byte的char,但是pointer項目卻要\(4\)bytes,這樣的資料結構就多花了4倍的記憶體空間在與真正要處理的資料無關的部分上,是個沒有效率的做法。

缺點

  • 新增/刪除資料很麻煩:若要在第一個位置新增資料,就需要O(\(N\))時間把矩陣中所有元素往後移動。同理,若要刪除第一個位置的資料,也需要O(\(N\))時間把矩陣中剩餘的元素往前移動。
  • 若資料數量時常在改變,要時常調整矩陣的大小,會花費O(\(N\))的時間在搬動資料(把資料從舊的矩陣移動到新的矩陣)。

適用時機

  • 希望能夠快速存取資料。
  • 已知欲處理的資料數量,便能確認矩陣的大小。
  • 要求記憶體空間的使用越少越好。


Linked list

優點

  • 新增/刪除資料較Array簡單,只要對O(\(1\))個node(所有與欲新增/刪除的node有pointer相連的node)調整pointer即可,不需要如同Array般搬動其餘元素。
    • 若是在Linked list的「開頭」新增node,只要O(\(1\))。
    • 若要刪除特定node,或者在特定位置新增node,有可能需要先執行O(\(N\))的「搜尋」。
  • Linked list的資料數量可以是動態的,不像Array會有resize的問題。

缺點

  • 因為Linked list沒有index,若要找到特定node,需要從頭(ListNode *first)開始找起,搜尋的時間複雜度為O(\(N\))。
  • 需要額外的記憶體空間來儲存pointer

適用時機

  • 無法預期資料數量時,使用Linked list就沒有resize的問題。
  • 需要頻繁地新增/刪除資料時。
  • 不需要快速查詢資料。


以上便是Linked list的初步介紹。
接下來的文章將逐一介紹class LinkedList的成員函式(member function)。



參考資料:


Linked List系列文章

Linked List: Intro(簡介)
Linked List: 新增資料、刪除資料、反轉

回到目錄:

目錄:演算法與資料結構