基于面向对象，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();
}

测试结果如下：