【 声明：版权所有，欢迎转载。 联系信箱：yiluohuanghun@gmail.com】
自之前写的两篇关于“数据结构与算法”的博文发表以后，就有两个博友发私信给我探讨我的这个分类，有博友说数据结构怎么能和算法在一起呢？其实吧，我倒感觉数据结构跟算法的关系就好比好基友是一辈子的关系。他们患难见真情、他们生死不相弃……事实上，数据结构和算法也有类似的关系。只谈数据结构，我们可以在很短的时间内就把几种重要的数据结构介绍完。不过听完后，你可能没啥感觉，不知道这些数据结构有啥用处。但如果我们把相应的算法结合起来讲一讲，演示一下，你就会发现，甚至开始感慨：原来解决计算机问题是如此的美妙！
这篇文章我主要聊一下双向链表。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构：
双向链表通常采用带表头结点的循环链表形式。
其通常的数据结构如下：
|
1
2
3
4
5
6
|
typedef
struct
_DOUBLE_LINK_NODE
{
int
data;
struct
_DOUBLE_LINK_NODE *prev;
struct
_DOUBLE_LINK_NODE *next;
};
|
链表中的每个结点至少有三个域：一个双向链表有一个表头结点，由链表的表头指针first指示，它的data域或者不放数据，或者存放一个特殊要求的数据；它的lLink指向双向链表的最后一个结点，它的lLink指向双向链表的最前端的第一个结点。
结点指向 p == p→lLink→rLink == p→rLink→lLink
有很多人不解，为何要有双向链表的存在呢？下面我们可以再看一幅图：
这货我们叫它火车，我记得我第一次做火车的时候遇到过一个现象，就是火车正在往前走，到达一个站后，又往后走了一站，但是当时让我吃惊的是为什么火车并没有掉头就能往回走，在后来我才明白原来是火车是两个头都可以连接火车头的，这也许就是一个最简单的双向链表的实例吧。
双向链表的插入操作
说起插入操作相对于单链表而言要稍微复杂一点，我们要做的第一步就是找到要插入的位置，而后将带插入的结点的后驱指向当前结点的后驱，将插入结点的前驱指向当前结点。将当前结点的后驱重新指向带插入结点，当前结点的后驱结点的前驱指向待插入结点，是不是听起来有点太绕了？没关系！用图来说明问题吧：
|
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
|
代码如下：
//创建双向链表节点
_DOUBLE_LINK_NODE *CreateDoubleLink(
int
data)
{
_DOUBLE_LINK_NODE *head =
(_DOUBLE_LINK_NODE *)
malloc
(
sizeof
(_DOUBLE_LINK_NODE));
ASSERT(head != NULL);
head->data = data;
head->prev = NULL;
head->next = NULL;
return
head;
}
//双向链表中插入数据
int
insert_data_into_double_link
(_DOUBLE_LINK_NODE** ppDLinkNode,
int
data)
{
_DOUBLE_LINK_NODE* pNode;
_DOUBLE_LINK_NODE* pIndex;
if
(NULL == ppDLinkNode)
return
0;
if
(NULL == *ppDLinkNode){
pNode = CreateDoubleLink
(data);
ASSERT(NULL != pNode);
*ppDLinkNode = pNode;
(*ppDLinkNode)->prev =
(*ppDLinkNode)->next = NULL;
return
1;
}
if
(NULL != find_data_in_double_link
(*ppDLinkNode, data))
return
FALSE;
pNode = CreateDoubleLink(data);
ASSERT(NULL != pNode);
pIndex = *ppDLinkNode;
while
(NULL != pIndex->next)
pIndex = pIndex->next;
pNode->prev = pIndex;
pNode->next = pIndex->next;
pIndex->next = pNode;
return
1;
}
|
双向链表的删除操作，其实我们掌握了插入操作以后，对于别的删除、查找操作就相对来说要容易的多了，那就直接上代码了：
|
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
|
//双向链表中删除数据
int
delete_data_from_double_link
(_DOUBLE_LINK_NODE** ppDLinkNode,
int
data)
{
_DOUBLE_LINK_NODE* pNode;
if
(NULL == ppDLinkNode || NULL ==
*ppDLinkNode)
return
0;
pNode = find_data_in_double_link
(*ppDLinkNode, data);
if
(NULL == pNode)
return
0;
if
(pNode == *ppDLinkNode){
if
(NULL == (*ppDLinkNode)-
>next){
*ppDLinkNode =
NULL;
}
else
{
*ppDLinkNode =
pNode->next;
(*ppDLinkNode)-
>prev = NULL;
}
}
else
{
if
(pNode->next)
pNode->next->prev =
pNode->prev;
pNode->prev->next = pNode->next;
}
free
(pNode);
return
1;
}
//在双向链表中查找数据
_DOUBLE_LINK_NODE* find_data_in_double_link
(
const
_DOUBLE_LINK_NODE* pDLinkNode,
int
data)
{
_DOUBLE_LINK_NODE* pNode = NULL;
if
(NULL == pDLinkNode)
return
NULL;
pNode = (_DOUBLE_LINK_NODE*)
pDLinkNode;
while
(NULL != pNode){
if
(data == pNode->data)
return
pNode;
pNode = pNode ->next;
}
return
NULL;
}
//统计双向链表中数据的个数
int
count_number_in_double_link(
const
_DOUBLE_LINK_NODE* pDLinkNode)
{
int
count = 0;
_DOUBLE_LINK_NODE* pNode =
(_DOUBLE_LINK_NODE*)pDLinkNode;
while
(NULL != pNode){
count ++;
pNode = pNode->next;
}
return
count;
}
//打印双向链表中数据
void
print_double_link_node(
const
_DOUBLE_LINK_NODE* pDLinkNode)
{
_DOUBLE_LINK_NODE* pNode =
(_DOUBLE_LINK_NODE*)pDLinkNode;
while
(NULL != pNode){
printf
(
"%d\n"
, pNode->data);
pNode = pNode ->next;
}
}
|
基本的操作也就这么多了，当然了，对于我们自己写程序来说一定要记得写测试程序，这个是非常非常重要的。
本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/1262417，如需转载请自行联系原作者
