ArrayList、LinkedList数据结构(线性表原理分析
1. 线性表描述
线性表是具有相同数据结构的n（n>=0）的数据元素的有序序列，其中n为表长，当n=0时线性表就是一个空表，若用L命名线性表，则其一般的表示为:
L=(a1,a2,a3,a4, ...,an)
线性表中的几个概念
- a1,为表头，an为表尾
除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个节点有且仅有一个直接后继，
线性表
线性表的存储/物理结构实现有:
- 顺序表(顺序存储)(java实现案例:ArrayList)
- 链表(链式存储)(java实现案例:LinkedList)
2. 顺序表:
- 定义:
用顺序存储的方式实现线性表。
顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻存储。元素之间的关系由存储单元的邻接关系来体现
顺序存储
- 顺序表的特点
- 随机访问->能在O(1)时间内找到第i个元素
- 存储密度高
- 扩展容量不方便
- 插入和删除不方便
- 顺序存储实现之一静态分配
通过创建顺序表的时候，定义一个固定长度的数组作为顺序表，从而避免了动态数组的开辟新数组，复制数组的过程，缺点在于，初始的时候需要计算好当前顺序表要插入多少数据，从而创建多长的顺序表
- 顺序存储实现之一动态分配
使用动态数组进行实现，定义一个固定长度的数组作为顺序表，当顺序表存满的时候，通过重写定义一个大于原先数组的新数组，作为新的顺序表，并且把原数组中的数据复制到新数组中，从而实现动态数组的效果。
优点:初始时候不需要考虑数组容量的大小，更灵活的存数据。
缺点: 需要重新创建新数组，复制原先数据数据到新数组，
- 顺序表的时间复杂度:
- 插入时间复杂度：最好为 O(1) 、最坏为O(n)、平均为O(n)。
- 删除时间复杂度: 最好为O(1)、最坏为O(n)、 平均为O(n)。
- 读取时间复杂度: 按位查找时间复杂度为O(1)、 按值查找的时间复杂度为O(n).
3. 链表(两种实现)
3.1 单链表
线性表的链式存储又称单链表，他是指通过一组任意的存储单元来存储线性表中
的元素。为了建立数据之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继结点的指针。
单链表图
3.1.1 单链表的两种实现:
- 带头节点的单链表
带头节点的单链表
-
创建单链表的时候先创建一个结点data不存储数据，而next指向头结点。
-
不带头节点的单链表
不带头节点的单链表
-
当没有头节点的时候不创建任何对象，创建单链表指向空，当由头节点的话指向头节点。
-
区别:
区别
3.1.2.单链表的建立
单链表的建立
单链表图
头插法: 每次有了新数据从头位置开始插入
尾插法: 每次有了新的数据从尾部开始插入
3.2 双链表
-
双链表在单链表的基础上结点多了一个指向前一个结点的指针，其余与单链表的情况全部一样。
双链表
-
时间复杂度分析:
链表插入一个数据: 查找位置时间复杂度为O(n), 插入的时间复杂度为O(1)
链表删除一个数据：查找位置时间复杂度为O(n),删除的时间复杂度为O(1)
链表获取一个数据: 查找的时间度为O(n).
