双向循环链表_双向链表头尾相接吗

双向循环链表是一种较为特殊的链表，也是一种常见的数据结构，其头尾相连，各节点之间可互相访问，在单链表中，只能依次向后访问，无法访问上一个节点，而双链表可以依次向下访问也可向上访问。

链表形式

双链表有很多节点形象的依次连接在一起，每个节点都由一个数据域和两个指针域构成，尾指针存放着下一个节点的地址，头指针存放着上一个节点的地址，故而形象的使各个节点依次相连。

插入一个节点：

在1、3节点之间插入节点2，1节点尾指针原本指向3节点，改变其指向，使之指向2节点，2节点的头指针便指向1节点，同理，改变3节点的头指针指向，使之指向2节点，2节点的尾指针指向3节点。

删除一个节点

例如删除2节点，只需将原3（现2节点）节点的地址赋给1节点的尾指针中，3节点的头指针指向1，再将原2（即删除的节点）节点的指针域释放掉即可

头插

循环双链表的链表头一般没有数据，且一般保持这个位置不动，所以访问数据是从第二个节点开始，如果在链表头后一直插入数据，则第二个节点一直都是新数据，所以其实是对双链表进行的是前插操作。

尾插

如果在链表头插入新数据，那么出现在链表头前面的都是新数据，所以和插在链表尾是一个道理，因为双向循环链表是首尾相连的。

具体代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h> 

typedef struct ListNode
{
    struct ListNode  *front;
    int data;
    struct ListNode* next;
}ListNode;

typedef struct List
{
    ListNode *head;
}List;
 
void init(List* plist)//初始化
{
    //分配空间
    plist->head =(ListNode*)malloc(sizeof(ListNode));
    
    //让头指针和尾指针都指向自己
    plist->head->front= plist->head;
    plist->head->next= plist->head;
}

int  data_num(List*  plist)//检查链表节点个数
{
    ListNode* tem;
    int  i = 0;
    for (tem =plist->head->next; tem != plist->head; tem = tem->next)
    {
        i++;
    }
    return i;//返回链表节点个数
}

void insert_front(ListNode*  plist, intdata)     //链表头前插
{
    //分配空间
    ListNode* cur =(ListNode*)malloc(sizeof(ListNode));
    
    //记录链表头尾指针的内容,存放的是一个节点的地址，即tem临时充当这个节点
    ListNode* tem =plist->next;
    cur->data = data;
    plist->next = cur;
//使链表头的尾指针指向新插进来的节点
    cur->front =plist;//新插进来的节点的头指针指向链表头
    tem->front =cur;  //使tem节点的头指针指向新插进来的节点
    cur->next =tem;   //新插进来的尾指针指向tem
 } 

void forntinsert_list(List* plist, int data)    //前插入一个节点
{
    insert_front(plist->head,data);
}

void insert_after(ListNode*  plist, intdata)     //链表头后插
{
    ListNode* cur =(ListNode*)malloc(sizeof(ListNode));
    ListNode* tem =plist->front; 
    cur->data = data;
    plist->front = cur; //使链表头的头指针指向新插进来的节点
    cur->next = plist;  //新插进来的节点的尾指针指向链表头
    tem->next = cur;    //使tem节点的尾指针指向新插进来的节点
    cur->front = tem;   //新插进来的头指针指向tem
}

void afterinsert_list(List* plist, int data) //后插入一个节点
{
    insert_after(plist->head,data);
}
 
void  the_insert(List  *plist, int pos, int data)
{
    int i = 0;
    ListNode* cur =(ListNode*)malloc(sizeof(ListNode));
    ListNode* tem =plist->head;
    int num =data_num(plist);
    if (pos > num)//所插入数据的位置不能大于节点数，因为是循环链表
    {
        printf("插入数据失败\n");
        return;
    }
    for (; i < pos;i++)
    {
        tem =tem->next;//找到插入新节点的位置
    }
    cur->data = data;
    cur->next =tem->next;//将tem尾指针中存放的内容赋给新节点的尾指针，即新节点的尾指针代替tem的尾指针
    
    tem->next->front= cur;//将原tem节点的下一个节点的头指针指向新节点
    cur->front = tem;//将新节点的头指针指向tem节点
    tem->next = cur;//将tem的尾指针指向新节点
}

void print(List* plist)                   //打印
{
    ListNode* tem;
    if (plist->head ==NULL)
    {
        printf("\n链表已销毁\n");
        return;
    }
    for (tem =plist->head->next; tem != plist->head; tem = tem->next)//双向循环链表的遍历
    {
        printf("%d  ", tem->data);
    }
    printf("\n");
}
 
void  del(ListNode   *the_plist)       //删除
{
    the_plist->front->next= the_plist->next;//将该节点尾指针中存放的内容存放到上一个节点的尾指针中
    
    the_plist->next->front= the_plist->front;//将该节点头指针中存放的内容存放到下一个节点的头指针中
    free(the_plist);//释放这个节点
}

 void  del_front(List  *plist)    //头删
{
    del(plist->head->next);//删除链表头
} 

void  del_after(List  *plist)    //尾删
{
    del(plist->head->front);//删除链表尾
}

ListNode* list_reach(List* plist, int data)     //查找
{
    ListNode* tem;
    for (tem =plist->head->next; tem != plist->head; tem = tem->next)
    {
        if (tem->data== data)
            return  tem;
    }
    return NULL;
}

void  the_del(List  *plist, int data)     //删除指定的节点
{
    ListNode* tmp =list_reach(plist, data);
    if (tmp)
        del(tmp);
}
 
void  destory(List  *plist)      //销毁链表
{
    while (plist->head!= plist->head->next)
    {
        del_front(plist);//依次删头
    }
    free(plist->head);//释放最后一个头
    plist->head = NULL;
}

int main()
{
    //定义一个“链表头”
    List* first ;
    init(&first);
     forntinsert_list(&first,2);
    forntinsert_list(&first,8);
    print(&first);
    afterinsert_list(&first,0);
    print(&first);
    the_insert(&first,1, 5);
    print(&first);
     the_insert(&first,1, 6);
    print(&first);
    the_insert(&first,0, 9);
    print(&first);
    forntinsert_list(&first,0);
    print(&first);
    int k =data_num(&first);
    printf("%d个节点\n",k);
    the_insert(&first,8, 7);
    print(&first); 
    del_after(&first);
    print(&first);
    del_front(&first);
  print(&first);
    the_del(&first,6);
    print(&first);
    system("pause");
    return 0;
}
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188