本文已經過時, 最新文章請點擊 : 《【資料結構-重構】連結串列》

循环链表比起单链表增加了最后一个元素的 next 指针域的指向, 那么双向链表就是在循环链表的基础上增加多一个指针域 - previous, 这个指针域指向当前元素之前的那一个元素. 如果当前元素就是 first, 那么这个指针域就会指向最后一个元素

这里用不带 last 指针的 SVG 图表示

上图非常清晰的指明了每一个指针应该指向的位置

在写代码的时候, 没有考虑到直接继承循环链表的类. 但是实际在写的过程中, 除了初始化、清空、摧毁、插入和删除之外, 其他和循环链表的代码其实是基本差不多的

下面给出源代码, 有错误欢迎指出

分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件

DoubleLinkedList.hpp :

#ifndef DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPP
#define DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPP

#include <iostream>
#include <cstdlib>

namespace DoubleLinkList {
    using std::cout;
    using std::cin;
    using std::endl;
    class Node {
    protected :
        int data;
        Node *next;
        Node *previous;
    public :
        int getData();
        Node *getNext();
        Node *getPrevious();
        void insertData(int data);
        void insertNext(Node *next);
        void insertPrevious(Node *previous);
    };
    class LinkList : protected Node{
    protected :
        Node *first;
        bool isEmpty();
        bool deleteFind(int data);
        void deleteOneByElement(int data);
    public :
        LinkList();
        ~LinkList();
        int getLength();
        long long int getElement(int position);
        void insert(int data, int position);
        void insertFromHead(int data);
        void insertFromTail(int data);
        int locateElement(int data);
        int *locateAllData(int data);
        void deleteByPosition(int position);
        void deleteByElement(int data);
        void cleanList();
        void showList();
    };
}


#endif //DOUBLELINKEDLIST_DOUBLELINKEDLIST_HPP

DoubleLinkedList.cpp :

#include "DoubleLinkedList.hpp"

using namespace DoubleLinkList;

Node *Node::getNext() {
    return this->next;
}
Node *Node::getPrevious() {
    return this->previous;
}
int Node::getData() {
    return this->data;
}
void Node::insertNext(Node *next) {
    this->next = next;
}
void Node::insertData(int data) {
    this->data = data;
}
void Node::insertPrevious(Node *previous) {
    this->previous = previous;
}
LinkList::LinkList() {
    first = new Node;
    next = first;
    previous = first;
    first->insertNext(first);
}
LinkList::~LinkList() {
    Node *linkList = first->getNext();
    while(linkList != first) {
        Node *node = linkList;
        linkList = node->getNext();
        delete node;
    }
    delete linkList;
}
bool LinkList::isEmpty() {
    if(first->getNext() == first) {
        return true;
    }
    return false;
}
int LinkList::getLength() {
    if(isEmpty()) {
        return 0;
    }
    Node *linkList = first;
    int length = 0;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        length++;
    }
    return length;
}
long long int LinkList::getElement(int position) {
    if(position < 1 || position > getLength()) {
        return INT64_MIN;
    }
    Node *linkList = first;
    for(int i = 1; i <= position; i++) {
        linkList = linkList->getNext();
    }
    auto returnData = (long long int)linkList->getData();
    linkList = nullptr;
    delete linkList;
    return returnData;
}
void LinkList::insert(int data, int position) {
    if(position < 1 || position > getLength() + 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *linkList = first;
    auto *newNode = new Node;
    newNode->insertData(data);
    for(int i = 1; i < position; i++) {
        linkList = linkList->getNext();
    }
    if(position == getLength() + 1) {
        newNode->insertNext(first);
        newNode->insertPrevious(linkList);
        linkList->insertNext(newNode);
        first->insertPrevious(newNode);
    }else {
        newNode->insertPrevious(linkList);
        newNode->insertNext(linkList->getNext());
        linkList->insertNext(newNode);
    }
}
void LinkList::insertFromHead(int data) {
    auto *newNode = new Node;
    newNode->insertData(data);
    newNode->insertNext(first->getNext());
    newNode->insertPrevious(first);
    first->insertNext(newNode);
}
void LinkList::insertFromTail(int data) {
    auto *newNode = new Node;
    newNode->insertData(data);
    newNode->insertNext(first);
    first->insertPrevious(newNode);
    Node *linkList = first;
    int length = getLength();
    for(int i = 1; i <= length; i++) {
        linkList = linkList->getNext();
    }
    linkList->insertNext(newNode);
}
int LinkList::locateElement(int data) {
    int position = 0;
    Node *linkList = first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        position++;
        if(linkList->getData() == data) {
            return position;
        }
    }
    return 0;
};
int *LinkList::locateAllData(int data) {
    int count = 0;
    Node *linkList = first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            count++;
        }
    }
    if(!count) {
        linkList = nullptr;
        delete linkList;
        return nullptr;
    }
    auto *returnArray = new int[count + 1];
    returnArray[0] = count;
    count = 1;
    linkList = first;
    int length = getLength();
    for(int i = 1; i <= length; i++) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            returnArray[count] = i;
            count++;
        }
    }
    linkList = nullptr;
    delete linkList;
    return returnArray;
}
void LinkList::deleteByPosition(int position) {
    if(position < 1 || position > getLength()) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *linkList = first;
    for(int i = 1; i < position; i++) {
        linkList = linkList->getNext();
    }
    Node *node = linkList->getNext();
    if(node->getNext() != first) {
        node->getNext()->insertPrevious(linkList);
        linkList->insertNext(node->getNext());
        delete node;
    }else {
        linkList->insertNext(first);
        first->insertPrevious(linkList);
        delete node;
    }
}
bool LinkList::deleteFind(int data) {
    Node *linkList =first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            return true;
        }
    }
    linkList = nullptr;
    delete linkList;
    return false;
}
void LinkList::deleteOneByElement(int data) {
    Node *linkList = first;
    while(linkList->getNext() != first) {
        Node *node;
        if(linkList->getNext()->getData() == data) {
            node = linkList->getNext();
            if(node->getNext() == first) {
                linkList->insertNext(first);
                first->insertPrevious(linkList);
                delete node;
            }else {
                linkList->insertNext(node->getNext());
                node->getNext()->insertPrevious(linkList);
                delete node;
            }
            linkList = nullptr;
            delete linkList;
            break;
        }
        linkList = linkList->getNext();
    }
}
void LinkList::deleteByElement(int data) {
    if(deleteFind(data)) {
        do {
            deleteOneByElement(data);
        }while(deleteFind(data));
    }else {
        cout << "Cannot find the element you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
    }
}
void LinkList::cleanList() {
    Node *linkList = first->getNext();
    while(linkList != first) {
        Node *node = linkList;
        linkList = linkList->getNext();
        delete node;
    }
    first->insertNext(first);
    first->insertPrevious(first);
}
void LinkList::showList() {
    int length = getLength();
    Node *linkList = first;
    cout << "Index : \t";
    for(int i = 1; i <= length; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        cout << linkList->getData() << "\t";
    }
    cout << endl;
}

main.cpp :

#include "DoubleLinkedList.hpp"

using namespace DoubleLinkList;

void menu();

int main(int argc, char *argv[]) {
    auto *linkList = new LinkList();
    int choice;
    int length;
    long long int gottenData;
    int location;
    int *locationAll;
    int data, position;
    do {
        system("clear");
        if(linkList->getLength()) {
            linkList->showList();
        }
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                length = linkList->getLength();
                cout << "The length of the list : " << length << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 2 :
                cout << "Please enter the position which you want to get its element : ";
                cin >> position;
                gottenData = linkList->getElement(position);
                if(gottenData == INT64_MIN) {
                    cout << "Cannot find the element you entered!" << endl;
                }else {
                    cout << "Position : " << gottenData << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element's position you want to insert : ";
                cin >> position;
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insert(data, position);
                break;
            case 4 :
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insertFromHead(data);
                break;
            case 5 :
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insertFromTail(data);
                break;
            case 6 :
                cout << "Please enter the element you want to locate : ";
                cin >> data;
                location = linkList->locateElement(data);
                if(location) {
                    cout << "Location : \t" << location << endl;
                }else {
                    cout << "Cannot find the element you entered!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 7 :
                cout << "Please enter the element you want to locate : ";
                cin >> data;
                locationAll = linkList->locateAllData(data);
                if(locationAll) {
                    cout << "Location : \t";
                    for(int i = 1; i <= locationAll[0]; i++) {
                        cout << locationAll[i] << "\t";
                    }
                    cout << endl;
                }else {
                    cout << "Cannot find the element you entered!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                cout << "Please enter the position you want to delete : ";
                cin >> position;
                linkList->deleteByPosition(position);
                break;
            case 9 :
                cout << "Please enter the element you want to delete : ";
                cin >> data;
                linkList->deleteByElement(data);
                break;
            case 10 :
                linkList->cleanList();
                break;
            case 11 :
                delete locationAll;
                delete linkList;
                exit(0);
            default :
                break;
        }
    }while(choice != 11);
}
void menu() {
    cout << "1. Get the list's length." << endl;
    cout << "2. Get element from the list." << endl;
    cout << "3. Insert to the list." << endl;
    cout << "4. Insert from head to the list." << endl;
    cout << "5. Insert from tail to the list." << endl;
    cout << "6. Locate a element from the list." << endl;
    cout << "7. Locate all elements from the list." << endl;
    cout << "8. Delete elements from the list by position." << endl;
    cout << "9. Delete elements from the list by element." << endl;
    cout << "10. Clean the list." << endl;
    cout << "11. Exit." << endl;
    cout << "----------------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}