为什么要使用双向链表

单向链表只能从头节点往后遍历，双向链表每个节点都有指向上一个节点的指针，支持反向遍历，如果数据量比较大的时候，从后往前遍历遍历效率更高，查找的效率会间接影响增删的效率。

具体逻辑实现

//
// Created by ygq on 2024/11/1.
//
#include "log.h"

#ifndef YGQ_TAG
#define YGQ_TAG

template<class E>
struct Node {
    E value;
    Node<E> *pre;
    Node<E> *next;

    Node(E value, Node<E> *pre, Node<E> *next) {
        this->value = value;
        this->pre = pre;
        this->next = next;
    }
};

template<class E>
class LinkedList {
private:
    int len = 0;
    Node<E> *head = nullptr;
    Node<E> *end = nullptr;
public:
    void push(E e);

    void insert(int index, E e);

    E remove(int index);

    Node<E> *findNode(int index);

    E get(int index);

    int size();

    void linkLast(E e);

    void linkBefore(Node<E> *cur, E e);
};

/*
template<class E>
void LinkedList<E>::push(E e) {
    Node<E> *new_node = new Node<E>(e, nullptr);
    if (head) {
        Node<E> *last = findNode(len - 1);
        last->next = new_node;
    } else {
        head = new_node;
    }
    len++;
}*/

template<class E>
void LinkedList<E>::push(E e) {
    Node<E> *new_node = new Node<E>(e, end, nullptr);
    if (head) {
        end->next = new_node;
        end = new_node;
    } else {
        head = new_node;
        end = new_node;
    }
    len++;
}

template<class E>
void LinkedList<E>::linkLast(E e) {
    Node<E> *new_node = new Node<E>(e, end, nullptr);
    if (head) {
        end->next = new_node;
        end = new_node;
    } else {
        head = new_node;
        end = new_node;
    }
}

template<class E>
void LinkedList<E>::linkBefore(Node<E> *cur, E e) {
    Node<E> *new_node = new Node<E>(e, cur->pre, cur);
    cur->pre->next = new_node;
    cur->pre = new_node;
}

template<class E>
void LinkedList<E>::insert(int index, E e) {
    if (index > len - 1 || index < 0) {
        LOGE("index:%d illegal,must <= %d or > 0", index, len - 1);
        return;
    }
    Node<E> *node = findNode(index);
    linkBefore(node, e);
    len++;
}

template<class E>
E LinkedList<E>::remove(int index) {
    if (index > len - 1 || index < 0) {
        LOGE("index:%d illegal,must <= %d or > 0", index, len - 1);
        return E();
    }
    Node<E> *cur = findNode(index);
    if (cur->pre) {
        cur->pre->next = cur->next;
    } else {//头节点
        head = cur->next;
    }
    if (cur->next) {
        cur->next->pre = cur->pre;
    } else {//尾节点
        end = cur->pre;
    }
    E value = cur->value;
    delete cur;
    len--;
    return value;
}

template<class E>
E LinkedList<E>::get(int index) {
    return findNode(index)->value;
}

template<class E>
Node<E> *LinkedList<E>::findNode(int index) {
    if (index > len >> 1) {
        //从后往前遍历
        Node<E> *cur = end;
        for (int i = len - 1; i > index; --i) {
            cur = cur->pre;
        }
        return cur;
    } else {
        //从前往后遍历
        Node<E> *cur = head;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur;
    }
}

template<class E>
int LinkedList<E>::size() {
    return len;
}

#endif

运行效果

index:0,value:0
index:1,value:1
index:2,value:2
index:3,value:5
index:4,value:6
index:5,value:7
---------
index:0,value:1
index:1,value:5
index:2,value:6

源码地址

https://github.com/treech/NDKDemo