【数据结构】链表的基本概念和操作网站首页 技术交流

【数据结构】链表的基本概念和操作

Tryagein 2025-03-25 00:01:02

简介【数据结构】链表的基本概念和操作

单链表

除顺序表外，线性表的另一种链式表示方法是链表。在链表中，逻辑上相邻的元素在物理存储位置上并不一定是相邻的，这时，连接各个元素的“链”显得尤为重要。通常，我们使用指针来表示元素之间的链式关系。

图1 实际链条与数据结构中单链表的对比

单链表

单链表的概念

单链表是链式存储结构的最简形式，一个单链表节点包含两个元素：当前节点的值以及下个节点的地址，一般使用data与next表示。

图2 单链表节点

通常使用一个头指针来标识一串单链表，头指针指向单链表的第一个结点。

图3 头指针示意

可以预见的是（但初学者不一定能够预见），上面这种形式的链表，处理首个结点和其他结点的操作会不太一样，这会增加操作的复杂度（比如专门为首节点的处理另起一段代码）。于是这里引入一个特殊的结点：头结点。头结点位于一串单链表的首位，并且不存放任何数据。

图4 头结点示意

经过这样处理后，单链表的首个带有数据的结点的处理方式与其他结点一样，同时无论链表是否为空，头指针都是指向头结点的非空指针。

这里有三点需要注意：

头指针始终指向链表的第一个结点。
头结点不算在链表长度里。
链表节点之间的存储位置不一定相邻，但在单个链表节点内部，数据与指向下一个节点的指针信息是相邻存储的，因为它们处于同一个结构体内。

单链表的基本操作

现假设链表中存储的元素为int类型。

定义

一串单链表中单个结点的定义代码如下：

typedef struct LNode{
	int data;                    //数据域
	struct LNode* next;          //指针域
}LNode,*LinkList;                //别名

这里*LinkList表示LNode结构体的指针别名，LinkList p等同于LNode *p。并且要注意指针域next是LNode型。

通过结点定义可以看出来链表与顺序表的不同之处：顺序表定义时定义的是一整个顺序表，一整个表就是一个结构体；而链表定义时结构体为一个结点而不是一串链表，结构体之间通过指针相连。

初始化

链表的初始化主要干三件事：创建头结点、头指针指向头结点、头结点next指针置空。

代码如下：

void InitList(LinkList &L){                //引入参数时头指针指向L
	L=(LNode*)malloc(sizeof(LNode));       //开辟头结点，大小为LNode形（不是int型）
	L->next=nullptr;                       //置空
}

求表长

求表长时注意头结点不计入表长，所以要注意循环的终止条件（或者设定好临时指针的初值）。

代码如下：

int Length(LinkList L){
	int len=0;
	for(LinkList p=L;p->next !=nullptr;p=p->next)
		len++;
	return len;
}

按序号查找

按序号查找时注意i的数值是否正确（是否小于零或者没有序号为i的链表结点）。另一方面遍历链表可以从头结点开始遍历，也可以从头结点的下一个结点开始遍历，这里以忽略头结点为例：

LinkList IndexSearch(LinkList L,int i) {   //LinkList（LNode*）型函数，用以返回搜寻元素的指针 
	if (i <= 0)                            //判定i是否小于0     
	   return nullptr;                  
	LinkList p = L->next;                  //定义临时指针用以遍历链表
	int j = 1;                             //计数变量j，由于略过头结点，j=1而不是0
        while (p != nullptr && j < i) {    //确保p不为空
        	p = p->next;                   
        	j++;
  	}
        return p;                          //返回指针
}

按值查找

与按序号查找相仿，不需要使用临时变量j。

代码如下：

LinkList ValueSearch(LinkList L,int e){
	LinkList p=L->next;
	while(p!=nullptr&&p->data!=e)
		p=p->next;
	return p;
}

插入

在给定位置i插入一个元素，主要分为两步：1、将新结点的next链条连上原链条第i位元素。2、将i-1位元素的next链条改连到新结点上。这里注意次序不能颠倒，否则会丢失i-1后的所有元素。

图4 单链表插入

代码如下：

bool InsertElem(LinkList &L,int i,int e){
	LinkList p=L;                                //临时指针用于寻找i-1号元素
	int j=0;                                     //从头结点开始遍历（插入位置可能为1号）
	while(p!=nullptr&&j<i-1){                    //寻找i-1号元素
		p=p->next;
		j++;
	}
	if(p==nullptr)
		return false;
	LinkList s=(LNode*)malloc(sizeof(LNode));    //开辟新结点
	s->next=p->next;                             //新结点链接
	p->next=s;                                   //i-1号节点改链
	s->data=e;	                                 //新结点赋值
	return true;
}

删除结点

删除结点主要分为两步：1、将i-1号结点的next链连上i结点的后一个节点。2、删除i结点。

图5 单链表删除

代码如下：

bool DeleteElem(LinkList &L,int i,int &e){
	LinkList p=L;                               //寻找i-1号结点
	int j=0;
	while(p!=nullptr&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==nullptr||p->next==nullptr)            //判定删除位置是否合法
		return false;
	LinkList q=p->next;                         //q为待删除结点
	p->next=q->next;                            //断链改连
	e=q->data;                                  //储存删除的数据
	free(q);                                    //释放储存空间
	return true;
}

头插建表

头插建表又称逆序建表，如果顺序读取一个给定数组，建立出来的链表元素顺序与原数组相反。

图6 头插建立单链表

代码如下：

LinkList HeadInsert(LinkList &L){          //假设已经初始化了链表L，已有头结点
	LinkList p;                            //节点地址
	int x;                                 //结点数据
	scanf("%d",&x);                        //第一个结点值
	while(x!=0){                           //键入0视为结束建表
		p=(LNode*)malloc(sizeof(LNode));   //开辟空间
		p->data=x;                         //赋值
		p->next=L->next;                   //链接新链
		L->next=p;                         //断链改连
		scanf("%d",&x);                    //继续键入下一个节点数据
	}
	return L;
}

尾插建表

尾插建表虽然可以正序建表，但是与头插建表相比要多一个尾指针。

图7 尾插法建立单链表

代码如下：

LinkList TailInsert(LinkList &L){
	LinkList p,t;                              //p指针用于存放新结点，t用于充当临时尾指针
	int x;                                     //数据值
	t=L;                                       //初始t位于头结点后
	scanf("%d",&x);
	while(x!=0){                               //键入x=0终止
		p=(LNode*)malloc(sizeof(LNode));       //开
		t->next=p;                             //尾指针指向新指针
		p->data=x;
		t=p;                                   //尾指针重置在队尾
		scanf("%d",&x);                        //键入新值
	}
	p->next=nullptr;                           //建表完毕时尾指针置空
	return L;
}

双链表

双链表的概念

单链表节点只有一个指向后继节点的指针，因此只能从前往后顺序遍历链表。在执行插入和删除操作时，若需要访问某个节点的前驱，只能从头节点开始逐个遍历，这使得访问前驱节点的时间复杂度为 O(n)。为了解决单链表的这一问题，引入了双链表。双链表中的每个节点有两个指针：prior 和 next，分别指向其直接前驱和直接后继。双链表的表头节点的 prior 指针和尾节点的 next 指针均为空（NULL）。

图8 双链表结构

需要注意的是，双链表由于有prior这个指针，也可以不设置头结点而只设置尾结点

双链表的基本操作

假设双链表存储int类型数据。

定义双链表结点

typedef struct DNode{
	int data;
	struct DNode *prior,*next;        //定义前驱后继指针
}DNode,*DLinkList;

插入

双链表的插入与单链表在本质上是一致的，即插入时不能够丢失原链条拆开两个部分的位置。这里举个错误例子就很好理解了。现假设已经找到了i-1的结点位置，需要在i位上插入新结点。

图9 链条丢失示例

这里已有的指针为i-1与新结点的指针，在不进行任何改动时，i的指针表示为p->next。如果进行上图的插入操作，用代码表示如下：

#假设新结点为s，i-1结点为p
p->next=s；
p->next->prior=s;          //这里p->next不再指示原链条i结点的地址，其地址丢失

当然这里如果使用一个临时变量存储原i位置结点，那么这种方法也是可行的，不过会增加一点内存使用量。

正确的方法如下：

s->next=p->next                //先链接新元素，保证不丢失原链
p->next->prior=s;
s->prior=p;
p->next=s;

当然这里方法不唯一，满足不丢链的原则就可以了。

删除

删除挺简单的，没有什么值得一提的，记住free掉不用的结点即可。

p->next=q->next;
q->next->prior->p;
free(q);

循环链表

循环单链表概念

循环单链表与单链表的主要区别在于，循环单链表的最后一个结点的指针不再指向 NULL，而是指向头结点，从而形成一个环。在循环单链表中，表尾节点 *r 的 next 域指向头结点，因此链表中没有指针域为 NULL 的结点。由于这一特点，循环单链表的判空条件不再是检查头结点的指针是否为空，而是判断头结点指针是否等于自己，即是否指向自身。循环单链表可以带有头指针或尾指针中的一种，或者是两者都带，这取决于操作需求，具体会在下面的辨析中提到。

图 10 循环单链表

循环双链表概念

与循环单链表不同的是，循环双链表头结点的prior指针指向尾结点，其他方面与循环单链表类似。

循环链表辨析

对于一个单链表而言，在表尾插入新结点的时间复杂度是O(n)，因为需要从头开始遍历才能找到尾结点。若一个循环单链表带有尾指针，则这项操作的时间复杂度降为O(1)；如果是删除表尾结点，那么循环单链表和单链表一样，需要O(n)的时间复杂度。但带头指针的循环双链表完成这个操作只要O(1)的时间复杂度。可以看出，循环链表使得一些操作的时间复杂度显著降低，尤其是表头或者表尾的某些操作。例如，带着尾指针的循环单链表可以用于表示队列（表头删除，表尾插入）。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。