【C++】链表模板实现

“基础的轮子还是要造的，可以加深对它的理解”  一、总体结构及头文件

文件名称：LinkedList

二、LinkedList.h

#pragma once

template
class ListNode {
public:
	T val;
	ListNode* nxt;
	ListNode* pre;
	ListNode();
	ListNode(T key);
};

/**********************************************************************/

template
class LinkedList {
public:
	LinkedList();
	LinkedList(int n);
	LinkedList(int n, T key);
	~LinkedList();
	ListNode* begin();
	ListNode* end();
	void push_front(T key);
	void push_back(T key);
	void pop_front();
	void pop_back();
	bool empty();
	void clear();
	ListNode* find(T key);
	void insert(ListNode* node, T key);
	void erase(ListNode* node, T key);
	void print();
	int size();
	
private:
	ListNode *head;
	ListNode *tail;
	int lens;
};

三、LinkedList.cpp (具体实现)

#pragma once
#include"LinkedList.h"
#include

template
ListNode::ListNode() {
	this->nxt = nullptr;
	this->pre = nullptr;
	this->val = 0;
}
template
ListNode::ListNode(T key) {
	this->nxt = nullptr;
	this->pre = nullptr;
	this->val = key;
}

/**********************************************************************/

template
LinkedList::LinkedList() {
	this->head = new ListNode;
	this->tail = new ListNode;
	this->head->nxt = this->tail;
	this->head->pre = nullptr;
	this->tail->nxt = nullptr;
	this->tail->pre = this->head;
	lens = 0;
}
template
LinkedList::LinkedList(int n) {
	this->head = new ListNode;
	this->tail = new ListNode;
	this->head->nxt = this->tail;
	this->head->pre = nullptr;
	this->tail->nxt = nullptr;
	this->tail->pre = this->head;
	lens = n;
	ListNode* tmp = this->head;
	while (n) {
		ListNode *node = new ListNode;
		node->pre = tmp;
		node->nxt = this->tail;
		tmp->nxt = node;
		this->tail->pre = node;
		tmp = node;
		--n;
	}
}
template
LinkedList::LinkedList(int n, T key) {
	this->head = new ListNode(key);
	this->tail = new ListNode(key);
	this->head->nxt = this->tail;
	this->head->pre = nullptr;
	this->tail->nxt = nullptr;
	this->tail->pre = this->head;
	lens = n;
	ListNode* tmp = this->head;
	while (n) {
		ListNode* node = new ListNode(key);
		node->pre = tmp;
		node->nxt = this->tail;
		tmp->nxt = node;
		this->tail->pre = node;
		tmp = node;
		--n;
	}
}
template
LinkedList::~LinkedList() {
	ListNode* tmp = this->head->nxt;
	ListNode* node = this->head->nxt->nxt;
	while (tmp != this->tail) {
		delete tmp;
		tmp = node;
		node = node->nxt;
	}
	this->head->nxt = this->tail;
	this->tail->pre = this->head;
	lens = 0;
}
template
ListNode* LinkedList::begin() {
	return this->head;
}
template
ListNode* LinkedList::end() {
	if (lens == 0) return nullptr;
	return this->tail->pre;
}
template
void LinkedList::push_front(T key) {
	ListNode* node = new ListNode(key);
	this->head->nxt->pre = node;
	node->nxt = this->head->nxt;
	node->pre = this->head;
	this->head->nxt = node;
	++lens;
}
template
void LinkedList::push_back(T key) {
	ListNode* node = new ListNode(key);
	this->tail->pre->nxt = node;
	node->pre = this->tail->pre;
	node->nxt = this->tail;
	this->tail->pre = node;
	++lens;
}
template
void LinkedList::pop_front() {
	if (lens == 0) return;
	ListNode* tmp = this->head->nxt->nxt;
	delete this->head->nxt;
	tmp->pre = this->head;
	this->head->nxt = tmp;
	--lens;
}
template
void LinkedList::pop_back() {
	if (lens == 0) return;
	ListNode* tmp = this->tail->pre->pre;
	delete this->tail->pre;
	tmp->nxt = this->tail;
	this->tail->pre = tmp;
	--lens;
}
template
bool LinkedList::empty() {
	return lens == 0;
}
template
void LinkedList::clear() {
	ListNode* tmp = this->head->nxt;
	ListNode* node = this->head->nxt->nxt;
	while (tmp != this->tail) {
		delete tmp;
		tmp = node;
		node = node->nxt;
	}
	this->head->nxt = this->tail;
	this->tail->pre = this->head;
	lens = 0;
}
template
ListNode* LinkedList::find(T key) {
	ListNode* tmp = new ListNode;
	tmp = this->head->nxt;
	while (tmp != this->tail) {
		if (tmp->val == key) return tmp;
	}
	return nullptr;
}
template
void LinkedList::insert(ListNode* node, T key) {
	if (node->nxt == nullptr) return;
	ListNode* ins = new ListNode(key);
	node->nxt->pre = ins;
	ins->nxt = node->nxt;
	ins->pre = node;
	node->nxt = ins;
	++lens;
}
template
void LinkedList::erase(ListNode* node, T key) {
	if (node->nxt == nullptr || node->pre==nullptr) return;
	node->nxt->pre = node->pre;
	node->pre->nxt = node->nxt;
	delete node;
	--lens;
}
template
void LinkedList::print() {
	ListNode* tmp = this->head->nxt;
	while (tmp != this->tail) {
		std::cout << tmp->val << " ";
		tmp = tmp->nxt;
	}
}
template
int LinkedList::size() {
	return lens;
}

四、测试代码

#include 
#include"LinkedList.cpp"

void testLinkedList() {
	LinkedList l1(5);
	l1.push_front(5);
	l1.push_back(6);
	l1.print();
	std::cout << std::endl << l1.size() << std::endl;
	l1.pop_back();
	l1.pop_front();
	l1.insert(l1.begin(), 10);
	l1.insert(l1.end(), 10);
	l1.print();
	std::cout << std::endl << l1.size() << std::endl;
	l1.clear();
	l1.print();
}

int main()
{
	testLinkedList();
	system("pause");
	return 0;
}

输出结果：（Visual C++ 2022编译环境）

 Tips：

若在<>中填写string等未在iostream中定义的运算，请先在LinkedList.cpp文件中加入所需的库