【数据结构】手撕双向链表

前言

1. 双向链表

带头双向循环链表的结构

2. 链表的实现

2.1 初始化

2.2 尾插

2.3 尾删

2.4 头插

2.5 头删

2.6 在pos位置之前插入

2.7 删除pos位置

3.双向链表完整源码

List.h

List.c

前言

在上一期中我们介绍了单链表，也做了一些练习题，在一些题中使用单链表会十分繁琐。因为单链表只能正着走，不能倒着走，例如：回文、逆置。本期我们将学习带头双向循环链表。

1. 双向链表

带头双向循环链表的结构

特点：带头双向循环链表结构最复杂，一般用在单独存储数据。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来多优势，实现反而简单了。

2. 链表的实现

2.1 初始化

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.2 尾插

带哨兵位的链表尾插时不用判断是否有节点，两种情况的插入相同，而且还不用传递二级指针。

void LTPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* newnode = CreateLTNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}

2.3 尾删

在尾删时我们通过 assert(phead->next != phead); 判断链表是否有节点。同时这个代码就有普遍性，不用单独考虑剩一个节点的情况。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;
}

2.4 头插

头删重要的是赋值的顺序，顺序错误会找不到后面的节点，导致内存泄漏。带哨兵位的链表不需要传递二级指针，因为改变的是结构体的变量。

void LTPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

2.5 头删

我们可以多定义几个指针来保存后面节点的地址，这样就不会造成节点的丢失，不用考虑赋值的顺序，会更加方便。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* tail = phead->next;
	LTNode* next = tail->next;
	phead->next = next;
	next->prev = phead;
	free(tail);
	tail = NULL;
}

2.6 在pos位置之前插入

void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* newnode = CreateLTNode(x);
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

2.7 删除pos位置

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
}

3.双向链表完整源码

List.h

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

typedef int LTDateType;

typedef struct ListNode
{
	LTDateType val;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

LTNode* LTInit();

void LTPrint(LTNode* phead);

void LTPushBack(LTNode* phead, LTDateType x);

void LTPushFront(LTNode* phead, LTDateType x);

void LTPopBack(LTNode* phead);

void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDateType x);

void LTInsert(LTNode* pos, LTDateType x);

void LTErase(LTNode* pos);

void LTDestroy(LTNode* phead);

List.c

#include"List.h"

LTNode* CreateLTNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
}

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("<=>哨兵位<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

void LTPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* newnode = CreateLTNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}

void LTPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* tail = phead->next;
	LTNode* next = tail->next;
	phead->next = next;
	next->prev = phead;
	free(tail);
	tail = NULL;
}

LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
			cur = cur->next;
	}
	return NULL;
}

void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* newnode = CreateLTNode(x);
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}