###### tags: `資料結構 & 演算法`
{%hackmd @kk6333/theme-sty1 %}
# DS3 - Linked List

## 觀念

Linked List 是一種使用 Node (節點) 組合而成的資料結構，可以方便動態配置儲存資料
其主要包含三個部分

> - head : 指向 Linked List 開頭的指標
> - node : 儲存資料的區域
> - tail : Linked List 的尾巴，通常指向 NULL

Linked List 在 C++ 中通常使用 pointer (指標) 來做實踐
架構如下圖

:::warning


每個 node 通常會有儲存資料的地方 ( 變數 )，以及一個指向下一個 node 的指標 "next"

:::

為了方便操作 Linkded List
通常還會設置幾個基本功能
> - 新增 node
> - 刪除 node
> - 插入 node
> - 印出 node
> - 排序 List.....

有了這些功能就可以很方便對 Linked List 做更動了

<br>

## Linked List 實踐

### 1.Node 定義

struct Node{
    // 儲存的 Data
    int id;
    string name;
    
    // 指向下一個 Node
    Node * next;    
}

Node * node = new Node();

或使用類別

// myClass.h
class Node{
public:
    int id;
    Node * next;
    Node( int num );    // 建構函數
};

Node * node = new Node(666);

<br>

### 2. Linked List 定義
這邊使用 Class 來製作 Linked List，當然如果你只想用函數也可以啦~
除了 Node，還有一些簡單的 function 可以操作 List，然後 Node 使用上方定義的類別

// myClass.h
class List{

private:
    Node * head;    // head
    Node * tail;    // tail
    int len;        // 長度

public:
    List();
    void AddNode( int num );    // 新增 Node
    void Show();                // 顯示 Node 資料
    int GetLength();            // 取得長度
};

<br>

### 3. List 中 Node 的相接 ( 以新增 node 為例 )
要如何將 node 串成 Linked List呢 ? 這邊用增加 node 的函數說明

**Step:**
> 1. 在最後一個 node 的 next 新增 node 指標物件 ( head or tail )
> 2. 設定 data & next
> 3. 改變 tail 指標 ( optional )

// myClass.cpp
void List::AddNode( int num ){
    if( len == 0 ){
        len++;
        head = new Node(num);       // 新增 node
        tail = head;
    }
    else{
        len++;
        tail->next = new Node(num); // 新增 node
        tail = tail->next;          // 變更 tail 資訊
        tail->next = NULL;
    }
}

如果要做像是 insert、delete node 那還會需要考慮 node 前後的連結

<br>

## Linked List 的變形

#### - Circular Linked List ( 環狀 ) :
> **作法** : 最後一個 node 接回第一個
> **用途** : 方便取用最後一個 node

#### - Dummy Head Node :
> **作法** : 在 head 與第一個 node 間新增一個沒用的 node
> **優點** : 在刪除 or 新增 node 時，不用再考慮 head 直接指向的第一個 node 的問題

#### - Doubly Linked List ( 雙向 ) :
> **作法** : 除了 next 指向下一個 node，再多一個 precede 指向前一個 node
> **優點** : 可以雙向取用 node 資料，第一個 node precede 會指向最後一個
> **缺點** : 做其他操作時會需要多考慮 precede 指標的處理