網頁

2022/7/11

資料結構 單向鏈結串列 singly linked list

資料結構的單向鏈結串列筆記。


單向鏈結串列(Singly linked list)為線性串列資料結構,特點是:

  • 資料是有順序的。
  • 非連續的記憶體空間儲存資料。
  • 每個資料元素除了資料本身還存有下一個資料元素的位址(指標(pointer))即鏈結(linked)。

  • 單向鏈結串列的一個資料元素又稱為節點(node),每個節點由資料欄位(data)及指標欄位(pointer)組成。資料欄位存有資料,指標欄位則存有下個節點的指標。第一個節點的指標稱為head,即為單向鏈結串列的頭,然後透過儲存的指標可以一直往下找到下個結點,此即為單向鏈結串列。

    Singly Linked List

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
    │data│next├───►│data│next├───►│data│null│
    └────┴────┘    └────┴────┘    └────┴────┘
       node1          node2          node3
    


    下面圖示說明單向鏈結串列的操作。

    建立

    建立一個指向第一個節點的head。第一個節點資料及指標欄位為null,即最後一個節點,。

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐
    │null│null│
    └────┴────┘
       node1
    


    插入

    在原本的第2個節點和第3個節點插入一個新結點。新結點的指標指向原本第3個節點,原本第2個節點的指標指向新節點。

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐    ┌────┬────┐              ┌────┬────┐
    │ A  │next├───►│ B  │next├──┐ ──X── ┌──►│ C  │null│
    └────┴────┘    └────┴────┘  │       │   └────┴────┘
       node1          node2     ▼       │      node4
                               ┌────┬───┴┐
                               │ D  │next│ (new node)
                               └────┴────┘
                                  node3
    


    刪除

    把原本的第2個節點刪除。第1個節點的指標改為指向第3個節點

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
    │ A  │next├─X─►│ B  │next├─X─►│ C  │null│
    └────┴───┬┘    └────┴────┘    └────┴────┘
       node1 │        node2        ▲ node2
             │       (deleted)     │
             │                     │
             └─────────────────────┘
    



    沒有留言:

    張貼留言