雙向鏈表（DoubleLinkList）

• 2021 年 7 月 6 日
• 筆記
• 雙向鏈表, 雙鏈表, 數據結構

雙向鏈表

有關鏈表的知識可以點擊我上篇文章這裡就不再贅述LinkedList

• 雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。

雙向循環鏈表的可以點擊我這篇文章這裡就不再贅述DoubleLoopLinkList

添加

頭添加

void addFirst(const T &e) {
	//新建一個節點讓它前驅指向頭，後繼指向頭的後繼然後再讓頭的後繼指向新建的節點，
        head->next = new Node<T>(e, head, head->next);
        //把新節點的後繼節點的前驅指向新節點
        head->next->next->prev = head->next;
        ++size;
}

指定節點添加

void add(const int index, const T &e) {
        assert(index >= 0 && index <= size);
        Node<T> *prevNode = head;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        prevNode->next = new Node<T>(e, prevNode, prevNode->next);
        prevNode->next->next->prev = prevNode->next;
        ++size;
    }

尾添加

void addLast(const T &e) {
		//
        tail->prev = new Node<T>(e, tail->prev, tail);
        tail->prev->prev->next = tail->prev;
        ++size;
}

刪除

頭刪除

 T removeFirst() {
        return remove(0);//調不調都是O(1)，就這吧。
    }

指定節點刪除

T remove(int index) {
        assert(index >= 0 && index < size);
        //找到待刪除節點的前一節點
        Node<T> *prevNode = head;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        //暫存要刪除的節點
        Node<T> *retNode = prevNode->next;
        T temp = retNode->e;
        //前一節點的後繼指向待刪除節點的後繼
        prevNode->next = retNode->next;
        //後一節點的前驅指向待刪除節點的前驅
        retNode->next->prev = retNode->prev;
        retNode->next = nullptr;
        retNode->prev = nullptr;
        --size;
        delete retNode;
        retNode = nullptr;
        return temp;
    }

尾刪除

T removeLast() {
	//先暫存要刪除的節點
    Node<T> *retNode = tail->prev;
    T temp = retNode->e;
    //尾指針的前驅指向待刪除的前驅
    tail->prev = retNode->prev;
    待刪除節點前面一節點的後繼指向尾指針
    retNode->prev->next = tail;
    retNode->next = nullptr;
    retNode->prev = nullptr;
    delete retNode;
    retNode = nullptr;
    --size;
    return temp;
}

頭尾指針版

//
// Created by cheng on 2021/7/5.
//

#ifndef LINKEDLIST_TEST_H
#define LINKEDLIST_TEST_H
#include <assert.h>

template<typename T>
class Node {
public:
    T e;
    Node *prev;
    Node *next;

    Node() : e(0), prev(nullptr), next(nullptr) {

    }

    Node(const T &E) : e(E), prev(nullptr), next(nullptr) {

    }

    Node(const T &E, Node<T> *Prev, Node<T> *Next) : e(E), prev(Prev), next(Next) {

    }
};

template<typename T>
class DoubleLinkedList {
public:
    DoubleLinkedList() : size(0) {
        head = new Node<T>(0, nullptr, head);
        tail = new Node<T>(0, tail, nullptr);
    }

    constexpr int getSize() const {
        return size;
    }

    constexpr bool isEmpty() const {
        return size == 0;
    }

    void add(const int index, const T &e) {
        assert(index >= 0 && index <= size);
        Node<T> *prevNode = head;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        prevNode->next = new Node<T>(e, prevNode, prevNode->next);
        prevNode->next->next->prev = prevNode->next;
        ++size;
    }

    void addFirst(const T &e) {
        head->next = new Node<T>(e, head, head->next);
        head->next->next->prev = head->next;
        ++size;
    }

    void addLast(const T &e) {
        tail->prev = new Node<T>(e, tail->prev, tail);
        tail->prev->prev->next = tail->prev;
        ++size;
    }

    void set(const int index, const T &e) {
        assert(index >= 0 && index < size);
        Node<T> *cur = head->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        cur->e = e;
    }

    void setFirst(const T &e) {
        head->next->e = e;
    }

    void setLast(const T &e) {
        tail->prev->e = e;
    }

    bool contains(const T &e) const {
        Node<T> *cur = head->next;
        while (cur != nullptr) {
            if (cur->e = e) {
                return true;
            }
            cur = cur->next;
        }
        return false;
    }

    T get(const int index) const {
        assert(index >= 0 && index < size);
        Node<T> *cur = head->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur->e;
    }

    T getFirst() const {
        return head->next->e;
    }

    T getLast() const {
        return tail->prev->e;
    }

    T remove(int index) {
        assert(index >= 0 && index < size);
        Node<T> *prevNode = head;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        Node<T> *retNode = prevNode->next;
        prevNode->next = retNode->next;
        retNode->next->prev = retNode->prev;
        retNode->next = nullptr;
        retNode->prev = nullptr;
        --size;
        T temp = retNode->e;
        delete retNode;
        retNode = nullptr;
        return temp;
    }

    T removeFirst() {
        return remove(0);
    }

    T removeLast() {
        Node<T> *retNode = tail->prev;
        T temp = retNode->e;
        tail->prev = retNode->prev;
        retNode->prev->next = tail;
        retNode->next = nullptr;
        retNode->prev = nullptr;
        delete retNode;
        retNode = nullptr;
        --size;
        return temp;
    }

    ~DoubleLinkedList() {
        Node<T> *cur = head->next;
        Node<T> *temp;
        while (cur != nullptr) {
            temp = cur->next;
            delete cur;
            cur = temp;
        }
        head->next = nullptr;
        head->prev = nullptr;
        tail->prev = nullptr;
        tail->next = nullptr;
        delete head;
        head = nullptr;
        delete tail;
        tail = nullptr;
    }

    void print() {
        Node<T> *prevNode = head;
        std::cout << "LinkedList: size = " << size << std::endl;
        std::cout << "[";
        for (int i = 0; i < size; ++i) {
            prevNode = prevNode->next;
            std::cout << prevNode->e;
            if (i < size - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]" << std::endl;
    }

private:
    Node<T> *head, *tail;
    int size;
};
#endif //LINKEDLIST_TEST_H

虛擬頭節點

//
// Created by cheng on 2021/7/5.
//

#ifndef LINKEDLIST_DOUBLELINKEDLIST_H
#define LINKEDLIST_DOUBLELINKEDLIST_H

#include <assert.h>

template<typename T>
class Node {
public:
    T e;
    Node *prev;
    Node *next;

    Node() : e(0), prev(nullptr), next(nullptr) {}

    Node(const T &E) : e(E), prev(nullptr), next(nullptr) {}

    Node(const T &E, Node<T> *Prev, Node<T> *Next) : e(E), prev(Prev), next(Next) {}
};

template<typename T>
class DoubleLinkedList {
public:
    DoubleLinkedList() : size(0) {
        dummyHead = new Node<T>(0, nullptr, dummyHead);
    }

    constexpr int getSize() const {
        return size;
    }

    constexpr bool isEmpty() const {
        return size == 0;
    }

    void add(const int index, const T &e) {
        assert(index >= 0 && index <= size);
        Node<T> *prevNode = dummyHead;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        prevNode->next = new Node<T>(e, prevNode, prevNode->next);
        prevNode->next->next->prev = prevNode->next;
        ++size;
    }

    void addFirst(const T &e) {
        add(0, e);
    }

    void addLast(const T &e) {
        add(size, e);
    }

    void set(const int index, const T &e) {
        assert(index >= 0 && index < size);
        Node<T> *cur = dummyHead->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        cur->e = e;
    }

    void setFirst(const T &e) {
        set(0, e);
    }

    void setLast(const T &e) {
        set(size, e);
    }

    bool contains(const T &e) const {
        Node<T> *cur = dummyHead->next;
        while (cur != nullptr) {
            if (cur->e = e) {
                return true;
            }
            cur = cur->next;
        }
        return false;
    }

    T get(const int index) const {
        assert(index >= 0 && index < size);
        Node<T> *cur = dummyHead->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur->e;
    }

    T getFirst() const {
        return get(0);
    }

    T getLast() const {
        return get(size - 1);
    }

    T remove(int index) {
        assert(index >= 0 && index < size);
        Node<T> *prevNode = dummyHead;
        for (int i = 0; i < index; ++i) {
            prevNode = prevNode->next;
        }
        Node<T> *retNode = prevNode->next;
        prevNode->next = retNode->next;
        retNode->next->prev = retNode->prev;
        retNode->next = nullptr;
        retNode->prev = nullptr;
        --size;
        T temp = retNode->e;
        delete retNode;
        retNode = nullptr;
        return temp;
    }

    T removeFirst() {
        return remove(0);
    }

    T removeLast() {
        return remove(size - 1);
    }

    ~DoubleLinkedList() {
        Node<T> *cur = dummyHead->next;
        Node<T> *temp;
        while (cur != nullptr) {
            temp = cur->next;
            delete cur;
            cur = temp;
        }
        dummyHead->next = nullptr;
        dummyHead->prev = nullptr;
        delete dummyHead;
        dummyHead = nullptr;
    }

    void print() {
        Node<T> *prevNode = dummyHead;
        std::cout << "LinkedList: size = " << size << std::endl;
        std::cout << "[";
        for (int i = 0; i < size; ++i) {
            prevNode = prevNode->next;
            std::cout << prevNode->e;
            if (i < size - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]" << std::endl;
    }

private:
    Node<T> *dummyHead;
    int size;
};


#endif //LINKEDLIST_DOUBLELINKEDLIST_H