双向链表

有关链表的知识可以点击我上篇文章这里就不再赘述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

最新文章

1. OC中如何把数组中字典的数据转换成URL?
2. 一些BOOTSTRAP的问题
3. 【Apache运维基础(5)】Apache的Rewrite攻略（2）
4. 【MongoDB】开启认证权限
5. 如何查找局域网的外网ip
6. Python学习笔记 ：01概述
7. String,StringBuffer与StringBuilder的差别??
8. SQL 练习题
9. java代码中获取进程process id（转）
10. centos 7.1系统更改Mariadb数据存储位置步骤分享
11. Node.js 常用工具
12. 熊掌号："搜索+信息流"双引擎与"百家号+熊掌号"双品牌内容平台
13. 谈谈在.NET Core中使用Redis和Memcached的序列化问题
14. 一口一口吃掉Hibernate（四）——多对一单向关联映射
15. iOS中使用iCloud一些需要注意的地方(Xcode7.2)
16. Webpack 4教程 - 第六部分 增强开发时体验
17. PL/SQL出现存储过程注释中文乱码
18. postman学习笔记（二）
19. Prufer codes与Generalized Cayley's Formula
20. GetTextMetrics与GetTextExtent的区别

热门文章

1. kenel 和shell
2. mysql基础之mysql双主（主主）架构
3. 技术干货 | 如何在 Library 中使用/依赖 mPaaS？
4. 防火墙 firewall iptables
5. 西门子 S7-300 以太网模块连接 WINCC方案
6. springboot整合JDBC出现Loading class `com.mysql.jdbc.Driver'. This is deprecated. The new driver class is `com.mysql.cj.jdbc.Driver'.
7. Python API vs C++ API of TensorRT
8. TensorRT 7.2.1 开发概要（上）
9. 记 Ant Designer Vue 2.0.1 layout 丢失样式类名问题分析
10. 一、Nginx的安装