iT邦幫忙

2

【小馬的資結演算法秘笈】(4) linked list 與 array比較

今天要介紹一種新的資料結構- linked list,
在介紹這種資料結構之前呢,
我們要先了解array

array有什麼缺點?

array可以用來記錄一連串相同型別的資料,
例如說c++語言寫int array[4]={1,5,8,3};
指的就是連續存放4個整數的array,如圖:

https://ithelp.ithome.com.tw/upload/images/20200321/20117114e8vBG57QgC.png

那麼假設我們原本有一個長度為n的array,
我們想要在第1個位置插入一個元素,
那麼我們就必須把後面的元素都往後移動一格,
大概要O(n)的時間,相當耗時

https://ithelp.ithome.com.tw/upload/images/20200321/20117114CWDsQW5epu.png

刪除元素也需要O(n)的時間

https://ithelp.ithome.com.tw/upload/images/20200321/20117114OTZ34TdTWn.png

array在刪除/新增元素至中間時,
需要搬移整個陣列的元素,相當耗時

新朋友: linked list

那有沒有辦法讓資料隨便擺,我們仍然可以知道順序呢?(這樣就不必把資料搬來搬去)
答案是「記錄下一個資料的位置」

有點像是在玩尋寶遊戲的感覺,
假設有個人收集了小熊、小馬、小狗、小貓四種玩偶,

  • 小熊玩偶放在廚房
  • 小馬玩偶放在臥室
  • 小狗玩偶放在電視機上面
  • 小貓玩偶放在獎杯櫃

那麼他只要記得小熊玩偶放在廚房就好,
然後在小熊玩偶上面貼張紙條,寫說下一個玩偶放在臥室
到了臥室,找到小馬玩偶,上面再貼個紙條寫下一個玩偶電視機上面
這樣就可以知道所有的玩偶放哪裡了

概念上,大概長的像這樣:
https://ithelp.ithome.com.tw/upload/images/20200321/20117114aevTEQdBx4.png

我們用指標去記錄下一筆資料的位置在哪裡
(若你不知道指標可參考c/c++語言: 超好懂的指標(pointer)與參考(reference),歡迎初學者)

新增一個元素?

https://ithelp.ithome.com.tw/upload/images/20200321/201171142WTVYeKCG4.png

刪除一個元素?

https://ithelp.ithome.com.tw/upload/images/20200321/20117114MNKxWvnHS8.png

我們可以看到,不論是新增或刪除一個元素,
只要改變前後記錄的位置就好,
不必大幅搬動資料

比較array和linked list的優缺點

array:

  • 優: 可以快速存取特定位置的資料(用索引即可快速找到該位置)、省記憶體空間(因為linked list要額外用指標存「下一個位置」的資訊)
  • 缺: 在中間新增/刪除資料很麻煩

linked list:

  • 優: 新增/刪除資料較Array簡單
  • 缺: 尋找特定位置的資料較array慢,必須從頭找起、需要額外的記憶體空間儲存指標

適用linked list的時機: 「需要頻繁地新增/刪除資料時」、「不需要快速查詢資料」

linked list的程式碼實作範例

我們創建兩個class,ListNodeLinkedList
ListNode是一筆資料,包括內容本身及指向下一個ListNode的位置

class ListNode{
public:
    ListNode():data(0),next(0){};
    ListNode(int a):data(a),next(0){};
    int data;
    ListNode *next;
};

把許多ListNode串起來即是LinkedList
我們希望實作可以在LinkedList中插入或刪除元素的函數

class LinkedList{
public:
    LinkedList():head(0){};
    ListNode *head;            // list的第一個node
    void printList();           // 印出list的所有資料,用來除錯
    void insertTail(int data); //在list尾巴插入元素
    void insert(int data, int position);   //在特定位置後插入元素
    void Delete(int position);  // 刪除特定位置的元素
};

這邊有個小細節,delete是c++關鍵字,不可當做變數名稱,
故用大寫的Delete

首先實作printList,可以把整個LinkedList的內容印出來,
以方便我們除錯
printList的邏輯很簡單,就是若指標非空就把內容印出來,
然後再去找下一個node的位置

void LinkedList::printList(){
    ListNode *node = head;
    while (node) {
        cout << node->data;
        node = node->next;
        if (node) {
            cout << " ";
        }
    }
    cout << endl;
}

在list尾巴插入元素

如果head為空,直接head=node;
否則跑迴圈先找到尾巴節點,在尾端接上新的node

void LinkedList::insertTail(int data){
    ListNode *node = new ListNode(data);
    if(!head){
        head=node;
    }
    else{
        ListNode *tail = head;
        while(tail->next){
            tail=tail->next;   
        }
        tail->next=node;
    }
}

特定位置後插入元素

void LinkedList::insert(int data, int position){
    ListNode *node = new ListNode(data); //欲插入的元素
    ListNode *prev = head;
    for(int i=0; i<position-1; i++){
        prev=prev->next;
    }
    node->next=prev->next;
    prev->next=node;
}

特定位置刪除元素

void LinkedList::Delete(int position){
    if(position==0){
        head = head->next; //處理要刪除位置就是head的情況
    }
    ListNode *prev = head;
    for(int i=0; i<position-1; i++){
        prev=prev->next;
    }
    ListNode *node = prev->next;
    prev->next=node->next;
    node->next=NULL;    
}

完整程式碼範例

#include <iostream>
using namespace std;

class ListNode{
public:
    ListNode():data(0),next(0){};
    ListNode(int a):data(a),next(0){};
    int data;
    ListNode *next;
};

class LinkedList{
public:
    LinkedList():head(0){};
    ListNode *head;            // list的第一個node
    void printList();           // 印出list的所有資料,用來除錯
    void insertTail(int data); //在list尾巴插入元素
    void insert(int data, int position);   //在特定位置後插入元素
    void Delete(int position);         // 刪除特定位置的元素
};

void LinkedList::printList(){
    ListNode *node = head;
    while (node) {
        cout << node->data;
        node = node->next;
        if (node) {
            cout << " ";
        }
    }
    cout << endl;
}

void LinkedList::insertTail(int data){
    ListNode *node = new ListNode(data);
    if(!head){
        head=node;
    }
    else{
        ListNode *tail = head;
        while(tail->next){
            tail=tail->next;   
        }
        tail->next=node;
    }
}

void LinkedList::insert(int data, int position){
    ListNode *node = new ListNode(data); //欲插入的元素
    ListNode *prev = head;
    for(int i=0; i<position-1; i++){
        prev=prev->next;
    }
    node->next=prev->next;
    prev->next=node;
}

void LinkedList::Delete(int position){
    if(position==0){
        head = head->next; //處理要刪除位置就是head的情況
    }
    ListNode *prev = head;
    for(int i=0; i<position-1; i++){
        prev=prev->next;
    }
    ListNode *node = prev->next;
    prev->next=node->next;
    node->next=NULL;    
}

int main()
{
    //測試LinkedList的程式碼
    LinkedList L;
    L.insertTail(20);
    L.insertTail(35);
    L.insertTail(-7);
    L.insertTail(9);
    L.printList();
    L.insert(88,0);
    L.printList();
    L.Delete(2);
    L.printList();
    return 0;
}

尚未有邦友留言

立即登入留言