【线性表】链表：循环单链表、双链表、循环双链表的基本特性

链表不仅作为链式存储的一种实现方式，还表达了计算机不连续（离散）的存储思想。在初学阶段，链表的实现类型有单链表（带/不带头结点）、循环单链表、双链表、循环双链表四种。

上文已经讲解了单链表，接下来将讲解其他三类。

---

Table of Contents

循环单链表

双链表

循环双链表

---

循环单链表

 

定义：

将单链表中终端结点的指针端由 NULL 改为 指向头结点 ，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

 

 

两种情形：

• 为使空链表与非空链表处理一致，通常设置一个头结点。但并非必须设置头结点。

循环单链表特征：

1. 对于单链表而言，最后一个结点指向NULL；把最后一个结点的不指向NULL而指向头，就是循环单链表；
2. 在单循环链表上的操作基本上与非循环链表相同。循环链表和单链表的主要差异就在于循环的条件判断上，原来是 p->next == NULL，现在是 p->next != 头结点 ，则循环未结束。
3. 单循环链表可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行。如果用头指针表示循环链表，则需O(n) 时间找到最后一个结点。若改用尾指针表示循环链表，此时查找开始结点和终端结点都很方便了。查找终端结点时间是O(1)，而开始结点，其实就是 rear->next->next ，其时间复杂也为O(1)。

第一个循环单链表

#include <stdio.h>
#include <malloc.h>
#include <assert.h>

typedef struct node
{
	int data;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = NULL; //头结点，不保存数据
	head->next = NodeAa;
	NodeAa->data = 202;
	NodeAa->next = NodeBb;
	NodeBb->data = 303;
	NodeBb->next = NodeCc;
	NodeCc->data = 404;
	NodeCc->next = head;  //单链表中：NodeCc->next = NULL;

	LinkList p = head->next; //把链表头结点的下一个节点，交给指针p，去遍历
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	return 0;
}

 

 

---

双链表

 

定义：

双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。

 

 

双链表的代码定义：

 

typedef struct node
{
	int data;
	struct node* pre; //前驱
	struct node* next; //后继
}Node;

 

特性：

1. 从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
2. 循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
3. 双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。

第一个双链表

第一个双链表
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

typedef struct node
{
	int data;
	struct node* pre;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = 101;
	head->pre = NULL;
	head->next = NodeAa;

	NodeAa->data = 202;
	NodeAa->pre = head;
	NodeAa->next = NodeBb;

	NodeBb->data = 303;
	NodeBb->pre = NodeAa;
	NodeBb->next = NodeCc;

	NodeCc->data = 404;
	NodeCc->pre = NodeBb;
	NodeCc->next = NULL;  //单链表中：NodeCc->next = NULL;

	LinkList p = head; //把链表头结点的下一个交给指针p，去遍历
	printf("顺序遍历：");
	while (p != NULL)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	printf("\n逆序遍历：");
	LinkList tail = NodeCc;
	p = tail;
	while (p != NULL)
	{
		printf("%d  ", p->data);
		p = p->pre;
	}

	return 0;
}

 

 

---

循环双链表

 

定义：

双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。头指针的前驱指向最后一个节点，最后一个节点的后继指向头指针。

双链表的代码定义：

typedef struct node
{
	int data;
	struct node* pre; //前驱
	struct node* next; //后继
}Node;

特性：

1. 从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
2. 循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
3. 双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。

两种情形：

第一个循环双链表

#include <stdio.h>
#include <malloc.h>
#include <assert.h>

typedef struct node
{
	int data;
	struct node* pre;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = NULL; //头结点，不保存数据
	head->pre = NodeCc;
	head->next = NodeAa;

	NodeAa->data = 202;
	NodeAa->pre = head;
	NodeAa->next = NodeBb;

	NodeBb->data = 303;
	NodeBb->pre = NodeAa;
	NodeBb->next = NodeCc;

	NodeCc->data = 404;
	NodeCc->pre = NodeBb;
	NodeCc->next = head;  //单链表中：NodeCc->next = NULL;

	LinkList p = head->next; //把链表头结点的下一个交给指针p，去遍历
	printf("顺序遍历：");
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	printf("\n逆序遍历：");
	p = p->pre;
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->pre;
	}

	return 0;
}

---