资讯专栏INFORMATION COLUMN

数据结构之链表

Lin_R / 1343人阅读

摘要:实际中更多是作为其他数据结构的子结构,如哈希桶图的邻接表等等。实际中使用的链表数据结构,都是带头双向循环链表。以结点的序列表示线性表称作线性链表线性链表单链表,单链表是链式存取的结构。

目录

1.链表的分类:

2.单链表的基本概念和性质:

链表的创建和遍历

 单链表的尾部插入

单链表的头部插入:

单链表pos位置后面插入:

单链表尾删

单链表头删

单链表pos位置删除:

单链表的查找:

单链表的销毁:


1.链表的分类:

1.单向或者双向

2. 带头或者不带头

3. 循环或者非循环

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

单链表

2.单链表的基本概念和性质:

1.1:单链表概念:

链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。

1.2单链表的存储方法:

链接方式存储的线性表简称为链表(Linked List)。

链表的具体存储表示为:

① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))

链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。

链表的创建和遍历

1.单链表中结点的定义

typedef int SLTDataType;struct SLTNode{	SLTNode(SLTDataType x)		:next(nullptr),val(x)	{}	SLTNode* next;	SLTDataType val;};

2.单链表内部结构:

单个节点:

 2.单链表的创建:

对应代码:

SLTNode* CreateSLTNode(SLTDataType x){	SLTNode* newnode = new SLTNode(x);	newnode->next = nullptr;	newnode->val = x;	return newnode;}

3.单链表的遍历:

void SLTNodePrint(SLTNode* head){	SLTNode* probe = head;	while (cur)//不为空则继续遍历	{		cout << probe->val << "->";//打应其数据		probe =probe->next;	}	cout << "nullptr" << endl;}

 单链表的尾部插入

实现思路:

1.如果链表没有头结点,新结点直接成为头结点。

2.如果有头节点则需要先找到链表当前的尾结点,并将新结点插入到链表尾部。

SLTNode* CreateSLTNode(SLTDataType x)//创建节点{	SLTNode* newnode = new SLTNode(x);	newnode->next = nullptr;	newnode->val = x;	return newnode;}void SLTNodePushBack(SLTNode*&phead,SLTDataType x){	SLTNode* newnode = CreateSLTNode(x);	if (phead == nullptr) {//如果一个节点也没有则此时我们需要创建节点				phead = newnode;		return;	}	SLTNode* tail = phead;	while (tail->next)//找尾	{		tail = tail->next;	}	tail->next = newnode;//链接}

单链表的头部插入:

1.如果链表没有头结点,新结点直接成为头结点。

2.否则新结点的next直接指向当前头结点,并让新结点成为新的头结点。

SLTNode* CreateSLTNode(SLTDataType x){	SLTNode* newnode = new SLTNode(x);	newnode->next = nullptr;	newnode->val = x;	return newnode;}void SLTNodePushFront(SLTNode*& phead,SLTDataType x){	SLTNode* newnode = CreateSLTNode(x);	if (phead == nullptr) {		phead = newnode;	}	else	{		newnode->next = phead;		phead = newnode;	}}

单链表pos位置后面插入:

实现思路:

在目标位置处插入数据元素流程如下:
1、从头结点开始,提供cur指针定位到目标位置
2、从堆空间申请新的Node结点
3、将新结点插入目标位置,并连接相邻结点的逻辑关系。

对应图解:

 da

对应代码实现:

void SLTNodeInsert(SLTNode* pos, SLTDataType x){	assert(pos);	SLTNode* newnode = CreateSLTNode(x);	newnode->next = pos->next;	pos->next = newnode;}

单链表尾删

实现思路

1.如果链表一个元素也没有则return

2.如果链表只有一个节点则将其置空,并将头节点置空

3.如果链表不止一个节点,我们则定义一个指针变量tail找尾,定义一个指针变量prev记录tail的前一个节点将prev->next指向tail->next,也就是prev->next=tail->next;在将尾部的节点释放

对应图解:

对应代码:

void SLTNodePopBack(SLTNode*& phead){	if (phead == nullptr) {		return;	}	else if (phead->next == nullptr) {		free(phead);		phead = nullptr;	}	else{		SLTNode* prve = nullptr;		SLTNode* tail = phead;		while (tail->next)		{			prve = tail;			tail = tail->next;		}		prve->next = tail->next;		free(tail);		tail = nullptr;	}}

单链表头删

实现思路:

1.首先判断链表是不是空链表,如果是那么就return;

2.如果不为空那么我们定义一个指针变量记录头节点的下一个节点,在让下一个节点做新的头,在释放原来的头节点

对应代码:

void SLTNodePopFront(SLTNode*& phead){	if (phead == nullptr) {//如果一个节点也没有就不用删了		return;	}	else	{		SLTNode* next = phead->next;		free(phead);		phead = next;	}}

单链表pos位置删除:

实现思路:

1.找到目标结点之前位置

2.提前保存目标结点后位置

3.销毁目标结点

4.链接原目标结点之前的位置与原目标结点之后的位置

代码实现:

 

void EraseCurrent(SLTNode*&phead,SLTNode* pos) {	assert(phead && pos);	if (phead == pos) {		SLTNode* next = phead->next;		free(phead);		phead = next;	}	else {		SLTNode* cur = phead;		SLTNode* prev = nullptr;//记录cur的前一个节点		while (cur) {			if (cur == pos) {				break;			}			prev = cur;			cur = cur->next;		}		if (cur) {			prev->next = cur->next;			free(cur);			cur = nullptr;		}	}}

或者这种写法也是可以的:

void SLTNodeErase(SLTNode*& phead, SLTNode* pos){	assert(phead && pos);	if (pos == phead){		SLTNode* next = phead->next;		free(phead);		phead = next;	}	else{		SLTNode* cur = phead;		while (cur->next != pos)		{			cur = cur->next;		}		cur->next = cur->next->next;		free(pos);		pos = nullptr;	}}

单链表的查找:

实现思路:

这个就比较暴力遍历一次链表,如果找到了就返回节点的指针,如果没有找到就返回NULL

代码实现:

SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos){	assert(pos && phead);	SLTNode* cur = phead;	while (cur)	{		if (cur->val == pos->val)		{			return cur;		}	}	return nullptr;}

单链表的销毁:

实现思路:

1.定义一个指针变量变量cur整个链表,在定义一个指针变量next记录cur的下一个节点

2.free(cur),在让cur指向下一个节点,即cur=next;

对应代码实现:

void SListDestory(SLTNode*&phead){	SLTNode* cur = phead;	while (cur)	{		SLTNode* next = cur->next;		free(cur);		cur = next;	}	phead = nullptr;}

代码汇总:

SList.cpp

#include"SList.h"SLTNode* CreateSLTNode(SLTDataType x){	SLTNode* newnode = new SLTNode(x);	newnode->next = nullptr;	newnode->val = x;	return newnode;}void SLTNodePrint(SLTNode* phead){	SLTNode* cur = phead;	while (cur)	{		cout << cur->val << "->";		cur = cur->next;	}	cout << "nullptr" << endl;}void SLTNodePushBack(SLTNode*&phead,SLTDataType x){	SLTNode* newnode = CreateSLTNode(x);	if (phead == nullptr) {				phead = newnode;		return;	}	SLTNode* tail = phead;	while (tail->next)	{		tail = tail->next;	}	tail->next = newnode;}void SLTNodePopBack(SLTNode*& phead){	if (phead == nullptr) {		return;	}	else if (phead->next == nullptr) {		free(phead);		phead = nullptr;	}	else{		SLTNode* prve = nullptr;		SLTNode* tail = phead;		while (tail->next)		{			prve = tail;			tail = tail->next;		}		prve->next = tail->next;		free(tail);		tail = nullptr;	}}void SLTNodePopFront(SLTNode*& phead){	if (phead == nullptr) {		return;	}	else	{		SLTNode* next = phead->next;		free(phead);		phead = next;	}}void SLTNodePushFront(SLTNode*& phead,SLTDataType x){	SLTNode* newnode = CreateSLTNode(x);	if (phead == nullptr) {		phead = newnode;	}	else	{		newnode->next = phead;		phead = newnode;	}}SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos){	assert(pos && phead);	SLTNode* cur = phead;	while (cur)	{		if (cur->val == pos->val)		{			return cur;		}	}	return nullptr;}void SLTNodeErase(SLTNode*& phead, SLTNode* pos){	assert(phead && pos);	if (pos == phead){		SLTNode* next = phead->next;		free(phead);		phead = next;	}	else{		SLTNode* cur = phead;		while (cur->next != pos)		{			cur = cur->next;		}		cur->next = cur->next->next;		free(pos);		pos = nullptr;	}}void SListDestory(SLTNode*&phead){	SLTNode* cur = phead;	while (cur)	{		SLTNode* next = cur->next;		free(cur);		cur = next;	}	phead = nullptr;}void SLTNodeInsert(SLTNode* pos, SLTDataType x){	assert(pos);	SLTNode* newnode = CreateSLTNode(x);	newnode->next = pos->next;	pos->next = newnode;}void SLTNodeEraseAfter(SLTNode* pos){	assert(pos);	SLTNode* next = pos->next;	pos->next = pos->next->next;	free(next);}void EraseCurrent(SLTNode*&phead,SLTNode* pos) {	assert(phead && pos);	if (phead == pos) {		SLTNode* next = phead->next;		free(phead);		phead = next;	}	else {		SLTNode* cur = phead;		SLTNode* prev = nullptr;//记录cur的前一个节点		while (cur) {			if (cur == pos) {				break;			}			prev = cur;			cur = cur->next;		}		if (cur) {			prev->next = cur->next;			free(cur);			cur = nullptr;		}	}}

Test.cpp

#include"SList.h"void TestSList(){	SLTNode* plist = nullptr;	/*SLTNodePushBack(plist, 1);	SLTNodePushBack(plist, 2);*/			SLTNodePushFront(plist, 0);	SLTNodePrint(plist);}int main(){	TestSList();}

SList.h

#pragma once#include#includeusing namespace std;typedef int SLTDataType;struct SLTNode{	SLTNode(SLTDataType x)		:next(nullptr),val(x)	{}	SLTNode* next;	SLTDataType val;};void SLTNodePrint(SLTNode* phead);void SLTNodePushBack(SLTNode*& phead,SLTDataType x);void SLTNodePopBack(SLTNode*& phead);void SLTNodePopFront(SLTNode*& phead);void SLTNodePushFront(SLTNode*& phead,SLTDataType x);SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos);void SLTNodeErase(SLTNode*& phead, SLTNode* pos);void SListDestory(SLTNode*&phead);void SLTNodeInsert(SLTNode* pos, SLTDataType x);void SLTNodeEraseAfter(SLTNode* pos);

 总结:

单链表增删查改时间复杂度分析:

增:

链表是通过记录头部地址来进行寻找后面数值的,所以需要遍历链表操作,如果在头部增,只需要查找一次,时间复杂度是 O(1),在尾部增需要查找n次,时间复杂度是 O(n).

删:

要遍历找到想要删除的数值,进行删除,对于链表,我们没法使用二分查找,只能遍历查找,找到该节点后删除,平均查找次数是n/2,时间复杂度是 O(n).

查:

要遍历查找,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).

改:

要遍历找到想要更改的数值,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).
 

 

如果觉得写的不错的话可以点个赞,如果有错误的话请在评论区留言谢谢!!!! 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/124468.html

相关文章

  • 数据结构与算法随笔链表-链表是否有环(二)

    摘要:初始化时指针走两步,指针走一步,不停遍历的变化最后快慢指针又相遇了,循环结束,代码实现如下复杂度分析,假设链表长度为时间复杂度,链表无环时,快指针会先到达尾部,时间就是如果有环,那么假设环部长度为,时间就是,也就是空间复杂度 上一篇文章我们分析了下链表之反转单向链表,这篇文章我们来分析下另外一个关于链表的经典题目。 判断链表是否有环(在leetcode上的题目地址:环形链表) 题目描述...

    molyzzx 评论0 收藏0
  • 学习数据结构与算法链表

    摘要:本系列所有文章第一篇文章学习数据结构与算法之栈与队列第二篇文章学习数据结构与算法之链表第三篇文章学习数据结构与算法之集合第四篇文章学习数据结构与算法之字典和散列表第五篇文章学习数据结构与算法之二叉搜索树简单介绍链表链表一种常见的数据结构,可 本系列所有文章:第一篇文章:学习数据结构与算法之栈与队列第二篇文章:学习数据结构与算法之链表第三篇文章:学习数据结构与算法之集合第四篇文章:学习数...

    jerryloveemily 评论0 收藏0
  • 03线性表链表

    摘要:带头双向循环链表结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。 肚子饿了就要吃   ~   嗝  ——— 路飞  1.本章重点 链表表示和实现(单链表+双链表)链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表 引子:顺序表的问题及思考 (1...

    jayce 评论0 收藏0
  • PHPer也刷《剑指Offer》链表

    摘要:剑指中链表相关题目俗话说光说不练假把式,既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下,下面来看剑指中的相关题目。题目分析合并两个排序的链表,需要分别比较两个链表的每个值,然后改变指针。 温故知新 链表由一个一个的作为节点的对象构成的,每一个节点都有指向下一个节点的指针,最后一个节点的指针域指向空。每个节点可以存储任何数据类型。 根据类型可以分为单链表、双链表、环形链表、...

    daydream 评论0 收藏0
  • 利用PHP实现《剑指 offer》链表数据结构与算法实战 )

    摘要:一定要认真看分析注释题目要求题目描述输入一个链表,从尾到头打印链表每个节点的值。分析因为链表只有知道当前结点才能知道下一结点,所以不可能直接从后往前打印。 一定要认真看 分析 | 注释 | 题目要求 Question 1 题目描述:输入一个链表,从尾到头打印链表每个节点的值。 分析:因为链表只有知道当前结点才能知道下一结点,所以不可能直接从后往前打印。这种逆序的算法(策略)我们常用栈这...

    hiYoHoo 评论0 收藏0
  • 利用PHP实现常用的数据结构链表(小白系列文章五)

    摘要:因为涉及指针,我们用引用来模拟,所以读者应该有面向对象的知识贮备。引文因为涉及内存,常常会有一些程序的边界限制,需要拥有一定严密的逻辑去保证代码的鲁棒性和健壮性,所以这个知识点是面试的常考点。 tips:因为涉及指针,我们用引用来模拟,所以读者应该有面向对象的知识贮备。 引子 你可以把链表简单理解为动态数组,它不需要一块一块的开辟空间,同时,你又要注意,它存在的主要意义或者说使用场景...

    rollback 评论0 收藏0

发表评论

0条评论

Lin_R

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<