为什么要使用双向链表
单向链表只能从头节点往后遍历，双向链表每个节点都有指向上一个节点的指针，支持反向遍历，如果数据量比较大的时候，从后往前遍历遍历效率更高，查找的效率会间接影响增删的效率。
具体逻辑实现
//
// 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
