数据结构 顺序表与链表

📕1. 线性表（linear list）

在集合框架中，List是一个接口。从数据结构的角度看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

常见的线性表：顺序表、链表、栈、队列……

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

线性结构规定：一个元素只能有一个前驱，一个后继。如果有多个前驱或后继，就不是线性结构。

💡注意：List是个接口，并不能直接用来实例化。

如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

ArrayList ⇒ 顺序表
LinkedList ⇒ 链表

📕2. ArrayList与顺序表

✏️2.1 顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组上完成数据的增删查改。

✏️2.2 ArrayList简介

在集合框架中，ArrayList是⼀个普通的类，实现了List接口，具体框架图如下：

💡注意：

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

✏️2.3 ArrayList的构造

方法	解释
ArrayList()	无参构造
ArrayList(int initialCapatity)	指定顺序表初始容量

public static void main(String[] args) {List<Integer> l1 = new ArrayList<>(); //实例化一个空表，推荐写法List<Integer> l2 = new ArrsyList<>(10); //实例化一个初始容量为10的空表List<Integet> l3 = new ArrayList<>(l2); //实例化出的l3,与l2中的元素一致
}

✏️2.4 ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，可以查看JAVA帮助手册。（可以我找要）

方法	解释
boolean add(E e)	尾插e
void add(int index,E e)	把e插入到 index位置
E remove（int index）	删除index位置的元素
E get(int index)	获取index位置的元素
E set(int index,E e)	将index位置元素设置为e
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexof(Object o)	返回第一的o所在的下标
int lastindexof(Object o)	返回最后一个o所在下标

💡特别提醒：虽然ArrayList中提供了常见的方法，但是我们仍需掌握方法的底层原理。

✏️2.5 ArrayList的遍历

ArrayList可以使用三种方法进行遍历：

1. for循环

public static void main(String[] args) {List<Integer> l1 = new ArrayList<>();l1.add(1);l1.add(2);l1.add(3);l1.add(4);l1.add(5);	l1.add(6);for(int i = 0;i<l1.size();i++){System.out.println(l1.get(i));}
}

2. for-each

public static void main(String[] args) {List<String> l2 = new ArrayList<>();l2.add("1");l2.add("2");l2.add("3");l2.add("4");for (String l : l2){System.out.println(l);}
}

注意：并不是所有的类都能写进for-each循环中，写进for-each循环中的类要求必须实现Iterable接口

3. 迭代器

public static void main(String[] args) {List<String> l3 = new ArrayList<>();l3.add("1");l3.add("2");l3.add("3");l3.add("4");Iterator<String> iterator = l3.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}}

ArrayList最常使用的遍历方式是：for循环 以及 foreach

✏️2.6 ArrayList的自动扩容机制

ArrayList内部持有一个数组，构造时设置的初始容量就是数组的大小，当ArrayList发现空间不够的时候，就会申请额外的空间，这就自动扩容机制。

自动扩容共有以下几步：

1. 发现空间不够之后，立刻创建一个更大的数组（为了防止申请空间过大浪费，ArrayList的策略是每次扩容为原来大小的1.5倍）
2. 把旧数组中的元素拷贝到新的数组中
3. 添加新的元素
4. 自动释放旧数组

✏️2.7 ArrayList常用方法的具体实现代码（重点！！！）

点击传送源代码

1. 以int类型为例，真正存储数据的是数组，顺序表本身就是基于数组的封装

2. 提供构造方法
   

3. 获取元素个数
   

4. 自动扩容操作
   

5. add方法
   
   

6. get方法
   

7. remove方法
   
   

8. toString方法
   

9. contains方法
   

10. clear方法
    

11. indexof方法
    

12. lastIndexOf方法
    

13. set方法
    

✏️2.8 ArrayLsit当前面临的问题

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O（N）。

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈1.5倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到150，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了45个数据空间。

为了解决以上问题，于是我们引入了链表，可实际上链表真的会解决这些问题吗？还是会带来更多的问题呢？请您继续往下阅读…………

📕3. LinkedList与链表

链表是⼀种物理存储结构上⾮连续存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的 。

✏️3.1 链表的概念

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

1. 单向或双向
2. 带头或者不带头
3. 循环或者非循环

然有这么多的链表的结构，但是我们重点掌握两种：

1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦
   结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
   

2. ⽆头双向链表：在Java的集合框架库中LinkedList底层实现就是⽆头双向循环链表。

✏️3.2 LinkedList简介

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引⽤将节点连接起来了，因此在在任意位置插⼊或者删除元素时，不需要搬移元素，效率⽐较⾼。

在集合框架中，LinkedList也实现了List接⼝，具体如下：

注意：

1. LinkedList实现了List接口
2. LinkedList的底层使⽤了双向链表
3. LinkedList的任意位置插⼊和删除元素时效率⽐较⾼，时间复杂度为O(1)

✏️3.3 LinkedList的构造

✏️3.4 LinkedList常见操作

✏️3.5 LinkedList常用方法的具体实现代码（重点！！！）

单向链表底层代码实现
双向链表底层代码实现

📕4. ArrayList和LinkedList的区别