【链表】还不会用C++实现链表？一文教会你各种链表的实现

本文将用C++语言来实现数据结构中的无头单链表，带头循环链表，以及带头循环双向链表等链表结构（带头单链表与后两种链表的结构相似，实现起来比后两种更简单，读者阅读完本文即可自行实现）

一、无头单链表的实现

无头单链表在头插时需要改变头指针的位置，具体代码实现如下：

//无头单链表

#include <iostream>
#include <assert.h>

using namespace std;

template <class T>

//先定义链表中的节点
struct SListNode
{
	T data;
	SListNode* next;

	SListNode(T x)
	{
		this->data = x;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	//链表初始化后链表中就有一个节点
	SListNode<T>* head;
	
public:
	SList(T x)
	{
		this->head = new SListNode<T>(x);
	}

	~SList()
	{
		SListNode<T>* cur = head;
		while (cur)
		{
			SListNode<T>* next = cur->next;
			delete cur;
			cur = next;
		}
	}


	// 动态申请一个节点
	SListNode<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	SListNode<T>* SListFind(T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(SListNode<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(SListNode<T>* pos);

};


template <class T>
SListNode<T>* SList<T>:: BuySListNode(T x)
{
	SListNode<T>* tmp = new SListNode<T>(x);
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	SListNode<T>* cur =head;
	while (cur)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	SListNode<T>* cur = head;

	while (cur->next)
	{
		cur = cur->next;
	}
	SListNode<T>* newnode = BuySListNode(x);
	cur->next = newnode;//连接
}
template <class T>
void SList<T>::SListPushFront(T x)
{
	SListNode<T>* newnode = BuySListNode(x);
	newnode->next = head;
	head = newnode;
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head);//头结点为空就不能继续删除了
	SListNode<T>* tail = head;
	//链表中只有一个节点就只能删除头结点
	if (tail->next == nullptr)
	{
		delete head;
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		delete tail->next;
		tail->next = nullptr;
	}

}

template <class T>
void SList<T>::SListPopFront()
{
	assert(head);
	SListNode<T>* cur = head->next;
	delete head;
	head = cur;
}

template <class T>
SListNode<T>* SList<T>::SListFind(T x)
{
	assert(head);
	SListNode<T>* cur = head;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(SListNode<T>* pos, T x)
{
	assert(pos);
	SListNode<T>* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


template <class T>
void SList<T>::SListEraseAfter(SListNode<T>* pos)
{
	assert(pos->next && pos);
	SListNode<T>* cur = pos->next;
	pos->next = pos->next->next;
	delete cur;
}


int main()
{

	SList<int> cur(1);

	cur.SListPushBack(2);
	cur.SListPushBack(3);
	cur.SListPushBack(4);
	cur.SListPushBack(5);
	cur.SListPushBack(6);
	cur.SListPrint();

	cur.SListPopFront();
	cur.SListPrint();

	cur.SListPopBack();
	cur.SListPrint();

	SListNode<int>* p1 = cur.SListFind(2);
	cur.SListInsertAfter(p1, 20);
	cur.SListPrint();

	cur.SListEraseAfter(p1);
	cur.SListPrint();


	
	return 0;
}

二、带头循环链表的实现

带头意味着链表中会一直存在着一个头结点，无论链表的插入还是删除都是对头结点后面的节点进行的操作。头插的节点也是直接连接在头结点的下一个结点，不会改变头结点。循环意味着尾节点的next指针指向头节点，就像是形成了一个环一样。

具体实现代码如下：

#include <iostream>
#include <assert.h>

using namespace std;

template <class T>
struct Node
{
	T data;
	struct Node* next;
	Node()
	{
		this->data = 0;
		this->next = nullptr;
	}
	Node(T data)
	{
		this->data = data;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	Node<T>* head;
	Node<T>* tail;
public:
	SList()
	{
		this->head = new Node<T>();
		this->tail = head;
	}

	~SList()
	{
		Node<T>* p = head;
		Node<T>* q = head;
		while (p != tail)
		{
			q = p->next;
			delete p;
			p = q;
		}
		delete tail;
	}

	
	// 动态申请一个节点
	Node<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	Node<T>* SListFind( T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(Node<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(Node<T>* pos);

};

template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
	Node<T>* tmp = new Node<T>;
	tmp->data = x;
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	assert(head->next);//保证头节点后还有结点才打印，不然报错
	Node<T>* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << "->";
		cur = cur->next;
	}
	cout << "NULL" << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	Node<T>* newnode = BuySListNode(x);
	tail->next = newnode;
	tail = newnode;
	tail->next = head;//尾节点的next指向头节点
}

template <class T>
void SList<T>::SListPushFront(T x)
{
	Node<T>* newnode = BuySListNode(x);
	if (head == tail)
	{
		head->next = newnode;
		tail = newnode;
		tail->next = head;
	}
	else
	{
		newnode->next = head->next;
		head->next = newnode;
	}
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head->next);
	Node<T>* cur = head;
	while (cur->next != tail)
	{
		cur = cur->next;
	}
	delete tail;
	tail = cur;
	tail->next = head;

}

template <class T>
void SList<T>::SListPopFront()
{
	assert(head->next);
	Node<T>* cur = head->next;

	if (head->next == tail)
	{
		delete tail;
		tail = head;
	}
	else
	{
		head->next = cur->next;
		delete cur;
	}
}

template <class T>
Node<T>* SList<T>::SListFind(T x)
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
	assert(pos);
	if (pos->next == head)
	{
		SListPushBack(x);
	}
	else if(pos == head)
	{
		SListPushFront(x);
	}
	else
	{
		Node<T>* newnode = BuySListNode(x);
		newnode->next = pos->next;
		pos->next = newnode;
	}
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
	assert(pos);
	//尾节点后的头节点不能删
	if (pos->next == head)
	{
		exit(-1);
	}
	else if (pos == head)
	{
		SListPopFront();
	}
	else
	{
		Node<T>* cur = pos->next;
		pos->next = pos->next->next;
		delete cur;
	}
}


int main()
{

	SList<int> SL1;
	SL1.SListPushBack(1);
	SL1.SListPushBack(2);
	SL1.SListPushBack(3);
	SL1.SListPushBack(4);
	SL1.SListPushBack(5);
	SL1.SListPrint();

	SL1.SListPushFront(10);
	SL1.SListPrint();

	SL1.SListPopFront();
	SL1.SListPrint();

	SL1.SListPopBack();
	SL1.SListPrint();

	Node<int>* cur = SL1.SListFind(2);
	SL1.SListInsertAfter(cur, 20);
	SL1.SListPrint();

	SL1.SListEraseAfter(cur);
	SL1.SListPrint();

	return 0;
}

三、带头双向循环链表的实现

具体实现思路与带头循环链表大同小异，只是在节点中需要增加一个指向前一个节点的指针。

具体实现代码如下：

#include <iostream>
#include <assert.h>

using namespace std;

template <class T>
struct Node
{
	T data;
	struct Node* prev;//指向前一个节点的指针
	struct Node* next;
	Node()
	{
		this->data = 0;
		this->prev = nullptr;
		this->next = nullptr;
	}
	Node(T data)
	{
		this->data = data;
		this->prev = nullptr;
		this->next = nullptr;
	}
};

template <class T>
class SList
{
private:
	Node<T>* head;//头节点
	Node<T>* tail;//尾节点
public:
	SList()
	{
		this->head = new Node<T>();
		head->next = nullptr;
		head->prev = nullptr;
		this->tail = head;
	}

	~SList()
	{
		Node<T>* p = head;
		Node<T>* q = head;
		while (p != tail)
		{
			q = p->next;
			delete p;
			p = q;
		}
		delete tail;
	}

	Node<T>* getHead()
	{
		return this->head;
	}

	// 动态申请一个节点
	Node<T>* BuySListNode(T x);

	// 单链表打印
	void SListPrint();

	// 单链表尾插
	void SListPushBack(T x);

	// 单链表的头插
	void SListPushFront(T x);

	// 单链表的尾删
	void SListPopBack();

	// 单链表头删
	void SListPopFront();

	// 单链表查找
	Node<T>* SListFind(T x);

	// 单链表在pos位置之后插入x
	void SListInsertAfter(Node<T>* pos, T x);

	// 单链表删除pos位置之后的值
	void SListEraseAfter(Node<T>* pos);

};

template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
	Node<T>* tmp = new Node<T>;
	tmp->data = x;
	tmp->prev = nullptr;
	tmp->next = nullptr;
	return tmp;
}

template <class T>
void SList<T>::SListPrint()
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << "<->";
		cur = cur->next;
	}
	cout << endl;
}

template <class T>
void SList<T>::SListPushBack(T x)
{
	Node<T>* newnode = BuySListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	tail = newnode;
	tail->next = head;
	head->prev = tail;
}

template <class T>
void SList<T>::SListPushFront(T x)
{
	Node<T>* newnode = BuySListNode(x);
	if (head == tail)//头节点后没有节点
	{
		head->next = newnode;
		newnode->prev = head;
		tail = newnode;
		tail->next = head;
		head->prev = tail;
	}
	else
	{
		newnode->next = head->next;
		newnode->prev = head;
		head->next = newnode;
	}
}

template <class T>
void SList<T>::SListPopBack()
{
	assert(head->next);

	Node<T>* cur = tail->prev;
	head->prev = tail->prev;
	delete tail;
	tail = cur;
	tail->next = head;
	
}


template <class T>
void SList<T>::SListPopFront()
{
	assert(head->next);//只剩头节点不删
	Node<T>* cur = head->next;

	if (head->next == tail)//头节点后只有一个节点
	{
		delete tail;
		tail = head;
		head->next = head;
		head->prev = head;
	}
	else
	{
		head->next = cur->next;
		cur->next->prev = head;
		delete cur;
	}
}

template <class T>
Node<T>* SList<T>::SListFind(T x)
{
	assert(head->next);
	Node<T>* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return nullptr;
}

template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
	assert(pos);
	if (pos->next == head)
	{
		SListPushBack(x);
	}
	else if (pos == head)
	{
		SListPushFront(x);
	}
	else
	{
		Node<T>* newnode = BuySListNode(x);
		newnode->next = pos->next;
		newnode->prev = pos;
		pos->next = newnode;
	}
}


template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
	assert(pos);
	if (pos->next == head)//尾节点后的头节点不删
	{
		exit(-1);
	}
	else if (pos == head)
	{
		SListPopFront();
	}
	else
	{
		Node<T>* cur = pos->next;
		pos->next = pos->next->next;
		pos->next->prev = pos;
		delete cur;
	}
}


int main()
{
	//SListNode<int>* head = new SListNode<int>;

	SList<int> SL1;
	SL1.SListPushBack(1);
	SL1.SListPushBack(2);
	SL1.SListPushBack(3);
	SL1.SListPushBack(4);
	SL1.SListPushBack(5);
	SL1.SListPrint();

	SL1.SListPushFront(10);
	SL1.SListPrint();

	SL1.SListPopFront();
	SL1.SListPrint();

	SL1.SListPopBack();
	SL1.SListPrint();

	Node<int>* cur = SL1.SListFind(2);
	SL1.SListInsertAfter(cur, 20);
	SL1.SListPrint();

	SL1.SListEraseAfter(cur);
	SL1.SListPrint();

	return 0;
}

文章来源地址https://uudwc.com/A/4rnnM