数据结构双链表和双循环链表(C语言代码)

单链表

单向链表特点：
  1.可以轻松的到达下一个节点, 但是回到前一个节点是很难的.
  2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾)

双向链表特点
  1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
  2.相对于单向链表, 必然占用内存空间更大一些.
  3.既可以从头遍历到尾, 又可以从尾遍历到头

双向链表的定义:
  双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。

指针域：用于指向当前节点的直接前驱节点；
数据域：用于存储数据元素；
指针域：用于指向当前节点的直接后继节点。

完整代码：

#include
#include #define TRUE 1
#define FALSE 0typedef struct Node {int data;struct Node* pre;struct Node* next;
}Node;//初始化链表
Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L->data = 0;L->pre = NULL;L->next = NULL;return L;
}//头插法
void headInsert(Node* L, int data) {Node* node= (Node*)malloc(sizeof(Node));node->data = data;if (L->data == 0) {//链表为空node->next = L->next;node->pre = L;L->next = node;}else {node->pre = L;node->next = L->next;L->next->pre = node;L->next = node;}L->data++;
}
//尾插法
void tailInsert(Node* L,int data) {Node* node= (Node*)malloc(sizeof(Node));Node* n= L;node->data = data;while (n->next){n = n->next;}node->pre = n;node->next = n->next;n->next = node;L->data++;
}//删除结点
int deleteList(Node* L,int data) {Node* node = L->next;while (node){if (node->data == data) {//删除操作node->pre->next = node->next;node->next->pre = node->pre;free(node);L->data--;return TRUE;}node = node->next;}return FALSE;}//遍历链表
void printList(Node* L) {Node* node = L->next;while (node){printf("%d->", node->data);node = node->next;}printf("NULL\n");
}int main(void) {Node* L = initList();headInsert(L, 1);headInsert(L, 2);headInsert(L, 3);headInsert(L, 4);tailInsert(L, 5);tailInsert(L, 6);tailInsert(L, 7);tailInsert(L, 8);printList(L);deleteList(L, 2);printList(L);deleteList(L, 5);printList(L);return 0;
}


运行结果：

双循环链表

双向链表也可以进行首尾连接，构成双向循环链表,如下图所示 在创建链表时，只需要在最后将收尾相连即可。

完整代码：

#include
#include #define TRUE 1
#define FALSE 0typedef struct Node {int data;struct Node* pre;struct Node* next;
}Node;//初始化链表
Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L->data = 0;L->pre = L;L->next = L;return L;
}//头插法
void headInsert(Node* L, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;if (L->data == 0) {//链表为空node->pre = L;node->next = L->next;L->next = node;L->pre = node;}else{//链表不为空node->next = L->next;node->pre = L;L->next->pre = node;L->next = node;}L->data++;
}//尾插法
void tailList(Node* L, int data) {Node* node= (Node*)malloc(sizeof(Node));Node* n = L;node->data = data;while (n->next!=L){n = n->next;}node->pre = n;node->next = L;n->next = node;L->pre = n;L->data++;
}//删除结点
int deleteList(Node* L, int data) {Node* node = L->next;while (node!=L){if (node->data==data){node->pre->next = node->next;node->next->pre = node->pre;free(node);L->data--;return TRUE;}else {node = node->next;}}return FALSE;
}//遍历链表
void printList(Node* L) {Node* node = L->next;while (node!=L) {printf("%d->", node->data);node = node->next;}printf("NULL\n");
}int main(void) {Node* L=initList();headInsert(L, 1);headInsert(L, 2);headInsert(L, 3);headInsert(L, 4);tailList(L, 5);tailList(L, 6);tailList(L, 7);tailList(L, 8);printList(L);deleteList(L, 2);printList(L);deleteList(L, 6);printList(L);return 0;
}


运行结果：