【数据结构】单链表&带头双向循环链表的实现

一、链表的概念及结构

1.链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2.链表的结构

一般讲的链表包括数据域和指针域：

二、链表的种类

实际中链表的结构非常多样，由以下三组类型自由组合可得8种链表结构：

1.单向、双向：

2.带头、不带头：

3.循环、非循环：

虽然有这么多类型，但我们最长使用的就是以下两种：

在此我们只实现这两种链表

三、单链表的实现

1.自定义链表结点struct SListNode

typedef int SLTDateType; typedef struct SListNode { 	SLTDateType data; 	struct SListNode* next; }SListNode;

2.链表打印数据SListPrint

//打印 void SListPrint(SListNode* plist) { 	if (plist == NULL) 		return;  	while (plist) 	{ 		printf("%d->", plist->data); 		plist = plist->next; 	} }

3.链表创建结点BuyListNode

//创建节点 SListNode* BuySListNode(SLTDateType x) { 	SListNode* new_node = (SListNode*)malloc(sizeof(SListNode)); 	if (new_node == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	} 	new_node->data = x; 	new_node->next = NULL; 	return new_node; }

4.链表尾部插入数据SListPushBack

//尾插 void SListPushBack(SListNode** pplist, SLTDateType x) { 	//无节点 	if (*pplist == NULL) 	{ 		(*pplist) = BuySListNode(x); 	}  	//有节点 	SListNode* tail = *pplist; 	while (tail->next) 	{ 		tail = tail->next; 	} 	tail->next = BuySListNode(x); }

5.链表头部插入数据SListPushFront

//头插 void SListPushFront(SListNode** pplist, SLTDateType x) { 	SListNode* new_node = BuySListNode(x); 	new_node->next = *pplist; 	*pplist = new_node; }

6.链表尾部删除数据SListPopBack

//尾删 void SListPopBack(SListNode** pplist) { 	//空链表 	if ((*pplist) == NULL) 		return;  	//一个节点 	if ((*pplist)->next == NULL) 	{ 		SListNode* tmp = *pplist; 		free(tmp); 		tmp = NULL; 	}  	//多个节点  	else 	{ 		SListNode* cur = *pplist; 		SListNode* next = cur->next;  		//找尾 		while (cur->next->next) 		{ 			cur = next; 			next = next->next; 		} 		free(next); 		cur->next = NULL; 	}  }

7.链表头部删除数据SListPopFront

//头删 void SLPopFront(SListNode** pplist) { 	//没有节点 	if ((*pplist) == NULL) 		return;  	//一个节点 	//多个节点 	SListNode* tmp = *pplist; 	*pplist = (*pplist)->next; 	free(tmp); 	tmp = NULL; }

8.链表查找数据

//查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { 	SListNode* cur = plist; 	while (cur) 	{ 		if (cur->data == x) 		{ 			return cur; 		} 		cur = cur->next; 	} 	return NULL; }

9.链表在pos位置之后插入数据

// 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x) { 	SListNode* newnode = BuySListNode(x); 	//在非尾节点插入 	if (pos->next != NULL) 	{ 		newnode->next = pos->next; 		pos->next = newnode; 	} 	else 	{ 		SListPushBack(&pos, x); 	} }

10.删除pos位置之后的值

// 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos) { 	if (pos->next == NULL) 	{ 		printf("erroe"); 		return; 	} 	SListNode* del = pos->next; 	pos->next = del->next; 	free(del); 	del = NULL; }

11.销毁链表

//销毁链表 void SLTDestroy(SListNode** pphead) { 	if (*pphead == NULL) 		return; 	SListNode* next = (*(pphead))->next; 	while (*pphead) 	{ 		//销毁 		SListNode* del = *pphead; 		free(del); 		del = NULL;  		//迭代 		*pphead = next; 		if(next) 		next = next->next; 	} }

四.带头双向循环链表的实现

1.自定义链表结点 ListNode

typedef int LTDataType; typedef struct ListNode { 	LTDataType _data; 	struct ListNode* _next; 	struct ListNode* _prev; }ListNode;

2.创建新节点

 //创建新节点 ListNode* BuyLTNode(LTDataType x) { 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); 	if (newnode == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	} 	newnode->_data = x; 	newnode->_next = NULL; 	newnode->_prev = NULL;  	return newnode; }

3.创建一个新链表，返回头结点

// 创建返回链表的头结点. ListNode* ListCreate() { 	ListNode* Phead = BuyLTNode(-1); 	Phead->_next = Phead; 	Phead->_prev = Phead;  	return Phead; }

4.打印链表

//打印链表 void ListPrint(ListNode* pHead) { 	if (pHead == NULL) 		return; 	ListNode* cur = pHead->_next; 	printf("pHead <=> "); 	while (cur!=pHead) 	{ 		printf("%d <=> ", cur->_data); 		cur = cur->_next; 	} }

5.在pos之前插入值为x节点

//在pos前插入 void ListInsert(ListNode* pos, LTDataType x) { 	ListNode* pre = pos->_prev; 	ListNode* newnode = BuyLTNode(x); 	newnode->_next = pos; 	pos->_prev = newnode; 	pre->_next = newnode; 	newnode->_prev = pre; }

6.尾插

//尾插 void ListPushBack(ListNode* pHead, LTDataType x) { 	ListInsert(pHead,  x); }

7.头插

//头插 void ListPushFront(ListNode* pHead, LTDataType x) { 	ListInsert(pHead->_next, x); }

8.删除pos位置节点

//删除pos位置的节点 void ListErase(ListNode* pos) { 	ListNode* pre = pos->_prev; 	ListNode* next = pos->_next; 	free(pos); 	pos = NULL; 	pre->_next = next; 	next->_prev = pre; }

9.双向链表头删

// 双向链表头删 void ListPopFront(ListNode* pHead) { 	ListErase(pHead->_next); }

10.双向链表尾删

// 双向链表尾删 void ListPopBack(ListNode* pHead) { 	ListErase(pHead->_prev); }

11.查找

// 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { 	ListNode* cur = pHead->_next; 	while (cur != pHead) 	{ 		if (cur->_data == x) 			return cur;  		cur = cur->_next; 	} 	return NULL; } 

12.销毁链表

//销毁链表 void ListDestory(ListNode* pHead) { 	ListNode* cur = pHead->_next; 	while (cur) 	{ 		ListNode* next = cur->_next; 		free(cur); 		pHead->_next = next; 		cur = next;  	} }

注：带头双向循环链表的头插头删，尾插尾删直接复用了插入删除代码。