关键词：
肚子饿了就要吃 ~ 嗝 ——— 路飞
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;
解释：
第一段代码是错误的，因为
java数据结构线性表之链表(代码片段)
目录（1）链表（2）单向链表（2.1）单向链表API设计（2.2）单向链表代码实现（3）双向链表（3.1）结点API设计（3.2）双向链表API设计（3.3）双向链表代码实现& 查看详情
线性表之链表(代码片段)
单链表也是一种链式存取的线性表，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，以next指针指向下一个节点而链接起来，相比于顺序表，链表有着快速增加，删除节点的优势，其节点... 查看详情
c语言严蔚敏数据结构线性表之链表实现(代码片段)
...算机科学与技术专业，复习专业课数据结构，正好学习到线性结构中的线性表用链表这种存储结构来实现。 首先，数据结构包括1、数据的操作2、逻辑结构3、存储结构(数据结构三要素。 直接上代码，现阶段代码实现功... 查看详情
数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)
链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表，也就是单链表。单链表因为结构简单，但是实际操作比较复杂，所... 查看详情
线性表之链表(代码片段)
线性表的链式存储表示的特点:是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了... 查看详情
线性表之链表c语言
线性表之链表【C语言】2.5线性表的链式表示和实现4、头指针、头结点和首元结点:讨论1:如何表示空表?讨论2:在链表中设置头结点有什么好处?讨论3:头结点的数据域内装的是什么?■链表(链式存储结构)的特点2.5.1单链表的定义和... 查看详情
线性表之链表源码
//链表#include<iostream>#include<algorithm>usingnamespacestd;typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkList;intInitList_L(LinkList&L){ L=newLNode; L->next=NULL; return 查看详情
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情
数据结构(线性表之单链表)(代码片段)
文章目录🥇为何要使用链表🥇单链表是什么单链表的数据存储方式🥇单链表之创建链表🥇单链表之打印链表🥇单链表之计算链表长度🥇单链表之增删查改单链表之头插法单链表之尾插法单链表之把一个... 查看详情
数据结构与算法-线性表之双向链表(代码片段)
...3561803.htmlhttps://blog.csdn.net/howlaa/article/details/385132351、概述线性表是一种线性结构，由数组、单项链表和双向链表组成，这里讲讨论双向链表的理论知识和实现代码。双向链表和单项链表类似，双向链表由两个指针作为指针域，分... 查看详情
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数... 查看详情
链表的初始化c语言(代码片段)
/*Byyangbocsu线性表之链表2021.07.20*/#include<stdio.h>#include<stdlib.h>/*预定义常量和类型*//*函数结果状态码*/#defineTRUE 查看详情
数据结构与算法-线性表之静态链表(代码片段)
前言：前面介绍的线性表的顺序存储结构和链式存储结构中，都有对对象地引用或指向，也就是编程语言中有引用或者指针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介 定义：用数组代替指针... 查看详情
数据结构学习总结线性表之单链表(代码片段)
一，回忆链表 链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs... 查看详情
算法习题---线性表之单链表的查找(代码片段)
一：问题已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该... 查看详情
数据结构之链表及实现(代码片段)
线性表的链式表示和实现线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。正由于这种特点，在做插入和删除操作时，需移动大量元素。链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，... 查看详情
数据结构与算法-线性表之循环链表(代码片段)
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说... 查看详情
线性链表之顺序表
/* @content线性链表之顺序表 @date2017-3-211:06 @authorJohnnyZen *//*线性表 顺序表 链式表[带头指针/不带头指针] 单链表 循环单链表 双向链表循环双链表 ADT& 查看详情