基于面向对象，C++实现双链表

双链表同单链表类似，由一个值和两个指针组成
在这里插入图片描述

`Node.h`节点头文件

#pragma once
class Node
{
public:int value;Node* prev;Node* next;Node(int value);~Node();
};

`Node.cpp`节点源文件

#include "Node.h"Node::Node(int value)
{this->value = value;prev = nullptr;next = nullptr;
}Node::~Node()
{
}

`DoubleLinkList.h`双链表头文件

#pragma once
#include "Node.h"
class DoubleLinkList
{public:Node* head;Node* tail;int length;DoubleLinkList(int val);//有参构造void PrintDoubleLinkList();//打印双链表void getLength();//获取双链表长度void append(int val);//尾部插入元素void prepend(int val);//头部插入元素void insert(int index, int val);//任意位置插入元素Node* removeLast();//删除最后一个元素Node* removeFirst();//删除第一个元素Node* remove(int index);//删除任意位置元素Node* get(int index);//获取元素bool change(int index, int val);//改变元素int search(int val);//查找元素
};

`DoubleLinkList.cpp`节点源文件

#include "DoubleLinkList.h"
#include<iostream>
using namespace std;DoubleLinkList::DoubleLinkList(int val)
{Node* newNode = new Node(val);head = newNode;tail = newNode;length = 1;
}//打印链表
void DoubleLinkList::PrintDoubleLinkList()
{Node* temp = head;while (temp!=nullptr) {cout << temp->value << " ";temp = temp->next;}cout << endl;
}
//获取双链表长度
void DoubleLinkList::getLength()
{cout << "双链表长度为：" << length << endl;
}//尾部插入
void DoubleLinkList::append(int val)
{Node* newNode = new Node(val);if (length == 0) {head = newNode;tail = newNode;}else {tail->next = newNode;newNode->prev = tail;tail = newNode;}length++;
}//头部插入
void DoubleLinkList::prepend(int val)
{Node* newNode = new Node(val);if (length == 0) {head = newNode;tail = newNode;}else {newNode->next = head;head->prev = newNode;head = newNode;}length++;
}//任意位置插入
void DoubleLinkList::insert(int index, int val)
{if (index<0 || index>length) {cout << "error";}else if (index == 0) {prepend(val);}else if(index == length){append(val);}else {Node* p1 = head;for (int i = 0; i < index - 1; i++) {p1 = p1->next;}Node* p2 = p1->next;Node* newNode = new Node(val);newNode->prev = p1;newNode->next = p2;p1->next = newNode;p2->prev = newNode;length++;}
}//删除尾部
Node* DoubleLinkList::removeLast()
{if (length == 0) {return nullptr;}Node* temp = tail;if (length == 1) {head = nullptr;tail = nullptr;}else {tail = tail->prev;tail->next = nullptr;temp->prev = nullptr;}length--;return temp;
}//删除头部
Node* DoubleLinkList::removeFirst()
{if (length == 0) {return nullptr;}Node* temp = head;if (length == 1) {head = nullptr;tail = nullptr;}else {head = head->next;head->prev = nullptr;temp->next = nullptr;}length--;return temp;
}//删除任意位置
Node* DoubleLinkList::remove(int index)
{if (index<0 || index>length) {return nullptr;}if (index == 0) {return removeFirst();}if (index == length - 1) {return removeLast();}Node* temp = head;for (int i = 0; i < index; i++) {temp = temp->next;}temp->next->prev = temp->prev;temp->prev->next = temp->next;temp->next = nullptr;temp->prev = nullptr;length--;return temp;
}//获取元素
Node* DoubleLinkList::get(int index)
{if (index<0 || index>length) {return nullptr;}Node* temp = head;if (index < length / 2) {for (int i = 0; i < index; i++) {temp = temp->next;}}else {temp = tail;for (int i = length - 1; i > index; i--) {temp = temp->prev;}}return temp;
}//改变元素
bool DoubleLinkList::change(int index, int val)
{Node* temp = get(index);if (temp) {temp -> value = val;return true;}return false;
}//查找元素
int DoubleLinkList::search(int val)
{int index = 0;Node* temp = head;while (temp->value != val) {index++;temp = temp->next;if (temp == nullptr) {cout << "未找到！" << endl;return -1;}}cout << "找到了！元素索引为：";return index;
}

插入元素

1. 头部插入

1.新节点的next指向head节点
2.head节点的prev指向新节点
3.head移动至新节点
具体如下图所示：

在这里插入图片描述

//头部插入
void DoubleLinkList::prepend(int val)
{Node* newNode = new Node(val);if (length == 0) {head = newNode;tail = newNode;}else {newNode->next = head;head->prev = newNode;head = newNode;}length++;
}

2. 尾部插入

1.尾节点tail的next指向新节点
2.新节点的prev指向尾节点tail
3.tail节点移动到新节点

在这里插入图片描述

//尾部插入
void DoubleLinkList::append(int val)
{Node* newNode = new Node(val);if (length == 0) {head = newNode;tail = newNode;}else {tail->next = newNode;newNode->prev = tail;tail = newNode;}length++;
}

3. 任意位置插入

1.创建新节点p1指向头结点head，然后移动至插入节点前一个节点，并创建新节点p2指向p1的next节点
2.新节点的prev指向p1
3.新节点的next指向p2
4.p1节点的next指向新节点
5.p2节点的prev指向新节点

在这里插入图片描述

//任意位置插入
void DoubleLinkList::insert(int index, int val)
{if (index<0 || index>length) {cout << "error";}else if (index == 0) {prepend(val);}else if(index == length){append(val);}else {Node* p1 = head;for (int i = 0; i < index - 1; i++) {p1 = p1->next;}Node* p2 = p1->next;Node* newNode = new Node(val);newNode->prev = p1;newNode->next = p2;p1->next = newNode;p2->prev = newNode;length++;}
}

删除元素

1. 尾部删除

1.新建一个节点temp指向尾节点tail
2.尾节点tail移动至tail的prev节点
3.尾节点tail的next指向空
4.temp的prev指针指向空

在这里插入图片描述

//删除尾部
Node* DoubleLinkList::removeLast()
{if (length == 0) {return nullptr;}Node* temp = tail;if (length == 1) {head = nullptr;tail = nullptr;}else {tail = tail->prev;tail->next = nullptr;temp->prev = nullptr;}length--;return temp;
}

2. 头部删除

1.新建一个节点temp指向头结点head
2.head节点移动到head的next指针指向的节点
3.head的prev指针指向nullptr
4.temp节点的next指针指向nullptr

在这里插入图片描述

//删除头部
Node* DoubleLinkList::removeFirst()
{if (length == 0) {return nullptr;}Node* temp = head;if (length == 1) {head = nullptr;tail = nullptr;}else {head = head->next;head->prev = nullptr;temp->next = nullptr;}length--;return temp;
}

3. 任意位置删除

1.新建一个节点temp指向头结点head
2.temp移动到要删除的节点处
3.temp的next节点的prev指针指向temp的prev节点
4.temp的prev节点的next指针指向temp的next节点
5.temp的next节点指向nullptr
6.temp的prev节点指向nullptr

在这里插入图片描述

//删除任意位置
Node* DoubleLinkList::remove(int index)
{if (index<0 || index>length) {return nullptr;}if (index == 0) {return removeFirst();}if (index == length - 1) {return removeLast();}Node* temp = head;for (int i = 0; i < index; i++) {temp = temp->next;}temp->next->prev = temp->prev;temp->prev->next = temp->next;temp->next = nullptr;temp->prev = nullptr;length--;return temp;
}

获取元素

1.比较索引和链表长度的大小
2.若索引比length小，则在链表的前一半向后找
3.若索引比length大，则在链表的后一半向前找

在这里插入图片描述

//获取元素
Node* DoubleLinkList::get(int index)
{if (index<0 || index>length) {return nullptr;}Node* temp = head;if (index < length / 2) {for (int i = 0; i < index; i++) {temp = temp->next;}}else {temp = tail;for (int i = length - 1; i > index; i--) {temp = temp->prev;}}return temp;
}

改变元素

1.获取节点
2.将节点的值改为需要的值即可

在这里插入图片描述

//改变元素
bool DoubleLinkList::change(int index, int val)
{Node* temp = get(index);if (temp) {temp -> value = val;return true;}return false;
}

查找元素

1.新建一个节点temp指向头结点head
2.不断向后移动temp并判断temp是否威空
3.最终返回索引

//查找元素
int DoubleLinkList::search(int val)
{int index = 0;Node* temp = head;while (temp->value != val) {index++;temp = temp->next;if (temp == nullptr) {cout << "未找到！" << endl;return -1;}}cout << "找到了！元素索引为：";return index;
}

测试：新建一个main文件进行测试

#include<iostream>
#include"Node.h"
#include"DoubleLinkList.h"using namespace std;void test01() {DoubleLinkList* myList = new DoubleLinkList(1);myList->append(3);myList->append(5);myList->append(7);myList->append(9);myList->PrintDoubleLinkList();myList->getLength();
}void test02() {DoubleLinkList* myList1 = new DoubleLinkList(1);myList1->append(3);myList1->append(5);myList1->append(7);myList1->append(9);//myList1->insert(5, 4);//myList1->removeLast();//myList1->remove(2);//cout<<myList1->get(4)->value<<endl;//myList1->change(2, 4);cout<<myList1->search(5)<<endl;myList1->PrintDoubleLinkList();myList1->getLength();
}int main() {//test01();test02();
}