数据结构-带头双向链表的建立，详细教程_构建空链表(30分),依次完成下述内容(双向链表,且带头结点): (1)使用头插法,插入4

前言

上一篇文章中我们学习了单链表的实现 本节将带大家学习带头双向链表的实现，希望能够对大家有一些帮助，话不多说，直接开干！！

---

---

一、带头双向链表的概念和结构

概念：带头双向链表是一种 带不存储数据的哨兵卫，循环，双向的一种链表结构。它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
特点:

• 在数据结构中具有双向指针
• 插入数据的时候方便找到上一个
• 同样，删除数据的是有也需要考虑前后方向的操作
  

和单链表的比较：

1.无头单向非循环链表：结构简单，但一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。另外，这种结构在笔试中出现很多。。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外，这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。后面我们代码实现了就知道了。

看代码

typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;
1
2
3
4
5
6
7

首先我们定义了一个结构体，结构体里的data被叫做数据域用来存放数据，next是指针域用来存放下一个节点的地址,prev是指针域用来存放上一个节点的地址。

二. 带头双向链表的接口实现

我们要实现如下的一些接口：

// 创建返回链表的头结点.
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
16
17
18
19
20

2.1 打印

*注意：头指针的位置不要轻易的去改动，所以在这定义了一个Cur来代替我们的头指针。
1

代码示例如下

// 单链表打印
void ListPrint(ListNode* pHead)
{
   assert(pHead);
  ListNode* cur=pHead->next;
  while(cur!=pHead) //这个条件很重要的
  {
      printf("%d->",cur->data);
      cur=cur->next;
  }
printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2 初始化

• 注意：带头双向链表的初始化 需要创建一个哨兵卫的头指针，该位置不存储有效数据 。

// 创建返回链表的头结点.
ListNode* ListCreate()
{
   ListNode* phead=BuySListNode(-1);
   phead->next=phead;
   phead->prev=phead;
   return phead;
}
1
2
3
4
5
6
7
8

2.3 开辟节点

**当我们插入的时候需要开辟新的节点，而我们有头插、尾插和任意位置插，每次写这些插入的时候都要<br /> 
申请节点，所以我们不妨写一个函数就直接申请节点，后面只需要调用就好了**
1
2

代码实现：

LTDataType* BuySListNode(LTDataType x)
{
    LTDataType* newnode=(LTDataType*) malloc(sizeof(ListNode));
    assert(newnode);
    newnode->data=x;
    newnode->next=NULL;
    newnode->prev=NULL;
    return newnode;
}
1
2
3
4
5
6
7
8
9

2.4 尾部插入节点

要尾插的话，我们首先得要开辟一个结点才能插啊，其次是要找到尾结点，那么如何找到尾结点呢？很简单，一个while循环就搞定了。
代码示例如下：

// 单链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
  	ListNode* newNode = BuySListNode(x);
	// 先不断开原链表，然后新节点连接到链表中
	newNode->prev = pHead->prev;
	newNode->next = pHead;
	newNode->prev->next = newNode;
	pHead->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10

2.5 尾部删除节点

示例代码如下：

void ListPopBack(ListNode* pHead)
{
   assert(pHead);
   %除哨兵结点外，链表为空的时候，就不能再删除了，用assert()
   assert(pHead->next!=pHead);
   
   ListNode* tail=pHead->prev;
   ListNode* tailPrev=tail->prev;
   free(tail);
   tailPrev->next=pHead;
   pHead->next=tailPrev;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.6 头部插入节点

示例代码如下：

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
   ListNode* newnode=BuySListNode( x);
   ListNode* next=pHead->next;
   pHead->next=newnode;
   newnode->next=next;
   newnode->prev=pHead;
   next->prev=newnode;
}
1
2
3
4
5
6
7
8
9
10

2.7 头部删除节点

示例代码如下：

void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  %除哨兵结点外，链表为空的时候，就不能再删除了，用assert()
  assert(pHead->next!=pHead);
  ListNode* next=pHead->next;
   pHead->next=next->next;
   next->next->prev=pHead;
   free(next);
}

1
2
3
4
5
6
7
8
9
10
11

2.8 查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
    assert(pHead);
 ListNode* cur=pHead->next;
  while(cur!=pHead)
  {
      if(cur->data==x)
      {
          return cur;
      }
      cur=cur->next;
  }
 return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.9 在Pos位置前插入

注意：Insert最大的作用是：头插和尾插可以进行复用。
示例代码如下：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
   assert(pos);
    ListNode* newnode=BuySListNode(x);
   ListNode* prev=pos->prev;
   prev->next=newnode;
   newnode->next=pos;
   newnode->prev=prev;
   pos->prev=newnode;
}
1
2
3
4
5
6
7
8
9
10
11

2.10 在Pos位置删除

示例代码如下：

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
   assert(pos);
   ListNode* next=pos->next;
   ListNode* prev=pos->prev;
   prev->next=next;
   next->prev=prev;
   free(pos);
}
1
2
3
4
5
6
7
8
9
10

2.11 销毁链表

示例代码如下：

// 双向链表销毁
void ListDestory(ListNode** pHead)
{
 assert(phead);
  ListNode* cur=(*pHead)->next;
  while(cur!=*pHead)
  {
      ListNode* next=cur->next;
      free(cur);
      cur=next;
  }
   free(*pHead);
   *pHead=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

List.h完整代码：

#pragma once//防止头文件重复包含
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

List.c
完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
// 动态申请一个节点

LTDataType* BuySListNode(LTDataType x)

{
    LTDataType* newnode=(LTDataType*) malloc(sizeof(ListNode));
    assert(newnode);
    newnode->data=x;
    newnode->next=NULL;
    newnode->prev=NULL;
    return newnode;
}


// 创建返回链表的头结点.

ListNode* ListCreate()
{
   ListNode* phead=BuySListNode(-1);
   phead->next=phead;
   phead->prev=phead;
   return phead;
}

// 双向链表销毁

void ListDestory(ListNode** pHead)
{
 assert(phead);
  ListNode* cur=(*pHead)->next;
  while(cur!=*pHead)
  {
      ListNode* next=cur->next;
      free(cur);
      cur=next;
  }
   free(*pHead);
   *pHead=NULL;
}

// 双向链表打印
void ListPrint(ListNode* pHead)
{
    assert(pHead);
  ListNode* cur=pHead->next;
  while(cur!=pHead) //这个条件很重要的
  {
      printf("%d->",cur->data);
      cur=cur->next;
  }
printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
  	ListNode* newNode = BuySListNode(x);
	// 先不断开原链表，然后新节点连接到链表中
	newNode->prev = pHead->prev;
	newNode->next = pHead;
	newNode->prev->next = newNode;
	pHead->prev = newNode;
}
// 双向链表尾删

void ListPopBack(ListNode* pHead)

{
    assert(pHead);
    assert(pHead->next!=pHead);
ListNode* cur=pHead->next;
  while(cur!=pHead)
  {
      ListNode* prev=cur;
      cur=cur->next;
  }
  prev->next=pHead;
  pHead->next=prev;
  free(cur);
}

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
   ListNode* newnode=BuySListNode( x);
   ListNode* next=pHead->next;
   pHead->next=newnode;
   newnode->next=next;
   newnode->prev=pHead;
   next->prev=newnode;
}

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(pHead->next!=pHead);
  ListNode* next=pHead->next;
   pHead->next=next->next;
   next->next->prev=pHead;
   free(next);
}


// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
    assert(pHead);
 ListNode* cur=pHead->next;
  while(cur!=pHead)
  {
      if(cur->data==x)
      {
          return cur;
      }
      cur=cur->next;
  }
 return NULL;
}



// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
   assert(pos);
    ListNode* newnode=BuySListNode(x);
   ListNode* prev=pos->prev;
   prev->next=newnode;
   newnode->next=pos;
   newnode->prev=prev;
   pos->prev=newnode;
}



// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
   assert(pos);
   ListNode* next=pos->next;
   ListNode* prev=pos->prev;
   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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

码字不易，如果觉得内容有用的话，就给博主三连吧！！！