C++怎么實現雙向鏈表

這篇“C++怎么實現雙向鏈表”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++怎么實現雙向鏈表”文章吧。

前言:

前面文章分析了單向鏈表，并給出了python和C++實現：單鏈表從原理到實現，python和C++兩個版本

本文介紹的雙向鏈表是在單向鏈表基礎上的一個改進，每個節點指向其直接前驅和直接后繼節點。因此，從雙向鏈表的任意位置開始，都能訪問所有的節點。

一、雙向鏈表優缺點

雙向鏈表的缺點：

從節點的結構上可以看出，雙向鏈表的所需的存儲空間大于單向鏈表。同時，對于插入和刪除等操作來說，雙向鏈表的節點操作更加復雜，涉及到節點的前后兩個節點。

雙向鏈表的節點：

對于雙向鏈表來說，它的每個節點要指向“直接前驅”和“直接后繼”，所以節點類需要含有兩個指針域。指向直接前驅的指針使用pre表示，指向后繼的指針使用next表示。

二、C++實現分析

（1）節點類

雙向鏈表的節點含有兩個指針域，即直接前驅pre和直接后繼next。節點類采用的是模板實現，這樣其所存儲的數據就不再依賴于特定類型。

template<class T>
class Node {
public:
    Node() {}
    Node *pre;
    Node *next;
    // 由于data屬性是私有的
    // 所以采用get和set對data進行處理
    void setData(T data) { this->data = data; }
    T getData() { return this->data; }
private:
    T data;
};

（2）鏈表類分析

鏈表類應該包含基本的增、改、刪、查等操作，由于其各種功能的實現是很相似的，

所以下面給出了需要實現的典型函數：

• 構造函數：

• isEmpty()判斷是否為空；

• size()返回鏈表長度；

• insert()頭插、尾插、中間插入節點；

• delete()刪除節點；

• getNode()獲取節點；

• traversal()遍歷鏈表；

鏈表類的定義如下：

template<class P>
class DoubleLinkedList {
public:
    DoubleLinkedList();
    bool isEmpty();
    Node<P>  *getNode(int index);
    int size();
    void insert(int data, int index);
    void traversal();
    void remove(int index);

private:
    Node<P> *head;
};

（3）鏈表類構造函數

初始化時需要創建頭節點，作為頭指針：

template<class P>
DoubleLinkedList<P>::DoubleLinkedList() {
    // 創建頭結點
    head = new Node<P>();
    head->pre = NULL;
    head->next = NULL;
    head->setData(666);
}

（4）isEmpty()判斷是否為空

對于雙向鏈表來說，判斷是否為空只需要判斷頭指針是否指向其他Node節點：

template<class P>
bool DoubleLinkedList<P>::isEmpty() {
    if (head->next == NULL) {
        return true;
    }
    else
    {
        return false;
    }
}

（5）size()獲取鏈表長度

獲取鏈表長度時需要判斷鏈表是否為空，從而確定是否采用遍歷的方式計算鏈表的長度。

由于采用的不是循環鏈表，所以循環的結束條件是判斷是否指向空節點：

template<class P>
int DoubleLinkedList<P>::size() {
    if (isEmpty()) {
        return 0;
    }
    else {
        int count = 0;
        Node<P> *current = head->next;
            // 循環結束條件
        while (current!=NULL)
        {
            current = current->next;
            count++;
        }
        return count;
    }
}

（6）getNode()獲取節點

在插入和刪除等操作中，需要頻繁的進行節點獲取操作。

所以應該封裝為單獨的函數用于節點獲取，如下：

template<class P>
Node<P> *DoubleLinkedList<P>::getNode(int index) { 
    Node<P> *current = head;
    int currentCount = 0;
    // 循環結束條件
    while (currentCount<=index)
    {
        current = current->next;
        currentCount++;
    }
    return current;
}

（7）insert()插入節點

插入節點依舊包含頭插法，尾插法和任意位置的插入。插入操作與單向鏈表的最大區別在于節點的指針移動較為復雜，需要將插入位置前后兩個節點與新節點均建立聯系：

template<class P>
void DoubleLinkedList<P>::insert(int data, int index) {
    Node<P> *node = new Node<P>();
    node->setData(data);
    // 1、列表為空時
    if (isEmpty()) {
        head->next = node;
        node->pre = head;
        return;
    }
    // 2、頭插法
    if (index == 0) {
        node->next = head->next;
        head->next->pre = node;
        node->pre = head;
        head->next = node;
    }
    // 3、尾插法
    else if (index >= this->size() - 1) {
        // printf("index %d, size %d \n", index, this->size());
        Node<P> *temp = this->getNode(this->size()-1);
        temp->next = node;
        node->pre = temp;
    }
    // 4、任意位置插入
    else
    {
        Node<P> *pre = this->getNode(index);
        Node<P> *next = pre->next;
        node->next = pre->next;
        node->pre = pre;
        pre->next = node;
        node->next->pre = node;
    }
}

（8）、remove()刪除節點

前面已經定義了用于獲取節點的getNode()函數，所以remove()函數只需要進行指針移動操作。

將所要刪除的節點的直接前驅節點和直接后繼節點相連：

template<class P>
void DoubleLinkedList<P>::remove(int index) {
    // 保證索引有意義
    if ((index < (this->size()-1)) && (index>0)) {
        Node<P> *node = this->getNode(index);
        Node<P> *pre = node->pre;
        Node<P> *next = node->next;
        pre->next = next;
        next->pre = pre;
    }
}

（9）traversal()遍歷鏈表函數

雖然可以從雙向鏈表的任一個節點開始遍歷整個鏈表，但是下面的實現依舊是從頭結點開始的，循環的結束依舊是指向空指針：

template<class P>
void DoubleLinkedList<P>::traversal() {
    if (!isEmpty()) {
        Node<P> *current = head;
        while (current)
        {
            cout << current->getData() << endl;
            current = current->next;
        }
    }
}

以上就是關于“C++怎么實現雙向鏈表”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。