03线性表之链表

jayce 发布于2021-09-09 09:33 / 1480人阅读

摘要：带头双向循环链表结构最复杂，一般用在多带带存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

肚子饿了就要吃 ~ 嗝 ——— 路飞

1.本章重点

链表表示和实现（单链表+双链表）
链表的常见OJ题
顺序表和链表的区别和联系

2.为什么需要链表

引子：顺序表的问题及思考

(1)动态顺序表

特点：

插入数据，空间不够了，需要增容。
要求数据是依次存储的。

缺陷：

如果空间不够，增容。增容会付出一定的性能消耗，需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容，可能存在增容后的空间有所浪费。（增容一般都是增容2倍）
头部或者中部左右插入数据，要求依次移动，插入效率低下。（ O(N) ）

（2）如何解决：

按需求给空间（存一个给一个）。
不需要物理空间连续，头部和中部的插入，不需要挪动数据。

这就引出了一个新的物理存储结构 ————> 链表

3.链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

逻辑结构（想象出来的），如图：（单链表为例）

物理结构（在内存中的结构），如图：（单链表为例）

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向，双向
带头，不带头
循环，非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：

结构简单，一般不会多带带用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：

结构最复杂，一般用在多带带存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

4.单链表的实现

注：

plist/phead——>头指针（一般保持不动）

cur——>当前位置( current简写)

找尾巴注意的点：

对比

	//错误代码    //找到原来的尾巴（进而插尾）	SLTNode* tail = phead;	while (tail != NULL)	{		tail = tail->next;	}

	//正确代码    //找到原来的尾巴（进而插尾）	SLTNode* tail = phead;	while (tail->next != NULL)	{		tail = tail->next;	}

解释：

第一段代码是错误的，因为

私有云专线服务服务器03还是08 服务器03和08 VoLLcloudh&amp03 rds035l03

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

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

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

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

molyzzx 2019-08-16 13:26 评论0 收藏0
数据结构与算法的Python实现（二）——线性表之顺序表

摘要：文章首发于公众号一件风衣在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基础，在中，和就可以看作是线性表的实现。文章首发于公众号一件风衣（ID：yijianfengyi）在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基...

TerryCai 2019-07-30 16:53 评论0 收藏0
数据结构之线性表

摘要：线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。链表之单链表线性表的定义，它是一些元素的序列，维持着元素之间的一种线性关系。线性表学习笔记，python语言描述-2019-1-14 线性表简介在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含...

leoperfect 2019-07-30 18:46 评论0 收藏0