Single linked list using C++

linked list (鏈結串列)

為Node所構成之集合

優點:

1.Node之間允許memory不連續配置

2.不同Node間可存放型態不同的資料

3.插入刪除元素容易

缺點:

多了point的空間

只能夠循序存取

========================================================================

Array在宣告時一定要給予大小，

雖然說可動態的宣告Array，但是也會在執行時要求其大小，很容易造成空間的浪費，

而鏈結串列相較之下不會有此問題，根據不同的情況常見的鏈結串列有:

Single linked list、Circular linked list、Double linked list ， 本篇是實作基本的 Single linked list，

其功能包含 循序加入資料、插入任意資料、刪除任意資料、查看所有資料。

而一個 Single linked list 大致上可用圖解畫成這樣:

而節點的宣告方式大致上如下圖所示，隨著需求不同而不同

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

插入節點可表示圖解為:

刪除節點可表示圖解為:

以下是Single linked list利用C++所實作的簡易程式碼

///SLL.h///

#ifndef SLL_H
#define SLL_H
#include <iostream>

class SLL{
private:
    struct DataNode *head;
    struct DataNode *current;
    struct DataNode *previous;
    struct DataNode *ptr;
    struct DataNode *clear;
    char DeleteData;
    char InsertData;
public:
    SLL();
    ~SLL();
    void Add();
    void Insert();
    void List();
    void Delete();
};

#endif

///SLL.cpp///

#include "SLL.h"
using namespace std;

struct DataNode{
    char CharData;
    struct DataNode *next;
};

SLL::SLL(){
    head=new DataNode;
    current=new DataNode;
    previous=new DataNode;
    head->next=NULL;
    current->next=NULL;
}

SLL::~SLL(){
    if(head->next==NULL){
        delete head;
        delete current;
        delete previous;
    }else{
        current=head;
        while(current!=NULL){
            clear=current;
            current=current->next;
            delete clear;
        }
        delete current;
        delete previous;
        cout<<"已經清除記憶體..."<<endl;
        system("Pause");
    }
}

void SLL::Add(){
    ptr=new DataNode;
    cout<<"請輸入資料"<<endl;
    cin>>ptr->CharData;
    if(head->next==NULL){
        head->next=ptr;
        ptr->next=NULL;
    }else{
        ptr->next=head->next;
        head->next=ptr;
    }
}

void SLL::Insert(){
    if(head->next==NULL){
        cout<<"linklist為空，無法插入"<<endl;
    }else{
        ptr=new DataNode;
        cout<<"請輸入資料"<<endl;
        cin>>ptr->CharData;
        List();
        cout<<"想在哪筆資料後插入資料?:"<<endl;
        cin>>InsertData;
        current=head->next;
        while(current!=NULL){
            if(current->CharData==InsertData){
                previous->next=ptr;
                ptr->next=current;
                break;
            }
            current=current->next;
            previous=previous->next;
        }
        List();
    }
}

void SLL::List(){
    if(head->next==NULL){
        cout<<"linklist為空"<<endl;
    }else{
        previous=head;
        current=head->next;
        cout<<"目前資料為:"<<endl;
        while(current!=NULL){
            cout<<current->CharData<<"->";
            current=current->next;
        }
        cout<<"null"<<endl;
    }
}

void SLL::Delete(){
    if(head->next==NULL){
        cout<<"linklist為空"<<endl;
    }else{
        List();
        cout<<"請輸入欲刪除資料:"<<endl;
        cin>>DeleteData;
        current=head->next;
        while(current!=NULL){
            if(current->CharData==DeleteData){
                previous->next=current->next;
                current->next=NULL;
                clear=current;
                delete clear;
                current=previous->next;
            }else{
                current=current->next;
                previous=previous->next;
            }
        }
    }
}

///main///

#include <iostream>
#include "SLL.h"
using namespace std;

int main()
{
    char option;
    SLL sll;
    while(1){
        cout<<"======"<<endl;
        cout<<"1.依序新增資料"<<endl;
        cout<<"2.在某筆資料前插入資料"<<endl;
        cout<<"3.刪除"<<endl;
        cout<<"4.顯示"<<endl;
        cout<<"5.結束"<<endl;
        while(cin.get(option)&&option=='\n');
        switch(option){
            case '1':sll.Add();
                break;
            case '2':sll.Insert();
                break;
            case '3':sll.Delete();
                break;
            case '4':sll.List();
                break;
            case '5':cout<<"程式結束"<<endl;
                return 0;
        }
    }
}

結論:

Single linked list 雖然新增予刪除節點方便O(1)，而也比Array省空間，

但是因為沒有索引值而導致要歷經每個節點才可找到特定值，n筆資料的話則 花費O(n)

也需花費儲存指標的記憶體，不過在某些情況下非常方便，可動態的加入刪除資料!!

By   Victor