双向链表（DoubleLinkList）
双向链表
有关链表的知识可以点击我上篇文章这里就不再赘述
- 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向循环链表的可以点击我这篇文章这里就不再赘述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本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文系转载，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录