[数据结构与算法]c++ 双向链表

双向链表

在节点中比单向链表多存储了一个指向 上一个节点的 prev 指针、还有一个尾指针 last

代码：linkedLists.h

#ifndef DOUBLE_LINKEDLIST_LINKEDLIST_H
#define DOUBLE_LINKEDLIST_LINKEDLISTS_H
#include <iostream>

template <class T>
class LinkedLists{
private:
    // 嵌套类模板：private
    template <class >
    class Node{
    public:
        T element;
        Node<T>* next;
        Node<T>* prev;

        Node(){
            element = T();
            next = nullptr;
            prev = nullptr;
        }

        Node(T element, Node<T>* next, Node<T>* prev):element(element){
//                this->element = element;
            this->next = next;
            this->prev = prev;
        }

        ~Node()=default;

    };

private:
    const int ELEMENT_NOT_FOUND = -1;
    int Size;
    Node<T>* first;
    Node<T>* last;

    Node<T>* node(int index) const{
        if (index <= Size >> 1){
            Node<T>* node = first;
            for(int i=0; i < index; ++i){
                node = node->next;
            }
            return node;
        }else{
            Node<T>* node = last;
            for (int i=Size-1; i > index; --i){
                node = node->prev;
            }
            return node;
        }
    }


public:
    LinkedLists();
    LinkedLists(T element, Node<T>* next, Node<T>* prev);

    ~LinkedLists();

    int size() const;
    void clear();
    bool contains(T element);
    void add(T element);
    void add(T element, int index);
    T get(int index) const;
    T set(T element, int index);
    T remove(int index) ;
    int getPos(T element);
    void display() const;

};

template <class T>
LinkedLists<T>::LinkedLists():Size(0){
    Node<T>();
    first = nullptr;
    last = nullptr;
}

template <class T>
LinkedLists<T>::LinkedLists(T element, Node<T>* next, Node<T>* prev):Size(0){
    Node<T>(element, next, prev);
    first = nullptr;
    last = nullptr;
}

template <class T>
LinkedLists<T>::~LinkedLists() {
    Node<T>* ptr = first;
    int cnt = 0;
    while(ptr != nullptr){
        auto q = ptr->next;
        ptr->prev = ptr->next = nullptr;
        delete ptr;
        ptr = q;
        ++cnt;
    }
    first = nullptr;
    std::cout << "...Finally, calling destructor..." << cnt << std::endl;

}

template <class T>
int LinkedLists<T>::size() const {
    return Size;
}

template <class T>
void LinkedLists<T>::clear() {
    Node<T>* node = first;
    int cnt = 0;
    for (int i=0; i < Size; ++i){
        auto q = node->next;
        node->prev = node->next = nullptr;
        delete node;
        node = q;
        ++cnt;
    }
    Size = 0;
    first = nullptr;
    std::cout << "clear--->cnt: " << cnt << std::endl;
}

template <class T>
bool LinkedLists<T>::contains(T element) {
    return getPos(element) != ELEMENT_NOT_FOUND;
}

template <class T>
void LinkedLists<T>::add(T element) {
    add(element, Size);
}

template <class T>
void LinkedLists<T>::add(T element, int index) {

   if (index == Size){
       Node<T>* oldLast = last;
       last = new Node<T>(element, nullptr, oldLast);
       if (oldLast == nullptr){// 空链表 插入第一个元素的情况
           first = last;
       } else{
           oldLast->next = last;    // 结尾插入时
       }
   } else{
       Node<T>* next = node(index);
       Node<T>* prev = next->prev;
       auto nd = new Node<T>(element, next, prev);
       next->prev = nd;
       if (prev == nullptr){// index = 0时， 插入节点。
            first = nd;
       } else {
           prev->next = nd;
       }
   }

    ++Size;
}

template <class T>
T LinkedLists<T>::get(int index) const{
    return node(index)->element;
}

template <class T>
T LinkedLists<T>::set(T element, int index) {
    Node<T>* ptr = node(index);
    T old = ptr->element;
    ptr->element = element;
    return old;
}

template <class T>
T LinkedLists<T>::remove(int index) {
    Node<T>* currentNd = node(index);
    Node<T>* prev = currentNd->prev;
    Node<T>* next = currentNd->next;
    if (prev == nullptr){
        next->prev = nullptr;
        first = next;
        currentNd->next = nullptr;
    }else{
        if (next == nullptr){
            last = prev;
            last->next = nullptr;
            currentNd->prev = nullptr;
        } else{
            prev->next = next;
            next->prev = prev;
            currentNd->prev = currentNd->next = nullptr;
        }
    }
    T old = currentNd->element;
    --Size;
    delete currentNd;          // 删除节点后，释放 add 时 new 出来的节点内存；
    return old;
}

template <class T>
int LinkedLists<T>::getPos(T element) {
    int position = ELEMENT_NOT_FOUND;
    Node<T>* ptr = first;
    for (int i=0; i < Size; ++i){
        if(element == ptr->element){
            position = i;
            break;
        }
        ptr = ptr->next;
    }
    return position;
}

template <class T>
void LinkedLists<T>::display() const {
    for(Node<T>* nd = first; nd != nullptr; nd = nd->next){
        std::cout << nd->element << "   ";
    }
    std::cout << std::endl;
}

#endif //DOUBLE_LINKEDLIST_LINKEDLIST_H

注意：
在清空、删除 和 析构函数中 free 节点时，需将节点中 next 和 prev 指针指向 nullptr，然后再 free 节点申请的堆空间内存。

测试代码：

main.cpp

// Created by ZP on 2021/8/19.

#include <iostream>
#include "LinkedLists.h"

using std::cout;
using std::endl;

typedef int T;

int main(){

//    auto listPtr = new LinkedLists<T>();
    auto listPtr = new LinkedLists<T>(0, nullptr, nullptr);

    // function---->add()
    listPtr->add(100, 0);
    listPtr->add(10000, listPtr->size());
    listPtr->add(20);
    listPtr->add(500);
    for (int i = 0; i < 10; ++i){
        listPtr->add(i*100, i+2);
    }
    listPtr->display();
    cout << "---------------------------------------------------------------------" << endl;

    // function---->remove()
    listPtr->remove(0);

    T a = listPtr->remove(3);
    cout << "a<--remove: " << a << endl;

    listPtr->remove(listPtr->size()-1);
    listPtr->display();
    cout << "---------------------------------------------------------------------" << endl;

    // function---->set()
    a = listPtr->set(10, 0);
    cout << "a<--set: " << a << endl;

    a = listPtr->set(20000, listPtr->size()-1);
    cout << "a<--set: " << a << endl;

    a = listPtr->set(30000, 3);
    cout << "a<--set: " << a << endl;
    listPtr->display();
    cout << "---------------------------------------------------------------------" << endl;

    // function---->get()
    a = listPtr->get(0);
    cout << "a<--get: " << a << endl;

    a = listPtr->get(listPtr->size()-1);
    cout << "a<--get: " << a << endl;

    a = listPtr->get(3);
    cout << "a<--get: " << a << endl;
    cout << "---------------------------------------------------------------------" << endl;

    // function---->getPos()
    int pos = listPtr->getPos(10);
    cout << "pos(element->10): " << pos << endl;

    pos = listPtr->getPos(20000);
    cout << "pos(element->20000): " << pos << endl;

    pos = listPtr->getPos(30000);
    cout << "pos(element->30000): " << pos << endl;
    cout << "---------------------------------------------------------------------" << endl;

    // function---->contains()
    bool tr = listPtr->contains(10);
    cout << "true(1) or false(0): " << tr << endl;
    tr = listPtr->contains(20000);
    cout << "true(1) or false(0): " << tr << endl;
    tr = listPtr->contains(-10);
    cout << "true(1) or false(0): " << tr << endl;
    cout << "---------------------------------------------------------------------" << endl;

    // function---->clear()
    listPtr->clear();
    listPtr->display();
    cout << "listPtr---->size: " << listPtr->size() << endl;
    cout << "---------------------------------------------------------------------" << endl;

    delete listPtr;
    return 0;
}

运行结果：

E:\programme\C_C++\CLion\C++\algorithm\LinkedList\double_LinkedList\cmake-build-debug\double_LinkedList.exe
100   10000   0   100   200   300   400   500   600   700   800   900   20   500
---------------------------------------------------------------------
a<--remove: 200
10000   0   100   300   400   500   600   700   800   900   20
---------------------------------------------------------------------
a<--set: 10000
a<--set: 20
a<--set: 300
10   0   100   30000   400   500   600   700   800   900   20000
---------------------------------------------------------------------
a<--get: 10
a<--get: 20000
a<--get: 30000
---------------------------------------------------------------------
pos(element->10): 0
pos(element->20000): 10
pos(element->30000): 3
---------------------------------------------------------------------
true(1) or false(0): 1
true(1) or false(0): 1
true(1) or false(0): 0
---------------------------------------------------------------------
clear--->cnt: 11

listPtr---->size: 0
---------------------------------------------------------------------
...Finally, calling destructor...0

Process finished with exit code 0