个人主页：爱编程的小新
不良人经典语录：”群雄侠隐仗剑，红颜相许半生”
目录
一. 链表的概念
二. 链表的结构特点
2.1 单向链表和双向链表
2.2循环链表和非循环链表
三.LinkedList
3.1 LinkedList的常见方法和使用
3.2 LinkedList的遍历
3.3 LinkedList的优缺点
四. ArrayList和LinkedList的区别
结语
在上期我们讲述了顺序表的概念和用法，但是顺序表的底层实际上是由数组实现的，当进行插入和删除元素的时候，时间复杂度为O(n)，效率是很低的，所以为了提升效率，那么就引入了链表的概念。
一. 链表的概念
链表与顺序表都是线性表中的一种，链表和顺序表在逻辑上都是连续的，但是链表是一种物理存储结构上非连续的存储结构，链表就像火车是由一个一个节点通过引用链接实现的：
链表的分类：有头链表和无头链表
- 有头链表：即头结点不存储实际数据，其指针指向第一个存储数据的节点；
- 无头链表：即没有头节点的链表，第一个节点直接存储数据，链表的头指针直接指向的就是第一个实际存储数据的节点；
二. 链表的结构特点
我们知道链表是由一系列节点组成的，每个节点又分为两个部分：数据域和指针域；那么我们来看一下几个链表结构。
2.1 单向链表和双向链表
单向链表：
1.节点结构：
- 数据域：用来存放数据元素
- 指针域：用来存放下一个节点的地址
2.特点：
- 单链表的节点只能通过指针指向下一个节点。形成一个单向的链状结构
- 只能从前往后的顺序的访问链表，无法从当前节点访问到前一个节点
双向链表：
1.节点结构：
- 数据域：与单链表一样，用来存放数据元素
- 指针域：拥有两个指针，一个指向前驱节点，一个指向后继节点
2.特点：
- 双链表可以从当前节点向前或者向后遍历链表，增加了操作的灵活性
- 在删除节点时，双链表比单链表更加方便，可以直接通过前驱结点找到前一个节点
2.2循环链表和非循环链表
循环链表：
1. 定义：
- 循环链表是一种特殊的链表结构，在单向循环链表中，最后一个节点的指针域指向 的不是null，而是该链表的头结点，从而形成一个环
- 在双向链表中，不仅最后一个节点的后继指针指向头结点，头结点的前驱节点也指向最后一个节点，形成双向的循环结构
非循环链表：
1.定义：
- 单向非循环链表每个节点只有指向下一个节点的指针，并且最后一个节点的指针域指向null
- 双向非循环链表每个节点有两个指针，分别指向前驱节点和后继节点，头指针的前驱指针为null，尾结点的后继指针为null
三.LinkedList
在Java中LinkedList是Java集合框架中的一个类，它实现了List接口，因此具有List的基本特征，LinkedList的底层是双向链表结构，使得它可以高效的在链表的任何位置进行插入和删除操作
LinkList的查阅文档
3.1 LinkedList的常见方法和使用
LinkedList的常见方法：
| 方法 | 解释 |
| boolean add(E e) | 尾插e |
| void add(int index,Eelement) | 将e插入到index位置 |
| boolean addAll(Collection<? extends E>c) | 尾插c中的元素 |
| E remove(int idnex) | 删除index位置元素 |
| boolean remove(Object o) | 删除遇到的第一个o |
| E get(int index) | 获得下标index位置元素 |
| E set(itn index,Eelement) | 将下标index位置元素设置为element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在下标 |
| int lastIndexOf(Object o) | 返回最后一个o的下标 |
| List<E>subList(int fromindex,int toIndex) | 截取部分list |
LinkedList中方法的使用：
public static void main(String[] args) {//实例化链表LinkedList<Integer>list=new LinkedList<>();LinkedList<Integer>list2=new LinkedList<>();//尾插list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list2.add(1);list2.add(2);list2.add(3);System.out.println("list中元素："+list);//打印链表1中的元素System.out.println("list2中的元素："+list2);//打印链表2中的元素list.add(0,0);//将0插入下标为0的位置list.addAll(list2);//将list2中的元素从尾部插入到list中、System.out.println("================");System.out.println("添加元素后的list中的元素："+list);//打印当前list中的元素list.remove(0);//删除0位置的元素list.remove((Object)1);//删除链表中遇到的第一个1System.out.println("================");System.out.println("删除元素后的list中的元素："+list);//打印当前list中的元素System.out.println("获得下标为5的元素："+list.get(5));list.set(5,10);//将下标5位置的元素改成10;System.out.println("将下标5位置的元素改变后的元素："+list.get(5));System.out.println("判断10是否在链表中："+list.contains(10));System.out.println("返回第一个1所在的下标"+list.indexOf(1));System.out.println("返回最后一个1所在的下标："+list.indexOf(1));System.out.println("================");System.out.println("list中的元素："+list);System.out.println("截取从下标2到下标5为止的元素(注意区间是前闭后开)："+list.subList(2,5));//前闭后开}
3.2 LinkedList的遍历
for循环遍历：
public static void main(String[] args) {LinkedList<Integer>list=new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}}foreach(增强for循环遍历)：
public static void main(String[] args) {LinkedList<Integer>list=new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for(Integer count:list){System.out.print(count+" ");}}
}迭代器遍历：
public static void main(String[] args) {LinkedList<Integer>list=new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//迭代器正向遍历ListIterator<Integer> ret=list.listIterator();while(ret.hasNext()){System.out.print(ret.next()+" ");}//迭代器反向遍历ListIterator<Integer> set=list.listIterator(list.size());while(set.hasPrevious()){System.out.print(set.previous()+" ");}}
}3.3 LinkedList的优缺点
（1）LinkedList的优点：
- 动态大小：链表的大小可以灵活的增加或者减小，在插入或者删除元素的时候，不需要像数组那样移动大量元素；
- 高效的插入和删除：在链表中间插入或者删除一个节点，只需要修改相邻节点的指针即可；时间复杂度为O(1)；
（2） LinkedList的缺点：
- 随机访问效率低：当访问链表中第n个元素时，需要从链表头结点开始遍历每个节点，不像数组可以直接通过索引进行访问；
- 额外的内存开销：每个节点除了存储数据，还要存储指向下一个节点（在单链表中）或前后节点（在双链表中）的指针，这会占用额外的内存空间；
- 遍历相对复杂：因为节点在内存中不是连续存储的，所以遍历操作比数组复杂，并且缓存性能不如数组好;
四. ArrayList和LinkedList的区别
| 不同点 | ArrayList | LinkedList |
| 在存储空间上 | 逻辑和物理上都是连续的 | 逻辑上连续，但是物理上不一定连续 |
| 随机访问 | 时间复杂度为O(1) | 时间复杂度为O(n) |
| 头插 | 需要往后搬运元素，时间复杂度为 | 只需要修改引用指向，时间复杂度为O(1) |
| 插入 | 空间不够需要扩容 | 没有扩容的概念 |
| 应用场景 | 元素高效存储和频繁访问 | 在任意位置插入和频繁删除元素 |
总结：当需要频繁访问元素的时候使用ArrayList效率是最好的，但是当需要频繁插入和删除元素时使用LinkedList效率是最好的
结语
以上就是本篇链表的内容啦，希望大家学习完顺序表和链表后，能够在不同的场景使用相应的存储结构存储元素来提高效率，在此感谢的大家的观看！！！
