Double linked list Using C++

Double linked list (雙向鏈結串列)

結構為:

LLink為指向前一個Node，RLink為指向下一個Node

優點:
任何一個Node可得知前後的Node

較為強固

缺點:
插入需更動4個指標，麻煩

刪除需更動兩個指標，麻煩



Double linked list 的插入如下圖所示:

Double linked list 的刪除如下圖所示:

這邊要注意一下，插入或刪除節點時，會因為節點位置而造成策略不同，如頭端。

下列為使用C++實作 Double linked list 之程式碼，功能有 循序加入節點、加入任意節點、

刪除節點、印出，這次程式碼有加上註解...

///DLL.h///

#ifndef DLL_H
#define DLL_H
#include <iostream>

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

#endif

///DLL.cpp///

#include "DLL.h"
using namespace std;

struct DataNode{
    char CharData;
    struct DataNode *Llink;
    struct DataNode *Rlink;
};

DLL::DLL(){
    head=new DataNode;
    current=new DataNode;
    head->Llink=NULL;
    head->Rlink=NULL;
    current->Llink=NULL;
    current->Rlink=NULL;        //初始化
}

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

void DLL::Add(){
    ptr=new DataNode;
    cout<<"請輸入資料"<<endl;
    cin>>ptr->CharData;
    if(head->Rlink==NULL){    //判斷是否為空，如為空則代表該資料為頭端
        head->Rlink=ptr;
        ptr->Llink=NULL;
        ptr->Rlink=NULL;
    }else{    //不為空則需要更動4根指標
        current=head->Rlink;
        current->Llink=ptr;
        ptr->Rlink=current;
        ptr->Llink=NULL;
        head->Rlink=ptr;
    }
}

void DLL::Insert(){
    if(head->Rlink==NULL){
        cout<<"linklist為空，無法插入"<<endl;
    }else{
        ptr=new DataNode;
        cout<<"請輸入資料"<<endl;
        cin>>ptr->CharData;
        List();
        cout<<"想在哪筆資料的左邊插入資料?:"<<endl;
        cin>>InsertData;
        current=head->Rlink;
        while(current!=NULL){
            if(current->CharData==InsertData){    //判斷該位置是否為我們要插入的資料
                if(current->Llink==NULL){    //插入資料為頭端
                    current->Llink=ptr;
                    ptr->Rlink=current;
                    ptr->Llink=NULL;
                    head->Rlink=ptr;
                    break;
                }else{    //插入資料為其他時，而因是插在某筆資料之前所以不會有尾端之情況
                    (current->Llink)->Rlink=ptr;
                    ptr->Llink=current->Llink;
                    current->Llink=ptr;
                    ptr->Rlink=current;
                    break;
                }
            }else{
                current=current->Rlink;    //前進
            }
        }
    }
}

void DLL::Delete(){
    List();
    cout<<"請輸入欲刪除資料:"<<endl;
    cin>>DeleteData;
    current=head->Rlink;
    while(current!=NULL){
        if(current->CharData==DeleteData){    //先判斷該位置是否是我們需要刪掉的資料
            if(current->Llink==NULL&&current->Rlink==NULL){    //判斷需要刪除資料的位置，因為位置的不同動作也有所不同，此判斷為只剩單一節點
                clear=current;
                current=current->Rlink;
                head->Rlink=NULL;
                clear->Llink=NULL;
                clear->Rlink=NULL;
                delete clear;    
            }else if(current->Llink==NULL){    //刪除資料為頭端
                (current->Rlink)->Llink=NULL;
                clear=current;
                current=current->Rlink;
                head->Rlink=current;
                clear->Llink=NULL;
                clear->Rlink=NULL;
                delete clear;    
            }else if(current->Rlink==NULL){    //刪除資料為尾端
                (current->Llink)->Rlink=NULL;
                clear=current;
                current=current->Rlink;
                clear->Llink=NULL;
                clear->Rlink=NULL;
                delete clear;    
            }else{    //刪除資料為中間節點
                (current->Llink)->Rlink=current->Rlink;
                (current->Rlink)->Llink=current->Llink;
                clear=current;
                current=current->Rlink;
                clear->Llink=NULL;
                clear->Rlink=NULL;
                delete clear;
            }
        }else{
            current=current->Rlink;    //前進
        }
    }
}

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

///main///

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

int main()
{
    char option;
    DLL dll;
    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':dll.Add();
                break;
            case '2':dll.Insert();
                break;
            case '3':dll.Delete();
                break;
            case '4':dll.List();
                break;
            case '5':cout<<"程式結束"<<endl;
                return 0;
        }
    }
}

by Victor