連結串列( Linked List )

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *next;
};

int main()
{
    Node *head,*tail,*ptr;

    head = new Node;
    head->data=20;
    tail = head;

    //cout<<tail->data<<endl;
    //cout<<head->data<<endl;

    ptr = new Node;
    ptr->data = 30;
    tail->next = ptr;
    tail = ptr;

    cout<<tail->data<<endl;

}

課程要點：從頭到尾帶學生完成一個可以新增刪除插入反轉的linked list

我這裡有一批上好的互動教材，不看看嗎？

Linked List 視覺化 https://visualgo.net/en/list

Linked List實作Queue https://www.cs.usfca.edu/~galles/visualization/QueueLL.html

Linked List實作Stack https://www.cs.usfca.edu/~galles/visualization/StackLL.html

Linked List 示意圖↓

Linked List V.S. Array

速度：

Array 抓資料速度快，只要給索引(index)就可以抓到想要的資料像是a[4]代表從a陣列中抓第4個值(從0開始)，而Linked List則必須從頭開始往後找。

空間方面(記憶體配置)：

Array 空間固定不易分配，分配太少怕不夠分配太多怕浪費，Linked List動態分配，加資料就重新分配一個空間出來放，資料不要了就釋放掉

過去記憶體容量小為了避免浪費，用Linked List可以節省空間，但現在記憶體容量越來越大也就比較不怕浪費了，而且STL也提供很多好用的function讓我們使用，也同樣像Linked List一樣可以有善管理空間，不過依然是資料結構必學的一個學問。

1.先建立一個Node吧！

建立linked list

head = tail = new Node;
head ->next=NULL;
head ->data=value;

試試看把Node加入建構子(Constructor)

#include<iostream>
using namespace std;

struct Node
{
    int data;
    Node * next;
    Node(int num){ //建構子 Constructor
        data=num;
    }
};

int main(){

    Node *a=new Node(2); //直接在宣告Node的時候給予data的值
    cout<<a->data; //輸出2
    return 0;
}

2.在尾巴加上新的Node

一個一個將Node給建立出來，看著教學影片，慢慢了解↓

How to Create a Linked List C++ Introduction to Linked Lists

在尾巴加上新的Node

ptr = new Node;   //創立一個全新的Node
ptr ->data=value; //並給予新Node值
ptr ->next=NULL;  //新Node要接在最後面，所以Node的next會是NULL
tail ->next=ptr;  //把尾巴接到新Node
tail = ptr;       //新Node成為了tail

3.列出每個Node的Data，並輸出Linked list長度

ptr = head;                    //從頭開始
while (ptr != NULL) {          //還沒到底的話
    cout << ptr ->data << " "; //輸出當前Node的資料
    ptr = ptr ->next;          //往下一個Node移動
}

4.搜尋Node

跟列出所有Node的程式碼很像，只是在每個Node都要判斷data等不等於key

cin >> key; // 要找的數字

ptr = head;
while (ptr != NULL)
{
    if (ptr ->data == key)
    {
        found = true;
        break;
    }
    ptr = ptr ->next;
}

if (found)
    cout << key << "is found" << endl;
else
    cout << key << "is not found" << endl;

5.刪除最後一個Node

if (head == tail) { //只剩一個Node，就直接刪掉自己
    ptr = head;
    head = NULL;
    delete ptr;
    cout << "清空linked list" << endl;
}
else{ //有兩個以上的Node

    ptr = head;
    while (ptr ->next != tail) {
        ptr = ptr ->next;
    }

    ptr ->next=NULL;
    delete tail;
    tail = ptr;

}

5-1. 在Head前插入Node


ptr = new Node;   //創立一個全新的Node
ptr->next=head;
head=ptr;

5-2. 刪除Head


ptr=head;
head=head->next;
delete ptr;

10.linked-list