双向链表，添加，删除一个节点_双向链表删除一个节点

---

前言

链表有几种，大致分为：单链表， 双向链表，循环链表，静态链表。这里为大家简单介绍双向链表节点的添加，删除。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、创建双向链表（重命名）

双向链表，即有两个指针，pre 和 next。 其中 pre 可指向当前节点的前一个节点， next 指向当前节点的下一个节点。
将该结构体重命名为 T_Name， PT_Name 便于定义结果体变量。

typedef struct NAME{
	char *name;
	struct NAME *pre;
	struct NAME *next;
}T_Name, *PT_Name;

1
2
3
4
5
6

二、添加一个节点

1.添加头指针：

static PT_Name g_ptNameHead;
1

2.若 头指针为空

ptNew 的 next 要赋值为NULL, 避免其成为野指针。

	PT_Name ptNew
	if(!g_ptNameHead)
	{
		g_ptNameHead = ptNew;
		ptNew->next = NULL;
	}

1
2
3
4
5
6
7

3.若头指针非空

定义一个临时指针 ptTemp 。通过判断 ptTemp->next 来确定是否为结尾的指针，若确定 ptTemp 为结尾节点，就可以在其后添加新节点 ptNew。

ptTemp->next = ptNew; 其中 ptTemp 下一个节点为 ptNew， 且 ptNew 的pre指针，指向 ptTemp 。

		PT_Name ptTemp;

		ptTemp = g_ptNameHead;
		while(ptTemp->next)
		{
			ptTemp = ptTemp->next;
		}
		ptTemp->next = ptNew;
		ptNew->pre   = ptTemp;

1
2
3
4
5
6
7
8
9
10

具体代码如下：

void add_name(PT_Name ptNew)
{
	PT_Name ptTemp;
	if(!g_ptNameHead)
	{
		g_ptNameHead = ptNew;
		ptNew->next = NULL;
	}
	else
	{
		ptTemp = g_ptNameHead;
		while(ptTemp->next)
		{
			ptTemp = ptTemp->next;
		}
		ptTemp->next = ptNew;
		ptNew->pre   = ptTemp;
	}
}

void add_one_name(void)
{
	PT_Name ptNew;
	char *str;
	char name[128];
	printf("enter the name:");
	scanf("%s", name);
	str = malloc(strlen(name) + 1);
	strcpy(str, name);
	
	ptNew = malloc(sizeof(T_Name));
	ptNew->name = str;
	ptNew->next = NULL;
	ptNew->pre  = NULL;
	
	add_name(ptNew);
}
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

三、删除一个节点

要删除某个节点，首先我们要通过名字找到这个节点，再将其删除。

1.找到某节点

若头指针为空，说明不存在节点，就直接返回。
否则 通过 strcmp 函数比较节点的名字，逐个寻找。若名字匹配，则将其节点返回。否则 ptTemp = ptTemp->next; 直到节点为空。

PT_Name get_name(char *name)
{
	PT_Name ptTemp;
	if(!g_ptNameHead)
	{
		return NULL;
	}
	else
	{
		ptTemp = g_ptNameHead;
		while(ptTemp)
		{
			if(0 == strcmp(name, ptTemp->name))
			{
				return ptTemp;
			}
			else
			{
				ptTemp = ptTemp->next;
			}
		}
	}
	return NULL;
}

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

2.将节点从链表中删除

要将一个中间节点删除。例如: 要删除的节点为 ptDel , 前一个节点为 ptPre, 后一个节点为 ptNext.
(1). ptPre 的 next 指针要指向 ptDel 的 next 。
（2）. ptNext 的 pre 指针要指向 ptPre 。
（3），free(ptDel->name); free(ptDel);

void del_name(PT_Name ptDel)
{
	PT_Name ptCur;	
	PT_Name ptPre;	
	PT_Name ptNext;	
	
	if (g_ptNameHead == ptDel)
	{
		g_ptNameHead = ptDel->next;
		/* 释放 */
		return;
	}
	else
	{
		ptCur = g_ptNameHead->next;
		while (ptCur)
		{
			if (ptCur == ptDel)
			{
				/* 从链表中删除 */
				ptPre  = ptCur->pre;
				ptNext = ptCur->next;
				ptPre->next = ptNext;
				if (ptNext)
				{
					ptNext->pre = ptPre;
				}
				break;
			}
			else
			{
				ptCur = ptCur->next;
			}
		}
	}
	free(ptDel->name);
	free(ptDel);
}

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

四. 展示所有的节点

当 ptTemp 为空时，就以结束。

void list_all_name(void)
{
	PT_Name ptTemp = g_ptNameHead;
	int i=0;
	while(ptTemp)
	{
		printf("%02d : %s\n", i++, ptTemp->name);
		ptTemp = ptTemp->next;
	}
}
1
2
3
4
5
6
7
8
9
10

五. 实验效果

---

总结

双向指针并不难，大家要多加理解。