概述
线性表，是指将具有“一对一”关系的数据依次储存到物理空间中，这种储存结构又称为“线性储存结构”，在物理空间中有两种线性储存结构分别为：**顺序储存结构**和**链式储存结构**。
**顺序储存结构**是将数据集中存放，在物理内存空间中分配一块连续的空间，将数据依次储存在这块连续空间中，简称“顺序表”
**链式储存结构**是将数据分散存放，数据分散存放在物理内存空间中，通过维护“一根线”来保存数据之间的逻辑关系，简称“链表”
顺序表
在Java中，我们通常使用数组来定义顺序表，使用下标来访问数组中的元素，首元素的下标为0，尾元素的下标为长度-1
顺序表特点
优点内存地址连续，遍历速度快查找指定下标元素，速度块，时间复杂度为O(1)缺点
长度固定，必须提前预估长度
插入、删除元素时速度相对较慢,最坏情况下时间复杂度为O(n)
链表
与顺序表不同，链表的物理储存空间是分散的，链表中每个元素都由两部分组成：数据域和指针域。因此，为了体现各元素之间的逻辑关系，每个数据元素都维护了一个指针，指向自己的后继元素
数据域：数据元素所在的区域
指针域：指向后继元素的指针
链表特点
优点长度不固定，不需要提前预估长度内存空间不连续，可以充分利用内存空间插入、删除元素时速度块，时间复杂度为O(1)缺点相比于数组占用空间更大，除存放元素本身还要存放其指向下一个节点的指针遍历和查找指定元素速度慢，查找指定元素最坏情况下时间复杂度为O(n)
链表分类：单向链表、双向链表、循环链表、双向循环链表
单向链表：每一个Node节点都包含一个数据域和一个指针域，数据域item用于储存数据，指针域next指向下一个节点的指针next
双向链表：每一个Node节点都包含一个数据域和两个指针域，数据域item用于储存数据，指针域next指向下一个节点的指针，prev指向上一个节点的指针prev
循环链表：循环链表是一个特殊的单向链表，单向链表的尾节点指向null，而循环链表的尾节点的next节点指向首节点的next节点
双向循环链表：循环链表是一个特殊的双向链表，双向链表的首尾节点都指向null，而双向循环链表的尾节点的next节点指向首节点的next节点，而首节点的prev节点指向尾节点的prev节点
链表与顺序表的区别
链表顺序表物理内存空间不连续连续遍历速度慢快，适合读多写少的场景容量动态扩容长度固定查找元素慢，时间复杂度O(n)快，时间复杂度O(1)插入、删除元素效率高，适合读多写少的场景，时间复杂度O(1)效率低，时间复杂度O(n)开辟空间方式每次开辟一个节点的空间一次开辟，永久使用空间利用率空间位置随机，产生大量空间碎片，空间利用率低物理储存空间连续，空间利用率高
本文转载自: https://blog.csdn.net/w259149/article/details/127111427
版权归原作者 雾远望 所有， 如有侵权，请联系我们删除。
版权归原作者 雾远望 所有， 如有侵权，请联系我们删除。