1.ArrayList的缺陷
由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。
2.链表
链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的，类似于火车的结构。
- 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
- 现实中的结点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或者双向：
带头或者不带头：
循环或者非循环：
链表的实现
// 无头单向非循环链表实现
public class SingleLinkedList {
// 定义链表节点类
private static class ListNode {
int data; // 节点数据
ListNode next; // 指向下一个节点的引用
ListNode(int data) {
this.data = data;
this.next = null;
}
}
private ListNode head; // 链表头节点，初始为 null 表示空链表
// 头插法：新节点插入到链表头部
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
newNode.next = head;
head = newNode;
}
// 尾插法：新节点插入到链表尾部
public void addLast(int data) {
ListNode newNode = new ListNode(data);
if (head == null) {
head = newNode;
return;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
// 任意位置插入，第一个数据节点为 0 号下标
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode newNode = new ListNode(data);
ListNode cur = head;
for (int i = 0; i < index - 1; i++) {
cur = cur.next;
}
newNode.next = cur.next;
cur.next = newNode;
}
// 查找是否包含关键字 key 是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
if (head == null) {
return;
}
if (head.data == key) {
head = head.next;
return;
}
ListNode cur = head;
while (cur.next != null && cur.next.data != key) {
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
}
}
// 删除所有值为 key 的节点
public void removeAllKey(int key) {
if (head == null) {
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null) {
if (cur.data == key) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
if (head.data == key) {
head = head.next;
}
}
// 得到单链表的长度
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
// 清空链表
public void clear() {
head = null;
}
// 打印链表数据
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
什么是LinkedList
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
总结：
- LinkedList实现了List接口。
- LinkedList的底层使用了双向链表。
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问。
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)。
- LinkedList比较适合任意位置插入的场景。
LinkedList的模拟实现
// 无头双向链表实现
public class MyLinkedList {
// 定义双向链表节点类
private static class ListNode {
int data; // 节点数据
ListNode prev; // 指向前一个节点的引用
ListNode next; // 指向后一个节点的引用
ListNode(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private ListNode head; // 链表头节点，初始为 null 表示空链表
// 头插法：新节点插入到链表头部
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
if (head == null) {
// 空链表时，新节点即为头节点
head = newNode;
} else {
// 新节点的 next 指向原头节点
newNode.next = head;
// 原头节点的 prev 指向新节点
head.prev = newNode;
// 头节点更新为新节点
head = newNode;
}
}
// 尾插法：新节点插入到链表尾部
public void addLast(int data) {
ListNode newNode = new ListNode(data);
if (head == null) {
// 空链表时，新节点直接作为头节点
head = newNode;
return;
}
ListNode cur = head;
// 遍历到链表尾部（cur.next == null 时是最后一个节点）
while (cur.next != null) {
cur = cur.next;
}
// 尾部节点的 next 指向新节点
cur.next = newNode;
// 新节点的 prev 指向原尾部节点
newNode.prev = cur;
}
// 任意位置插入，第一个数据节点为 0 号下标
// 需先检查下标合法性（越界抛异常，根据需求调整）
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
}
if (index == 0) {
// 下标 0 等价于头插
addFirst(data);
return;
}
if (index == size()) {
// 下标等于链表长度等价于尾插
addLast(data);
return;
}
ListNode newNode = new ListNode(data);
ListNode cur = head;
// 找到下标 index 对应的节点（待插入位置的节点）
for (int i = 0; i < index; i++) {
cur = cur.next;
}
// 新节点的 prev 指向 cur 的前驱
newNode.prev = cur.prev;
// 新节点的 next 指向 cur
newNode.next = cur;
// cur 原前驱的 next 指向新节点
cur.prev.next = newNode;
// cur 的 prev 指向新节点
cur.prev = newNode;
}
// 查找是否包含关键字 key 是否在链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.data == key) {
// 找到则返回 true
return true;
}
cur = cur.next;
}
// 遍历结束未找到返回 false
return false;
}
// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
if (head == null) {
// 空链表直接返回
return;
}
ListNode cur = head;
// 先找到要删除的节点
while (cur != null && cur.data != key) {
cur = cur.next;
}
if (cur == null) {
// 遍历完没找到 key，无需操作
return;
}
if (cur == head) {
// 处理头节点删除
head = cur.next;
if (head != null) {
// 新头节点的 prev 置空
head.prev = null;
}
} else {
// 待删除节点的前驱节点 next 指向待删除节点的后继
cur.prev.next = cur.next;
if (cur.next != null) {
// 待删除节点的后继节点 prev 指向待删除节点的前驱
cur.next.prev = cur.prev;
}
}
}
// 删除所有值为 key 的节点
public void removeAllKey(int key) {
if (head == null) {
// 空链表直接返回
return;
}
ListNode cur = head;
while (cur != null) {
if (cur.data == key) {
if (cur == head) {
// 处理头节点匹配的情况
head = cur.next;
if (head != null) {
head.prev = null;
}
} else {
// 非头节点匹配，调整前驱和后继的引用
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
}
}
}
// 继续遍历下一个节点
cur = cur.next;
}
}
// 得到链表的长度
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
// 打印链表数据（从前往后遍历输出）
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
// 清空链表（置空头节点，Java 中后续节点会被 GC 回收）
public void clear() {
head = null;
}
}
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());
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, 10); // 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());
}
LinkedList的遍历
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListTraversalExample {
public static void main(String[] args) {
// 创建并初始化LinkedList
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Date");
list.add("Eggplant");
System.out.println("原始链表: " + list);
System.out.println("--------------------------------");
// 1. 迭代器（Iterator）正向遍历
System.out.println("1. 迭代器正向遍历:");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("--------------------------------");
// 2. 迭代器（Iterator）逆向遍历
System.out.println("2. 迭代器逆向遍历:");
Iterator<String> reverseIterator = list.descendingIterator();
while (reverseIterator.hasNext()) {
System.out.println(reverseIterator.next());
}
System.out.println("--------------------------------");
// 3. 增强for循环（foreach）
System.out.println("3. 增强for循环:");
for (String element : list) {
System.out.println(element);
}
System.out.println("--------------------------------");
// 4. 普通for循环（通过索引）
System.out.println("4. 普通for循环:");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
ArrayList和LinkedList的区别
