1. 链表的概念
链表用于存储一系列元素，由一系列节点组成，每个节点包含两部分：数据域和指针域。
数据域：用于存储数据元素
指针域：用于指向下一个节点的地址，通过指针将各个节点连接在一起，形成一个链式结构。
注意：
链表在逻辑上是连续的，空间上并不是连续的
根据指针的连接方式，链表可以分为单向链表和双向链表
注意：
单向链表和双向链表的结点存在差异
2. 单向链表
单向链表是链表的一种，它的每个节点除了存储数据外，还包含一个指针指向下一个节点地址
2.1 单向列表的节点
每个节点只有一个指针，指向下一个节点。
最后一个节点的指针指向null，表示链表结束。
代码实现：
class ListNode{
int val;
ListNode next;//next指向新的节点
public ListNode(int val) {
this.val = val;
}
}注意：
结点一般都是从堆上申请出来，每次在堆上申请的空间，按照一种策略来进行分配，多次申请出来的空间，可能连续，也可能不连续
2.2 链表的创建
1. 创建一个节点
2.创建第二个节点，让第一个节点的指针域存放第一个节点的地址，以此类推，可以创建出链表
代码实现：
public void createList(){
//创建节点
ListNode listNode = new ListNode(15);
ListNode listNode1 = new ListNode(56);
ListNode listNode2 = new ListNode(45);
ListNode listNode3 = new ListNode(88);
//节点连接
listNode.next = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
this.head = listNode;
}注意：
不要忘记标注链表的头节点，当输出头节点时，会输出整个链表的数据
2.3 链表的种类
2.4 链表的基本操作
2.4.1 增加
（1）头插法
主要操作：
- 将新创建的节点的指针域更改为头节点的地址
- 将头节点的位置进行改变
public void addFirst(int data){
//代码不能交换
//必须先绑定信息
ListNode listNode = new ListNode(data);
listNode.next = head;
head = listNode;
}注意：代码的先后顺序不能颠倒，否则获取不到listNode.next的位置
（2）尾插法
主要操作：
- 将最后一个节点的指针域指向新节点的地址
特殊情况：
- 链表内没有一个节点，那么让新节点成为头节点
代码实现：
public void addLast(int data){
ListNode listNode = new ListNode(data);
ListNode cur = head;
if(cur==null){
head = listNode;
return ;
}
while(cur.next!=null){//关注next的指向,找到最后一个节点
cur = cur.next;
}
cur.next = listNode;
}（3）固定位置插入
主要操作：
- 找到要插入位置的前一个位置（cur）
- 让新节点的指针域指向要插入位置的旧节点
- 让cur指针域指向新节点的地址
注意：第二步和第三步不能交换位置，如果交换，会导致cur的位置发生改变，导致无法找到要插入位置的地址
代码实现：
public void addIndex(int index,int data){
if(index<0||index>size()){
System.out.println("位置有问题");
return;
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return ;
}
ListNode cur = head;
int count = 0;
ListNode listNode = new ListNode(data);
while(count<index-1){
cur =cur.next;
count++;
}
//不能互换位置
listNode.next = cur.next;
cur.next = listNode;
}
注意：
不要忘记检查，插入的位置是否合法
如果插入的位置为0；那么意味着头插法，位置为元素的长度，那么就是尾插法
2.4.2 删除
（1）删除第一个出现的元素
主要步骤：
- 找到你要删除元素的前一个节点
- 找到你要删除的节点
- 进行删除操作
代码实现：
public void remove(int data){
if(head ==null){
return;
}
if(head.val ==data){
head = head.next;
return;
}
//1.找到你要删除的前一个节点
ListNode cur = head;
int count = 0;
while(cur.next!=null){
if(cur.next.val == data){
break;
}
count++;
cur= cur.next;
}
//找到要删除的节点
ListNode del = head;
int delindex = 0;
while (del!=null){
if(del.val ==data){
break;
}
delindex++;
del = del.next;
}
//删除操作
cur.next = del.next;
}
注意：删除的具体操作就是：删除节点的前一个节点的指向发生改变，指向删除元素的指向
（2）删除出现的所有元素
主要步骤：
- 初始化两个节点，cur节点进行判断值是否相同，previous是cur节点的前一个结点，方便进行删除操作
- 进行遍历链表，找到相同的值，则进行删除操作，反之将两个节点都向后移动一位
代码实现：
if(head ==null){
return;
}
ListNode cur = head.next;
ListNode previous = head;
while(cur!=null){
if(cur.val==data){
previous.next = cur.next;
cur = cur.next;
}else{
previous = cur;//注意，小心写成 previous.next = cur;//错误
cur = cur.next;
}
}
if(head.val ==data){
head = head.next;
}
}注意：不要忘记对头节点进行判断
2.4.3 查看
（1）查看链表是否存在元素
public boolean contains(int value){
ListNode cur = head;
while(cur!=null){
if(cur.val==value){
return true;
}
cur = cur.next;
}
return false;
}主要步骤：
采用遍历的形式，如果找到元素，则返回true，反之，返回false
2.4.4 获取链表长度
int size(){
int count = 0;
ListNode cur = head;
while (cur!=null){
cur = cur.next;
count++;
}
return count;
}2.4.5 清空链表
void clear(){
ListNode cur = head;
ListNode curNext ;
while(cur!=null){
curNext = cur.next;
cur.next = null;
cur = curNext;
}
head = null;
}
}注意： 遍历链表逐个释放节点的引用，让每个节点不再被引用
3. 快慢指针
思想：通过使用两个速度不同的指针（快指针和慢指针）来遍历数据结构，从而实现特定的功能
注意：本质就是利用指针的移动速度差异来解决问题
常见的解决情况：
（1）找出中间的节点
ListNode findListNode(Text_2 list){
ListNode mid = head;
if(head == null){
return null;
}
if(head.next ==null){
return head;
}
int count = size(list);
int midCount = count/2;
while (midCount>0){
mid = mid.next;
midCount--;
}
return mid;
}这是解决这种问题，我们第一个想到的方法，需要遍历两次链表，获取长度和中间节点 ，复杂度高，下面是我们引用了快慢指针：
ListNode findListNode1(){
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){//不能交换
fast = fast.next.next;
slow = slow.next;
}
return slow;
}核心思想：使用快慢双指针，快的是慢的二倍；那么快的到了，慢的一定就在中间
（2）找出倒数第k个节点
ListNode findListNode(int k){
if(head ==null){
return null;
}
if(k<=0||k>size()){
System.out.println("k取值不对");
return null;
}
ListNode slow = head;
ListNode fast = head;
int count = k-1;
while (count>0){
fast = fast.next;
count--;
}
while(fast!=null&&fast.next!=null){
fast =fast.next;
slow =slow.next;
}
return slow;
}核心思想：快的比慢的先走了k-1个，然后每次都移动一个， 那么快的到了，满的就是倒数第k个.
先走k-1个，因为下标从0开始
4. 双向链表
双向链表是链表的一种，它的每个节点除了存储数据外，还包含两个指针：一个指向前一个节点，另一个指向下一个节点
4.1 双向列表的节点
注意：
由于有前驱指针，删除和插入操作更高效。
每个节点需要额外存储一个指针，因此比单向链表占用更多内存。
可以从头节点向后遍历，也可以从尾节点向前遍历。
代码实现：
class ListNode{
int val;
ListNode prev;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}4.2 LinkedList
在 Java 中，LinkedList是java.util 包中的一个类，LinkedList的底层使用了双向链表
4.3 LinkedList的使用
4.3.1 LinkedList的构造
（1）无参构造
//调用无参构造
List<Integer> list =new LinkedList<>();（2）利用Collection构建
List<Integer> list1 =new LinkedList<>();
list1.add(1);
list1.add(2);
list1.add(3);
System.out.println(list1);
List<Integer> list2 = new LinkedList<>(list1);
list2.add(2);
System.out.println(list2);注意：会继承传入实例对象的所有元素，并且元素的顺序也会保持一致
4.3.2 LinkedList的常用API
| boolean add(E e) | 尾插 |
| void add(int index, E element) | 在index位置添加元素 |
| boolean addAll(Collection<? extends E> c) | 将c中的所有元素插入进来 |
| E remove(int index) | 删除index下标的元素 |
| boolean remove(Object o) | 删除一个o元素 |
| E get(int index) | 获得index下标的元素 |
| E set(int index, E element) | 将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) | 截取顺序表的一部分 |
（1）增加
public class Add {
public static void main(String[] args) {
//尾插法
LinkedList<Integer> list =new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
System.out.println(list);
//插入固定位置
LinkedList<Integer> list1 = new LinkedList<>();
list1.add(0,1);
list1.add(0,6);
list1.add(1,9);
System.out.println(list1);
//尾插所有元素
Integer[] array = {9,99,999};
list.addAll(Arrays.asList(array));
System.out.println(list);
}
}
（2）删除
public class Remove {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
//删除下标的数
list.remove(2);
System.out.println(list);
//删除第一个出现的数
list.remove(new Integer(2));
System.out.println(list);
}
}
（3）修改
public class Set {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.set(1,999);
System.out.println(list);
}
}
（4）获取
public class Get {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
int x = list.get(2);
System.out.println(x);
}
}
（5）清空
public class Clear {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.clear();
System.out.println(list);
}
}
（6）查找
public class Contains {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
// 判断元素是否在表中
Boolean x = list.contains(2);
System.out.println(x);
// 返回第一个元素所在的下标
int a = list.indexOf(2);
System.out.println(a);
// 返回最后一个元素所在的下标
int b = list.lastIndexOf(2);
System.out.println(b);
}
}
（7）截取
public class Sublist {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(6);
list.add(9);
// LinkedList<Integer> list1 = new LinkedList<>(list.subList(1,4));//创建新的对象，进行操作，不会影响原来列表的数据
//subList返回值是List类型
List<Integer> list1 = list.subList(1,4);
list1.add(999);
list1.add(888);
list1.set(0,111);
System.out.println(list1);
System.out.println(list);
}
}
4.3.3 LinkedList的遍历
（1）for循环遍历
//1.
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();（2）for-each遍历
//2
for (int x : list){
System.out.print(x+" ");
}（3）使用迭代器
正向遍历
//3
Iterator<Integer> iterator = list.listIterator();//传数据
while (iterator.hasNext()){
System.out.print(iterator.next()+" ");
}
System.out.println();反向遍历
//4
ListIterator<Integer> listIterator = list.listIterator(list.size());
while (listIterator.hasPrevious()){
System.out.print(listIterator.previous()+" ");
}
System.out.println();注意：
（从前往后）while循环中的判断条件表示：是否存在下一个元素，如果存在，则获取迭代器的下一个元素并输出，因为 next 方法，所以在每次调用后进行移动1位
5. ArrayList和LinkedList的区别
| 差别 | ArrayList | LinkedList |
| 底层实现 | 基于动态数组实现 | 基于双向链表实现 |
| 访问效率 | 随机访问效率高 | 随机访问效率低 |
| 插入和删除效率 | 尾部插入和删除效率高 中间或头部插入和删除效率低 | 任意位置插入和删除效率高 |
| 内存占用 | 内存占用较少，因为只需要存储数据和数组容量。 可能存在内存浪费，因为数组会预留一定的容量 | 内存占用较多，因为每个节点需要存储数据以及前后指针。 |
总结：
ArrayList 适合频繁访问元素的场景，例如随机读取数据，适合元素数量相对固定的场景。
LinkedList 适合频繁插入和删除的场景，例如实现栈、队列，适合元素数量动态变化的场景。
