数据结构基础——双向链表

什么是双向链表

首先，双向链表一样是链表，逻辑上存储连续，物理上存储不连续。但是相对于单链表每个结点存储两个数据（data 数据 next 下一个结点的地址），双向链表每个结点存储三个数据，比普通链表多 prior 储存上一结点的地址。

双向链表的每个结点除了存储后一个结点的地址，还需要存储前一个结点的地址。 – 从前向后遍历和从后向前遍历

双向链表的实现

1、结构的声明

typedef   double  DataType;

typedef  struct Node
{
    union{
        int   length;
        DataType   data;
    };
    
    struct Node *prior;
    struct Node  *next;
}DoubleList;
1
2
3
4
5
6
7
8
9
10
11
12

在结构声明中使用 union 可以令头结点存储链表长度而不影响后续的结点

2、方法的声明

// 初始化
void  InitDoubleList(DoubleList *head);

//按位置插入
bool  InsertDoubleList(DoubleList *head, DataType value, int pos);

void ShowDoubleList(DoubleList *head);

bool  DeleteDoubleList(DoubleList *head, int pos);

void DestroyDoubleList(DoubleList *head);
1
2
3
4
5
6
7
8
9
10
11

3、方法的实现

双链表的初始化

void  InitDoubleList(DoubleList *head)
{
	if (head == NULL)  exit(0);

	head->length = 0;
	head->next = head->prior = NULL;
}
1
2
3
4
5
6
7

初始化一个链表 给 length赋值0 令next和prior指向NULL

给双链表插入数据

bool  InsertDoubleList(DoubleList *head, DataType value, int pos)
{
//传入参数分别为 双向链表指针 插入数据 插入位置
	if (head == NULL)   exit(0);

	if (pos < 0 || pos > head->length)  return false;

	DoubleList *p = head;

	while (pos)
	{
		p = p->next;
		pos--;
	}

	// while循环结束后，需要在p的后面插入新结点

	DoubleList *new_node = ApplyNode(value, p, p->next);//这里引用新的函数
	if (new_node == NULL)  return  false;

	//  p已经是尾结点了，在P的后面插入新结点
	if (p->next != NULL)   p->next->prior = new_node;
	
	p->next = new_node;

	head->length++;

	return true;
}

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

上面代码中 最后几句 首先判断p->是否为空，若为空则p为尾结点

不为空时： 先将p->next的前驱结点指向新结点 new_node 。
再让p->指向new_node。
这样就能将 new_node 完美插入到p与p->next之间。

为空时： 直接令p->指向new_node即可。
然后head->length++ 头结点存储的长度加一

创建一个新的结点 插入p与p->next之间 使得成为新的p->next

static DoubleList *ApplyNode(DataType value, DoubleList *prior, DoubleList *next)
{
	DoubleList *new_node = (DoubleList*)malloc(sizeof(DoubleList));
	if (new_node == NULL)  return NULL;

	new_node->data = value;
	new_node->next = next;
	new_node->prior = prior;

	return new_node;
}
1
2
3
4
5
6
7
8
9
10
11

ShowDoubleList

void ShowDoubleList(DoubleList *head)
{
	if (head == NULL) exit(0);

	DoubleList *p = head->next;
	printf("正向： ");
	while (p->next != NULL)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	printf("%d\n", p->data);

	printf("逆向： ");
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->prior;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

while循环从头结点打印至尾结点即可 逆向同理。

删除结点
传入参数分别为 链表 删除位置

与插入相同 利用while循环寻找到需要删除的结点为 p->next 结点

令需要删除的结点为 q： ** DoubleList *q =p->next **

首先判断需要删除结点是否为尾结点

若不是尾结点： 使得q结点的后继指向 p ，即 q 结点的前驱 随后令p->next 等于q->next, 即 q前驱的next 指向 q的next

若是尾结点： 直接令 p 的 next 指向 q->next,即NULL
但为代码的简洁高效，下面的代码为：q->next=q->next；

随后释放q的内存空间，并且令head->length–（一定不要忘记！）

bool  DeleteDoubleList(DoubleList *head, int pos)
{
	if (head == NULL) exit(0);

	// 判断pos是否合法
	if (pos < 0 || pos >= head->length) return false;

	DoubleList *p = head;

	while (pos)
	{
		p = p->next;
		pos--;
	}

	// while循环结束后，需要删除的是p的next结点。
	DoubleList *q = p->next;
	if(q->next != NULL) q->next->prior = p;
	p->next = q->next;
	free(q);
	head->length--;

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

销毁双向链表
循环判断头结点next是否为空，调用删除结点函数

void DestroyDoubleList(DoubleList *head)
{
	if (head == NULL) exit(0);

	while (head->next != NULL)
	{
		DeleteDoubleList(head, 0);
	}
}
1
2
3
4
5
6
7
8
9

双向循环链表

如图，将原本双向链表的尾结点next指向头结点地址，头结点的prior指向尾结点的地址。

1、结构声明

typedef   double  DataType;

typedef  struct Node
{
    union{
        int   length;
        DataType   data;
    };
    
    struct Node *prior;
    struct Node  *next;
}DoubleCycleList;
1
2
3
4
5
6
7
8
9
10
11
12

2、方法的实现

void InitDoubleCycleList(DoubleCycleList *head);

bool InsertDoubleCycleList(DoubleCycleList *head, DataType value, int pos);

bool InsertDoubleCycleListHead(DoubleCycleList *head, DataType value);

bool InsertDoubleCycleListRear(DoubleCycleList *head, DataType value);

bool DeleteDoubleCycleList(DoubleCycleList *head, int pos);

bool DeleteDoubleCycleListRear(DoubleCycleList *head);
1
2
3
4
5
6
7
8
9
10
11

3、方法的实现

static DoubleCycleList *ApplyNode(DataType value, DoubleCycleList *prior, DoubleCycleList *next)
{
	DoubleCycleList *new_node = (DoubleCycleList*)malloc(sizeof(DoubleCycleList));
	if (new_node == NULL) return NULL;

	new_node->data = value;
	new_node->prior = prior;
	new_node->next = next;
	
	return new_node;
}

//  在当前节点now后面插入一个新的数据结点
static bool InsertNodeAfter (DoubleCycleList *now, DataType value)
{
	DoubleCycleList *new_node = ApplyNode(value, now, now->next);
	if (new_node == NULL) return false;

	now->next->prior = new_node;
	now->next = new_node;

	return true;
}

void InitDoubleCycleList(DoubleCycleList *head)
{
	if (head == NULL) exit(0);

	head->length = 0;
	head->prior = head->next = head;
}

bool InsertDoubleCycleList(DoubleCycleList *head, DataType value, int pos)
{
	if (head == NULL) exit(0);

	if (pos < 0)  return false;

	pos %= (head->length + 1);

	DoubleCycleList *p = head;

	while (pos)
	{
		p = p->next;
		pos--;
	}

	// while循环结束后，在p的后面插入新结点
	if (InsertNodeAfter(p, value))
	{
		head->length++;
		return true;
	}

	return false;
}

bool InsertDoubleCycleListHead(DoubleCycleList *head, DataType value)
{
	return InsertDoubleCycleList(head, value, 0);
}

bool InsertDoubleCycleListRear(DoubleCycleList *head, DataType value)
{
	if (head == NULL) exit(0);

	DoubleCycleList *p = head->prior;  // p就是最后一个结点

	if (InsertNodeAfter(p, value))
	{
		head->length++;
		return true;
	}

	return false;
}

bool DeleteDoubleCycleList(DoubleCycleList *head, int pos)
{
	if (head == NULL)  exit(0);
	
	if (pos < 0 || head->length == 0) return false;

	pos %= head->length;

	DoubleCycleList *p = head;

	while (pos)
	{
		p = p->next;
		pos--;
	}

	DoubleCycleList *q = p->next;

	q->next->prior = p;
	p->next = q->next;
	free(q);
	head->length--;

	return true;
}

bool DeleteDoubleCycleListRear(DoubleCycleList *head)
{
	if (head == NULL) exit(0);

	if (head->length == 0)  return false;

	DoubleCycleList *p = head->prior; // p就是要删除的节点

	p->prior->next = p->next;
	p->next->prior = p->prior;

	free(p);
	head->length--;
	return true;
}
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

方法的实现与双向链表基本一致，只需要注意头尾结点以及按位删除或插入需要按余数进行查找。