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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> c++ 双向链表 -> 正文阅读

[数据结构与算法]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