目录
1. ArrayList的缺陷
在上一节中，我们学习了ArrayList的基本用法，以及其特点。
那么，现在我们来思考一个问题，ArrayList有缺陷吗？
在上一节，我们学到ArrayList底层其实是一段连续的空间。
也就是说，在ArrayList任意位置插入或者删除元素时，我们都需要将后序元素整体往前移或者往后移，这样一来，时间复杂度就是O（n），效率是较低的。
综上所述，ArrayList是不适合用于任意位置插入和删除操作比较多的场景的。
因此，Java集合中引入了LinkedList结构，也就是链表结构。
2. 链表
2.1 链表的概念以及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
ps：
- 从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
- 现实中的节点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可以连续，也可能不连续。
而链表的结构其实是非常多样的。
1.单向或双向链表
2.带头或不带头链表
3.循环或非循环链表
尽管有这么多种链表结构，但我们重点只需掌握两种便OK。
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.2 链表的实现
这里，我们来简单实现一个无头单向非循环链表
import com.sun.xml.internal.bind.v2.model.core.EnumLeafInfo;
/**
* @Author @fiber-cloud
* 手写List
* @Date 2025/7/27 10:50
*/
public class MySingleList {
static class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;
//返回整个链表的长度
public int size(){
if (this.head == null){
return 0;
}
ListNode cur = this.head;
int count = 0;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
//打印链表中的数据，默认从头开始
public void display(){
ListNode cur = this.head;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
/**
* 从指定节点newHead开始打印链表
*/
public void display(ListNode cur){
ListNode cur1 = cur;
while (cur1 != null){
System.out.print(cur1.val+" ");
cur1 = cur1.next;
}
System.out.println();
}
//逆序打印
public void display2(ListNode cur){
if (cur == null){
return;
}
if (head.next == null){
System.out.print(head.val + " ");
return;
}
display2(head.next);
System.out.print(head.val + " ");
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int val){
ListNode cur = this.head;
while (cur != null){
if(cur.val == val){
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data){
ListNode cur = new ListNode(data);
cur.next = head;
head = cur;
}
//尾插法
public void addLast(int data){
ListNode cur = new ListNode(data);
ListNode temp = this.head;
if (temp == null){
this.head = cur;
}else {
while (temp.next != null){
temp = temp.next;
}
temp.next = cur;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) throws IndexWrongFulException {
//先检查输入的数据是否合法
if (index < 0 || index > size()){
System.out.println("index位置不合法");
throw new IndexWrongFulException("index位置不合法");
}
if (index == 0){
addFirst(data);
return;
}
if (index == size()){
addLast(data);
return;
}
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
//走index-1步
private ListNode findIndexSubOne(int index) {
ListNode cur = this.head;
while (index-1 != 0){
cur = cur.next;
index-- ;
}
return cur;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
//判断链表是否为空
if (this.head == null){
return;
}
if (this.head.val == key){
this.head = this.head.next;
return;
}
ListNode cur = findPrevOfKey(key);
if (cur == null){
System.out.println("没有你要删除的数据");
return;
}
ListNode temp = cur.next;
cur.next = temp.next;
}
//找到key的前驱节点
private ListNode findPrevOfKey(int key) {
ListNode cur = this.head;
while (cur.next != null){
if (cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
//删除整个链表中所有值为key的节点
public void removeAllKey(int key){
//判断链表是否为空
if (this.head == null){
return;
}
ListNode cur = this.head.next;
ListNode prev = this.head;
while (cur != null){
if (cur.val == key){
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
if (this.head.val == key){
this.head = this.head.next;
}
}
//倒数第K个节点
public ListNode FindKthToTail(int k){
if (k <= 0|| k >size()){
return null;
}
//快慢指针
ListNode slow = this.head;
ListNode fast = this.head;
//fast先走k-1步
while (k-1 != 0){
fast = fast.next;
if (fast == null){
return null;
}
k--;
}
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
//链表分割
public ListNode partition(ListNode pHead, int x) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//遍历链表
while (cur != null){
if (cur.val < x){
//第一次进行插入节点
if (bs == null ){
bs = cur;
be = cur;
}else {
be.next = cur;
be = be.next;
}
}else {
if (as == null){
as = cur;
ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//第一个段里面没有数据
if (bs == null){
return as;
}
be.next = as ;
if (as != null){
ae.next = null;
}
return bs;
}
//链表的回文结构
public boolean chkPalindrome(ListNode head) {
if (head == null){
return false;
}
if (head.next == null){
return true;
}
ListNode curNext = null;
//1.找到链表的中间节点
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
// 2.翻转中间节点后面的链表
ListNode cur = slow.next;
while (cur != null){
curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// 3.一个从头开始 一个从尾部开始
cur = head;
while (head != slow){
if (head.val != slow.val){
return false;
}
if (head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
//相交链表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1.求链表长度
ListNode pl = headA;//永远指向最长的链表
ListNode ps = headB;//永远指向最短的链表
int lenA = 0;
while (pl != null){
lenA++;
pl = pl.next;
}
int lenB = 0;
while (ps != null){
lenB++;
ps = ps.next;
}
pl = headA;
ps = headB;
int len = lenA - lenB;
if (len < 0){
pl = headB;
ps = headA;
len = lenB - lenA;
}
//2. 让最长的链表 先走len步
while (len != 0){
pl = pl.next;
len--;
}
// 3.pl和ps 现在在相同的起始位置
while (pl != ps){
pl = pl.next;
ps = ps.next;
}
// 走到这里，pl和ps相等了，pl == ps == null
if (pl == null){
return null;
}
return pl;
}
//环形链表
public boolean hasCycle(ListNode head) {
//追及相遇问题
if (head == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
return true;
}
}
return false;
}
//环形链表Ⅱ
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
ListNode temp = head;
while (temp != slow){
temp = temp.next;
slow = slow.next;
}
return temp;
}
}
return null;
}
}3.LinkedList的模拟实现
我们前面说到，LinkedList的底层其实是一个双向链表，这里我们来模拟实现一下。
/**
* @Author @fiber-cloud
* @Date 2025/7/28 20:32
* 模拟实现LinkedList
*/
public class MyLinkedList {
//LinkedList是一个双向链表
// prev指向的是前一个节点的地址
// next指向的是后一个节点的位置
static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;//标记双向链表的头部
public ListNode tail;//标记双向链表的尾巴
//从头到尾打印双向链表的每一个节点的值
public void display1(){
ListNode cur = this.head;
while (cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//得到单链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null){
cur = cur.next;
count++;
}
return count;
}
//清除链表
public void clear() {
ListNode cur = this.head;
while (cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
//头插法
public void addFirst(int data) {
ListNode d = new ListNode(data);
//当前链表只有一个节点
if (this.head == null){
this.head = d;
this.tail = d;
}else {
d.next = this.head;
this.head.prev = d;
head = d;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null){
this.head = node;
this.tail = node;
}else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) throws IndexWrongFulException {
//判断index的输入是否合法
if (index < 0 || index > size()){
throw new IndexWrongFulException("index位置不合法！");
}
//判断特殊位置，头插、尾插
if (index == 0){
addFirst(data);
return;
}
if (index == size()){
addLast(data);
return;
}
//在index插入值,找到index位置
ListNode cur = findIndexListNode(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
private ListNode findIndexListNode(int index) {
ListNode cur = this.head;
while (index != 0){
cur = cur.next;
index -- ;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = this.head;
//链表为null
if (this.head == null){
return false;
}else {
while (cur != null){
if (cur.val == key){
return true;
}else {
cur = cur.next;
}
}
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
ListNode cur = this.head;
while (cur != null){
if (cur.val == key){
if (cur == head){
head = head.next;
if (head != null){
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.tail = cur.prev;
}
}
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null){
if (cur.val == key){
if (cur == head){
head = head.next;
if (head != null){
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
}
4.LinkedList的使用
4.1 什么是LinkedList
LinkedList (Java Platform SE 8 )
在集合框架中，LinkedList也实现了List接口，具体如下：
ps：
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
4.2 LinkedList的使用
4.2.1. LinkedList的构造
方法 |
解释 |
LinkedList() |
无参构造 |
public LinkedList(Collection<? extends E> c) |
使用其他集合容器中元素构造List |
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}4.2.2. LinkedList的其他常用方法介绍
方法 |
解释 |
boolean add(E e) |
尾插 e |
void add(int index, E element) |
将 e 插入到 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) |
截取部分 list |
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}4.2.3. LinkedList的遍历
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}5. ArrayList和LinkedList的区别
特性 |
ArrayList |
LinkedList |
底层数据结构 |
动态数组 (可自动扩容的数组) |
双向链表 (每个节点包含数据、前驱、后继引用) |
随机访问性能 (get/set) |
极快 O(1)。 直接通过索引计算内存偏移量访问。 |
慢 O(n)。 需要从头或尾遍历链表找到索引位置。 |
头部插入/删除性能 |
慢 O(n)。 需要移动插入点之后的所有元素。 |
快 O(1)。 只需修改头节点和前几个节点的引用。 |
尾部插入/删除性能 |
快 O(1) (摊销)。 通常只需在数组末尾操作，偶尔触发扩容。 |
快 O(1)。 只需修改尾节点引用。 |
中间插入/删除性能 |
慢 O(n)。 需要移动插入点之后的所有元素。 |
相对慢 O(n)。 需要遍历找到位置，但找到后操作快 O(1) (只需修改相邻节点引用)。 |
内存占用 |
较低。 主要是存储数据的数组。可能有少量未使用的尾部空间。 |
较高。 每个元素都需要额外的空间存储前驱和后继引用。 |
空间局部性/CPU缓存 |
好。 元素在内存中连续存储，利于CPU缓存预取。 |
差。 元素分散在内存各处，缓存不友好。 |
迭代性能 |
快。 顺序访问数组元素非常高效。 |
快。 顺序访问链表节点也很高效。 |
内存回收 |
删除元素时，内部数组对应位置置 |
删除节点后，节点对象及其引用会被GC回收。 |
详细解释差异点
底层数据结构：
- ArrayList： 基于一个可动态调整大小的数组。当数组容量不足时，会创建一个更大的新数组（通常是原容量的1.5倍），并将旧数组的数据复制过去。元素在内存中是连续存储的。
- LinkedList： 基于双向链表。每个元素（节点）包含三个部分：实际存储的数据 (item)、指向下一个节点的引用 (next)、指向前一个节点的引用 (prev)。元素在内存中是分散存储的，通过指针连接。
随机访问性能：
- ArrayList： 访问任意索引 i 的元素 (get(i), set(i, element)) 非常快，时间复杂度是 O(1)。因为它可以通过简单的公式 base_address + i * element_size 直接计算出元素在内存中的位置。
- LinkedList： 访问索引 i 的元素需要从头节点（或尾节点，如果 i 靠近尾部）开始遍历链表，直到找到第 i 个节点。时间复杂度是 O(n)。对于大型列表，随机访问性能很差。
插入/删除性能：
- ArrayList：
- 尾部插入 (add(e))： 通常是 O(1)（摊销时间）。大部分情况下直接在数组末尾添加元素。只有当数组满了需要扩容时，复制操作是 O(n)，但扩容是偶尔发生的，平均（摊销）下来还是 O(1)。
- 头部/中间插入 (add(0, e), add(i, e)) 或删除 (remove(0), remove(i))： 非常慢，时间复杂度是 O(n)。因为需要将插入点/删除点之后的所有元素向后/向前移动一位来腾出空间/填补空缺。插入点越靠前，需要移动的元素越多。
- LinkedList：
- 头部/尾部插入/删除 (addFirst(e), addLast(e), removeFirst(), removeLast() 或 add(0, e), add(size(), e), remove(0), remove(size()-1))： 非常快，时间复杂度是 O(1)。因为只需要修改头节点/尾节点及其相邻节点的引用即可。
- 中间插入/删除 (add(i, e), remove(i))： 时间复杂度是 O(n)。但是！ 这个 O(n) 的时间主要用于遍历链表找到索引 i 对应的节点。一旦找到了目标节点（位置），实际的插入或删除操作本身只需要 O(1)，因为只需要修改目标节点前后相邻节点的引用即可，无需移动大量数据。如果应用程序能利用迭代器在遍历过程中进行插入删除（如 ListIterator.add(e) / ListIterator.remove()），则可以避免查找位置的 O(n) 开销，实现 O(1) 的操作。
内存占用：
- ArrayList： 主要占用内存的是存储数据的数组。数组可能会有一些未使用的尾部空间（为了减少频繁扩容）。每个元素本身只占用存储其数据所需的空间（不考虑对象头等开销）。
- LinkedList： 除了存储元素数据本身，每个节点还需要额外的空间（通常是两个引用，32位JVM上每个引用4字节，64位JVM通常也是4字节或8字节）来存储指向前驱节点和后继节点的引用。对于存储小对象（如 Integer, String）的链表，这些引用的额外开销可能比数据本身还大。
空间局部性与CPU缓存：
- ArrayList： 元素在内存中连续存储。现代CPU的缓存机制对这种连续访问模式非常友好，可以高效地预取数据到高速缓存中，显著提升顺序访问（迭代）和随机访问的速度。
- LinkedList： 元素分散在堆内存的不同位置。遍历链表时，访问下一个节点通常意味着访问一个全新的、可能不在缓存中的内存地址（指针追逐）。这会导致大量的缓存未命中（Cache Miss），降低访问速度，即使时间复杂度是 O(n)，实际耗时也可能比遍历相同大小的 ArrayList 慢很多。