看到这句话的时候证明：此刻你我都在努力
加油陌生人 
前言
今天给大家带来一篇有关Java顺序表和链表的文章，顺序表和链表我之前的专栏也是写过的，是用C语言实现的，也是模仿实现了顺序表和链表里的方法了。
认识List
Java中的List是java.util包下的一个接口，它是Collection接口的一个子接口，表示一个有序的集合，可以包含重复的元素。List接口提供了一些独特的方法来插入、访问、删除元素以及搜索列表中的元素。以下是List接口的一些关键特性和常用实现：
特性
- 有序性：
List中的元素按照添加的顺序进行排序。 - 允许重复：可以包含重复的元素。
- 动态数组：大多数
List实现（如ArrayList）使用动态数组来存储元素，这使得随机访问非常高效。
常用方法add(E e)：向列表末尾添加一个元素。
add(int index, E element)：在指定位置插入一个元素。
remove(int index)：移除指定位置的元素并返回被移除的元素。
remove(Object o)：移除列表中第一次出现的指定元素。
get(int index)：返回指定位置的元素。
set(int index, E element)：用指定元素替换列表中指定位置的元素。
size()：返回列表中的元素数量。
indexOf(Object o)：返回第一次出现的指定元素的索引。
lastIndexOf(Object o)：返回最后一次出现的指定元素的索引。
clear()：移除列表中的所有元素。
常用实现
ArrayList：基于动态数组实现，支持快速随机访问。但插入和删除操作可能需要数组复制，效率较低。
LinkedList：基于双向链表实现，适合频繁的插入和删除操作。但随机访问效率较低。
Vector：和ArrayList类似，但它是同步的。
Stack：继承自Vector，实现栈的功能，后进先出（LIFO）。
CopyOnWriteArrayList：线程安全的变体，在读多写少的场景下性能较好。
泛型
从Java 5开始，List接口支持泛型，允许开发者指定列表中元素的类型，提高类型安全。
使用场景
- 当你需要有序集合并且频繁进行随机访问时，选择
ArrayList。 - 当你需要频繁在列表中插入或删除元素，并且对随机访问的需求不高时，选择
LinkedList。
注意事项
List的实现不是线程安全的。如果需要线程安全，可以使用Collections.synchronizedList()方法或CopyOnWriteArrayList。- 选择合适的
List实现对于性能至关重要，因为不同的实现在不同的操作下表现不同。
List接口是Java集合框架中非常重要的一部分，合理选择和使用List可以提高程序的性能和可读性。
认识ArrayList（顺序表）
顺序表一个用数组实现的一个结构，他和数组不同的就是它是一个类，数组是一个引用类型，顺序表还扩展了一些方法
像增，删，查，改等是最基本的，还有一些其它方法，像List里的接口方法也实现了。
ArrayList是Java集合框架中的一种实现，属于List接口的实现类之一，同时也实现了RandomAccess接口，表明它支持快速的随机访问。
基本特性
- 基于数组：
ArrayList内部使用一个动态数组（Object数组）来存储元素。 - 动态扩容：当添加元素导致数组容量不足时，
ArrayList会自动扩容，通常是将现有容量增加到原来的1.5倍（或根据需要调整）。 - 允许空元素：可以包含
null值。 - 非同步：
ArrayList不是线程安全的。
性能特点
随机访问：由于基于数组实现，ArrayList提供了快速的随机访问能力，即get(int index)操作的时间复杂度为O(1)。
添加和删除：在列表末尾添加元素（add(E e)）是高效的，时间复杂度为O(1)。但是，如果需要在列表中间或开始位置添加或删除元素，可能需要移动其他元素以维持数组的连续性，这会导致时间复杂度为O(n)。
常用方法
代码演示：
import java.util.ArrayList; public class T { public static void main(String[] args) { ArrayList<Integer> arrayList1=new ArrayList<>(); //创建一个存储整数的顺序表 ArrayList<Character> arrayList2=new ArrayList<>(); //创建一个存储字符的顺序表 ArrayList<String> arrayList3=new ArrayList<>(); //创建一个存储字符串的顺序表 //给整形顺序表添加数据 arrayList1.add(1); arrayList1.add(2); arrayList1.add(3); //给字符顺序表添加数据 arrayList2.add('a'); arrayList2.add('b'); arrayList2.add('c'); //给字符串顺序表添加数据 arrayList3.add("abc"); arrayList3.add("abcd"); arrayList3.add("abcde"); //分别打印三个顺序表 System.out.println(arrayList1.toString()); System.out.println(arrayList2.toString()); System.out.println(arrayList3.toString()); //也可以单独取其中的元素进行打印 //如下取每个顺序表第一个元素进行打印 System.out.println(arrayList1.get(0)); System.out.println(arrayList2.get(0)); System.out.println(arrayList3.get(0)); } }
注：使用ArrayList前需先导入对应的包 ：import java.util.ArrayList;
上面代码中我只是简单使用了其中的几个方法，但是顺序表即：ArrayList类还自带许多方法呢。
这张图的方法仅仅只是ArrayList中2/3的方法呢，所以ArrayList功能还是很强大的。
顺序表之类的集合方法都有个非常厉害的功能，就是可以将另一个顺序表，一次性直接加入另一个顺序表。
代码演示：
public class T { public static void main(String[] args) { ArrayList<Integer> arrayList1=new ArrayList<>(); ArrayList<Integer> arrayList2=new ArrayList<>(); //给arrayList1添加数据 arrayList1.add(1); arrayList1.add(2); arrayList1.add(3); //给arrayList2添加数据 arrayList2.add(4); arrayList2.add(5); arrayList2.add(6); arrayList1.addAll(arrayList2); System.out.println(arrayList1.toString()); } }
这样是否见识到ArrayList的强大呢。
除了继承自Collection和List接口的方法外，ArrayList还提供了一些特定方法：
ensureCapacity(int minCapacity)：增加内部数组的容量至少为指定的最小容量，有助于减少扩容操作。
trimToSize()：将内部数组的大小调整为当前元素的数量，释放多余的内存。
扩容机制
当ArrayList中的元素数量达到当前数组容量时，会进行扩容操作：
创建一个新的数组，容量为原数组的1.5倍（加上原数组容量）。
将原数组中的所有元素复制到新数组中。
用新数组替换原数组。
使用场景
当你需要一个可以快速随机访问元素的集合时，ArrayList是一个好选择。
当元素的添加主要集中在列表末尾时，ArrayList的性能较好。
认识LinkedList（链表）
链表也是一个实现了List的一个类。它的功能和ArrayList比较相似，不同的是LinkedList是没有扩容机制的。
且他们在某些地方插入数据的时间复杂度是不一样的。
LinkedList 在 Java 中是一种实现了 List 和 Deque 接口的双向链表。
基本特性
双向链表：LinkedList 中的每个元素都是一个节点，包含数据和两个指针，分别指向前一个和后一个节点。
动态数组：链表的长度可以根据需要动态增长或缩小。
非线程安全：LinkedList 默认不是线程安全的。如果需要线程安全，可以使用 Collections.synchronizedList() 方法或 CopyOnWriteArrayList。
内部结构
LinkedList 的内部结构由 Node 内部类实现，每个 Node 对象包含：
item：存储数据。
next：指向下一个节点的引用。
prev：指向前一个节点的引用。
性能特点
插入和删除：在列表的头部或尾部进行插入和删除操作非常高效（O(1)），因为不需要移动其他元素。在列表中间进行这些操作需要 O(n) 时间复杂度，因为需要遍历到特定位置。
随机访问：由于链表的非连续性，随机访问（通过索引获取元素）的时间复杂度为 O(n)，因为需要从头开始遍历链表。
常用方法
代码演示：
import java.util.LinkedList; public class T { public static void main(String[] args) { LinkedList<Integer> linkedList1=new LinkedList<>();//创建一个存储整数的链表 LinkedList<Character> linkedList2=new LinkedList<>();//创建一个存储字符的链表 LinkedList<String> linkedList3=new LinkedList<>();//创建一个存储字符串的链表 //给整形顺序表添加数据 linkedList1.add(1); linkedList1.add(2); linkedList1.add(3); //给字符顺序表添加数据 linkedList2.add('a'); linkedList2.add('b'); linkedList2.add('c'); //给字符串顺序表添加数据 linkedList3.add("abc"); linkedList3.add("abcd"); linkedList3.add("abcde"); //分别打印三个顺序表 System.out.println(linkedList1.toString()); System.out.println(linkedList2.toString()); System.out.println(linkedList3.toString()); //也可以单独取其中的元素进行打印 //如下取每个顺序表第一个元素进行打印 System.out.println(linkedList1.get(0)); System.out.println(linkedList2.get(0)); System.out.println(linkedList3.get(0)); } }
链表也是支持addall（）方法的，也是可以将一个链表添加到另一个链表。
import java.util.LinkedList; public class T { public static void main(String[] args) { LinkedList<Integer> linkedList1=new LinkedList<>(); LinkedList<Integer> linkedList2=new LinkedList<>(); linkedList1.add(1); linkedList1.add(2); linkedList1.add(3); linkedList2.add(4); linkedList2.add(5); linkedList2.add(6); linkedList1.addAll(linkedList2); System.out.println(linkedList1.toString()); } }
除了继承自 List 的方法外，LinkedList 还提供了以下特有方法：
addFirst(E e) 和 addLast(E e)：在链表头部和尾部添加元素。
getFirst() 和 getLast()：获取链表头部和尾部的元素。
removeFirst() 和 removeLast()：移除链表头部和尾部的元素。
offerFirst(E e)、offerLast(E e)、pollFirst() 和 pollLast()：这些方法提供了双端队列的功能。
使用场景
当需要频繁地在列表的头部或尾部添加或删除元素时，LinkedList 是一个很好的选择。
当不需要频繁地进行随机访问时，LinkedList 可以提供比 ArrayList 更好的性能。
总结：
顺序表（如ArrayList）
基于数组：顺序表使用数组来存储元素，元素在内存中连续存放。
随机访问：支持快速的随机访问，即可以直接通过索引访问任意位置的元素（时间复杂度O(1)）。
动态扩容：当元素数量超过数组容量时，需要进行扩容操作，这通常涉及到创建更大的数组并复制现有元素。
插入和删除：在数组末尾添加元素非常快（时间复杂度O(1)），但在中间或开始位置插入或删除元素可能较慢，因为需要移动后续元素以维持连续性（时间复杂度O(n)）。
内存使用：通常比链表更紧凑，因为不需要额外存储指向其他元素的引用。
适用场景：适合于随机访问频繁的场景，以及在列表末尾添加元素的操作。
链表（如LinkedList）
基于节点：链表由一系列节点组成，每个节点包含数据和指向下一个（及前一个，对于双向链表）节点的指针。
非连续存储：元素在内存中可以是不连续的，通过指针连接。
动态大小：大小可以动态变化，不需要预先分配大量内存。
插入和删除：在已知前一个节点的情况下，可以在O(1)时间内完成，因为只需要改变几个指针。但在中间位置进行操作可能需要O(n)时间来找到前一个节点。
随机访问：不支持高效的随机访问，访问特定位置的元素需要从头开始遍历（时间复杂度O(n)）。
内存使用：每个节点需要额外存储至少一个（单向链表）或两个（双向链表）指针，因此内存使用相对较高。
适用场景：适合于插入和删除操作频繁的场景，尤其是在列表中间，以及不需要频繁随机访问元素的应用。
总结
顺序表适合于需要快速随机访问元素的场景，以及主要在列表末尾添加元素的情况。
链表适合于插入和删除操作频繁，尤其是在列表中间，且不经常进行随机访问的场景。
选择使用顺序表还是链表，取决于具体的应用需求和操作模式。理解它们的特点可以帮助开发者选择最合适的数据结构，以优化程序的性能。
. - 力扣（LeetCode）：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
. - 力扣（LeetCode）：逆置单链表
. - 力扣（LeetCode）：给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
. - 力扣（LeetCode）：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
. - 力扣（LeetCode）：合并两个有序链表
. - 力扣（LeetCode）：求环的路口
. - 力扣（LeetCode）：判断链表是否为环
. - 力扣（LeetCode）：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
需要答案可私聊我，当然官方也有题解唔。
