数据结构--链表_struct listnode* head = (struct listnode*)malloc(s

链表

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

2. 常用的两种链表结构：无头单向非循环链表和带头双向循环链表。
   
   

3. 链表的特点：
   （1）进行插入、删除时，不需要移动表中元素；
   （2）不必事先估计存储空间；
   （3）所需空间与线性表长度成正比。

4. 带头双向循环链表增删查改的实现：

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType x)
{
	struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
	head->_data = x;
	head->_next = head->_prev = NULL;
	return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	struct ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		struct ListNode* next = cur->_next;
		free(cur);
		cur = cur->_next;
	}
	free(pHead);
	pHead = NULL;
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	struct ListNode* cur = pHead->_next;
	while (cur!=pHead)
	{
		printf("%d ", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}
// 双向链表尾插
//tail  node  pHead
void ListPushBack(ListNode* pHead, LTDataType x)
{
	struct ListNode* tail = pHead->_prev;
	struct ListNode* node = ListCreate(x);
	tail->_next = node;
	node->_prev = tail;
	pHead->_prev = node;
	node->_next = pHead;
}
// 双向链表尾删
//prev tail pHead
void ListPopBack(ListNode* pHead)
{
	if (pHead->_prev == pHead)
		return;
	struct ListNode* tail = pHead->_prev;
	struct ListNode* prev = tail->_prev;
	free(tail);
	prev->_next = pHead;
	pHead->_prev = prev;
}
// 双向链表头插
// pHead node next
void ListPushFront(ListNode* pHead, LTDataType x)
{
	struct ListNode* node = ListCreate(x);
	struct ListNode* next = pHead->_next;
	pHead->_next = node;
	node->_prev = pHead;
	next->_prev = node;
	node->_next = next;
}
// 双向链表头删
//pHead prev next
void ListPopFront(ListNode* pHead)
{
	if (pHead->_prev == pHead)
		return;
	struct ListNode* prev = pHead->_next;
	struct ListNode* next = prev->_next;
	free(prev);
	pHead->_next = next;
	next->_prev = pHead;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	if (pHead->_prev == pHead)
		return NULL;
	struct ListNode* head = pHead;
	while (pHead->_data != x)
	{
		pHead = pHead->_next;
		if (pHead->_next = head)
			return NULL;
	}
	return pHead;
}
// 双向链表在pos的前面进行插入
//prev node pos
void ListInsert(ListNode* pos, LTDataType x)
{
	struct ListNode* node = ListCreate(x);
	struct ListNode* prev = pos->_prev;
	prev->_next = node;
	node->_prev = prev;
	node->_next = pos;
	pos->_prev = node;
}
// 双向链表删除pos位置的节点
//prev pos next
void ListErase(ListNode* pos)
{
	struct ListNode* prev = pos->_prev;
	struct ListNode* next = pos->_next;
	prev->_next = next;
	next->_prev = prev;
	free(pos);
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122