双链表实现

C语言
691 words

双链表

这里的双链表指带头循环双向链表

虽然数据结构本身比较复杂，但是增删查改比较方便，是一个比较独立的数据结构

头文件声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#pragma once
// 带头+双向+循环链表增删查改实现

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<memory.h>
#include<stdbool.h>
#include<math.h>
//常见头文件包含

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;//链表数据
	struct ListNode* next;//指向下一个节点的指针
	struct ListNode* prev;//指向上一个节点的指针
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();


// 双向链表销毁
void ListDestory(ListNode* pHead);

// 双向链表打印
void ListPrint(ListNode* pHead);

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);

// 双向链表尾删
void ListPopBack(ListNode* pHead);

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);

// 双向链表头删
void ListPopFront(ListNode* pHead);

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

具体实现函数

创建节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* ListCreate()
{
 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
 	
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	//这里要注意判断 newnode 是否正确申请空间 否则报错
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

链表打印

1
2
3
4
5
6
7
8
9
10
11
void ListPrint(ListNode* pHead)
{
	ListNode* cur = pHead;
	while (cur->next != pHead)
	{
		if (cur != pHead)
			printf("%d <=> ", cur->data);
		cur = cur->next;
	}
	printf("%d\n", cur->data);
}

链表销毁

1
2
3
4
5
6
7
8
9
10
11
void ListDestory(ListNode* pHead)
{
	ListNode* cur = pHead;
	while (cur->next != pHead)
	{
		ListNode* pre = cur;
		cur = cur->next;
		free(pre);
	}
	free(cur);
}

链表尾插

1
2
3
4
5
6
7
8
9
10
11
void ListPushBack(ListNode* pHead, LTDataType x)
{
	ListNode* newnode = ListCreate();
	ListNode* last = pHead->prev;

	last->next = newnode;
	newnode->prev = last;
	newnode->next = pHead;
	pHead->prev = newnode;
	newnode->data = x;
}

链表尾删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void ListPopBack(ListNode* pHead)
{
	assert(!CheckEmpty(pHead));
	ListNode* last = pHead->prev;
	ListNode* last_before = last->prev;
	last_before->next = pHead;
	pHead->prev = last_before;


	last->data = 0;
	last->next = NULL;
	last->prev = NULL;

	free(last);
}

链表头插

1
2
3
4
5
6
7
8
9
10
11
void ListPushFront(ListNode* pHead, LTDataType x)
{
	ListNode* newnode = ListCreate();

	newnode->next = pHead->next;
	pHead->next->prev = newnode;
	newnode->prev = pHead;
	pHead->next = newnode;

	newnode->data = x;
}

链表头删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ListPopFront(ListNode* pHead)
{
	assert(!CheckEmpty(pHead));
	
	ListNode* first = pHead;
	ListNode* second = pHead->next;
	ListNode* third = pHead->next->next;

	first->next = third;
	third->prev = first;

	second->next = NULL;
	second->prev = NULL;

	free(second);
}

链表查找

1
2
3
4
5
6
7
8
9
10
11
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead;
	while (cur->next != pHead)
	{
		cur = cur->next;
		if (cur->data == x)
			return cur;
	}
	return NULL;
}

链表插入

在pos前插入一个节点，通常配合链表查找一起使用

1
2
3
4
5
6
7
8
9
10
11
12
13
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* newnode = ListCreate();
	newnode->data = x;

	ListNode* first = pos->prev;
	ListNode* second = pos;

	second->prev = newnode;
	newnode->next = second;
	first->next = newnode;
	newnode->prev = first;
}

链表删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ListErase(ListNode* pos)
{
	ListNode* first = pos->prev;
	ListNode* second = pos;
	ListNode* third = pos->next;

	first->next = third;
	third->prev = first;

	second->next = NULL;
	second->prev = NULL;

	free(second);
}

判空

在进行链表删除操作时需要判断链表是否为空

这里只作为内置函数，并不向外部提供函数接口，故不写入头文件中

1
2
3
4
5
6
7
bool CheckEmpty(ListNode* pHead)
{
	if (pHead->next == pHead)
		return true;
	else
		return false;
}
Comments