数据结构笔记第3篇：双向链表

1、双向链表的结构

注意：这里的 "带头" 跟前面我们说的 "头结点" 是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点，实际为 "哨兵位" ，哨兵位节点不存储任何有效元素，只是站在这里 "放哨的"。

"哨兵位" 存在的意义：

遍历循环链表避免死循环。

注意：双向链表中，哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。

哨兵位是作为头结点和尾结点的中点，是头结点的起点也是尾节点的终点。这样解释更容易理解。

2、双向链表的实现

List.h 链表函数和链表节点类型的声明：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;
typedef struct ListNode
{
	SLDataType data;//存储数据
	struct ListNode* prve;//存储前一个节点的地址
	struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();

void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁

List.c 链表函数的实现:

#include "List.h"
//链表初始化
SList* SLInit()
{
	SList* phead = (SList*)malloc(sizeof(SList));
	if (phead == NULL)
	{
		perror("malloc error");
		return NULL;
	}
	phead->data = -1;
	//因为是循环链表，所以初始化要遵循循环格式
	phead->next = phead;
	phead->prve = phead;
	return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{
	SList* retNode = (SList*)malloc(sizeof(SList));
	if (retNode == NULL)
	{
		perror("malloc error");
		return NULL;
	}
	retNode->data = x;
	retNode->prve = retNode;
	retNode->next = retNode;
	return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{
	assert(phead);
	SList* Node = ListBuyNode(x);
	Node->prve = phead->prve;
	Node->next = phead;
	phead->prve->next = Node;
	phead->prve = Node;
}
//链表数据显示
void SLPrint(SList* phead)
{
	assert(phead);
	SList* pcur = phead->next;
	while (pcur != phead)//哨兵位作为结束标识
	{
		printf("%d", pcur->data);
		if (pcur->next != phead)
			printf("->");
		pcur = pcur->next;
	}
	printf("\n");
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{
	assert(phead);
	SList* Node = ListBuyNode(x);
	Node->next = phead->next;
	Node->prve = phead;
	phead->next->prve = Node;
	phead->next = Node;
}
//链表尾删
void SLPopBack(SList* phead)
{
	assert(phead);
	assert(phead->next != phead);
	SList* del = phead->prve;
	del->prve->next = phead;
	phead->prve = del->prve;
	free(del);
	del = NULL;
}
//链表头删
void SLPopFront(SList* phead)
{
	assert(phead);
	assert(phead->next != phead);
	SList* del = phead->next;
	del->next->prve = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{
	assert(pos);
	SList* Node = ListBuyNode(x);
	Node->next = pos->next;
	Node->prve = pos;
	pos->next = Node;
	Node->next->prve = Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{
	assert(phead);
	SList* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{
	assert(pos);
	pos->prve->next = pos->next;
	pos->next->prve = pos->prve;
	free(pos);
	pos = NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{
	assert(pphead && *pphead);
	SList* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		SList* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(*pphead);
	*pphead = NULL;
}

test.c 函数的调用:

#include "List.h"

void SLtest()
{
	SList* plist = NULL;
	plist = SLInit();
	//尾插
	SLPushBack(plist, 1);
	SLPushBack(plist, 2);
	SLPushBack(plist, 3);
	SLPushBack(plist, 4);
	SLPrint(plist);//打印:1->2->3->4
	//头插
	SLPustFront(plist, 5);
	SLPustFront(plist, 6);
	SLPustFront(plist, 7);
	SLPrint(plist);//打印:7->6->5->1->2->3->4
	//尾删
	SLPopBack(plist);
	SLPrint(plist);//打印:7->6->5->1->2->3
	//头删
	SLPopFront(plist);
	SLPrint(plist);//打印:6->5->1->2->3
	//指定位置插入
	SList* find = SLfind(plist, 5);
	SLInsert(find, 11);
	SLPrint(plist);//打印:6->5->11->1->2->3
	//指定位置删除
	find = SLfind(plist, 1);
	SLEarse(find);
	SLPrint(plist);//打印:6->5->11->2->3
	//链表销毁
	SLDestory(&plist);
}
int main()
{
	SLtest();
	return 0;
}

3、顺序表和双向链表的优缺点分析

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁