網頁

▼

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)     │
         │                     │
         └─────────────────────┘



    沒有留言:

    張貼留言