LinkedList与链表
LinkedList与链表
文章目录
- LinkedList与链表
- ArrayList的缺陷
- 链表
-
- 链表概念及结构
- 链表的实现
- LinkedList模拟实现
- LinkedList的使用
-
- 什么是LinkedList
- LinkedList的使用
- LinkedList的遍历
- ArrayList和LinkedList区别
ArrayList的缺陷
因为ArrayList底层是一段连续的空间，ArrayList 适合读多写少、随机访问频繁、单线程环境的场景，但在频繁插入 / 删除中间元素、多线程并发、存储大量基本数据类型等场景下，需考虑其缺陷并选择更合适的集合（如 LinkedList、CopyOnWriteArrayList 等）
具体例子：
场景：向 ArrayList中间频繁插入元素，对比 LinkedList 的性能差异
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;public class ArrayListDefectDemo { public static void main(String[] args) { List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); int size = 10000; // 数据量 // 向ArrayList中间插入元素 long start = System.currentTimeMillis(); for (int i = 0; i < size; i++) { arrayList.add(0, i); // 每次在头部（索引0）插入 } long arrayTime = System.currentTimeMillis() - start; // 向LinkedList中间插入元素 start = System.currentTimeMillis(); for (int i = 0; i < size; i++) { linkedList.add(0, i); // 同样在头部插入 } long linkedTime = System.currentTimeMillis() - start; System.out.println(\"ArrayList头部插入耗时：\" + arrayTime + \"ms\"); System.out.println(\"LinkedList头部插入耗时：\" + linkedTime + \"ms\"); }}运行结果：
ArrayList头部插入耗时：235msLinkedList头部插入耗时：3ms总结：
1.中间插入 / 删除频繁 → 用 LinkedList 更合适
2.多线程场景 → 用 CopyOnWriteArrayList 或同步集合
链表
链表概念及结构
链表是一种常见的线性数据结构，与数组不同，它的元素（称为 “节点”）在内存中非连续存储，而是通过指针（或引用）相互连接，形成链式结构。这种特性让链表在插入、删除操作上更灵活，但随机访问效率较低
常见链表类型：
nullprev指向上一个节点，next指向下一个节点），头节点prev为null，尾节点next为nullprev和next指针，时间复杂度O(1)LinkedList）null，而是指向头节点，形成环形结构prev指向尾节点，尾节点next指向头节点，形成环形结构注意⚠️：
1.链式结构在逻辑上是连续的，但是在物理上不一定是连续的
2.现实中的节点一般都是从堆上申请出来的
3.从堆上申请的空间是按照一定的策略来分配的，两次申请的空间，可能是连续的也可能不连续
链表的实现
import java.util.NoSuchElementException;// 单链表节点定义class ListNode { int val; // 数据域 ListNode next; // 指针域（指向下一个节点） // 构造方法 ListNode(int val) { this.val = val; this.next = null; }}// 单链表实现类public class SinglyLinkedList { private ListNode head; // 头节点 private int size; // 链表长度（元素个数） // 初始化空链表 public SinglyLinkedList() { head = null; size = 0; } /** * 1. 在链表头部插入元素 * 时间复杂度：O(1) */ public void addFirst(int val) { ListNode newNode = new ListNode(val); newNode.next = head; // 新节点指向原头节点 head = newNode; // 头节点更新为新节点 size++; } /** * 2. 在链表尾部插入元素 * 时间复杂度：O(n)（需遍历到尾节点） */ public void addLast(int val) { ListNode newNode = new ListNode(val); if (head == null) { // 空链表直接插入头部 head = newNode; } else { ListNode cur = head; while (cur.next != null) { // 遍历到尾节点 cur = cur.next; } cur.next = newNode; // 尾节点指向新节点 } size++; } /** * 3. 在指定索引位置插入元素（索引从0开始） * 时间复杂度：O(n)（需遍历到目标位置的前一个节点） */ public void add(int index, int val) { // 校验索引合法性 if (index < 0 || index > size) { throw new IndexOutOfBoundsException(\"索引越界：\" + index); } if (index == 0) { // 头部插入（复用addFirst） addFirst(val); return; } if (index == size) { // 尾部插入（复用addLast） addLast(val); return; } // 找到索引的前一个节点 ListNode prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } ListNode newNode = new ListNode(val); newNode.next = prev.next; // 新节点指向prev的下一个节点 prev.next = newNode; // prev指向新节点 size++; } /** * 4. 删除头部元素 * 时间复杂度：O(1) */ public int removeFirst() { if (head == null) { throw new NoSuchElementException(\"链表为空，无法删除\"); } int val = head.val; head = head.next; // 头节点后移一位 size--; return val; } /** * 5. 删除尾部元素 * 时间复杂度：O(n)（需遍历到倒数第二个节点） */ public int removeLast() { if (head == null) { throw new NoSuchElementException(\"链表为空，无法删除\"); } if (size == 1) { // 只有一个节点（直接删除头部） return removeFirst(); } // 找到倒数第二个节点 ListNode prev = head; while (prev.next.next != null) { prev = prev.next; } int val = prev.next.val; prev.next = null; // 断开与尾节点的连接 size--; return val; } /** * 6. 删除指定索引位置的元素 * 时间复杂度：O(n) */ public int remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界：\" + index); } if (index == 0) { // 删除头部（复用removeFirst） return removeFirst(); } // 找到索引的前一个节点 ListNode prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } int val = prev.next.val; prev.next = prev.next.next; // 跳过待删除节点 size--; return val; } /** * 7. 修改指定索引位置的元素 * 时间复杂度：O(n) */ public void set(int index, int val) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界：\" + index); } ListNode cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } cur.val = val; // 更新值 } /** * 8. 查找指定索引位置的元素 * 时间复杂度：O(n) */ public int get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界：\" + index); } ListNode cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } /** * 9. 查找元素首次出现的索引（不存在返回-1） * 时间复杂度：O(n) */ public int indexOf(int val) { ListNode cur = head; for (int i = 0; i < size; i++) { if (cur.val == val) { return i; } cur = cur.next; } return -1; } /** * 10. 判断链表是否为空 */ public boolean isEmpty() { return size == 0; } /** * 11. 获取链表长度 */ public int size() { return size; } /** * 12. 打印链表元素（以\"[a,b,c]\"格式） */ public void print() { if (isEmpty()) { System.out.println(\"[]\"); return; } StringBuilder sb = new StringBuilder(\"[\"); ListNode cur = head; while (cur != null) { sb.append(cur.val); if (cur.next != null) { sb.append(\",\"); } cur = cur.next; } sb.append(\"]\"); System.out.println(sb.toString()); } // 测试方法 public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); list.addLast(1); list.addLast(2); list.addFirst(0); list.add(2, 100); // 在索引2插入100 list.print(); // 输出：[0,1,100,2] System.out.println(\"索引1的值：\" + list.get(1)); // 输出：1 System.out.println(\"100的索引：\" + list.indexOf(100)); // 输出：2 list.set(3, 200); list.print(); // 输出：[0,1,100,200] list.remove(2); // 删除索引2的100 list.removeFirst(); list.print(); // 输出：[1,200] System.out.println(\"链表长度：\" + list.size()); // 输出：2 }}方法说明：
LinkedList模拟实现
import java.util.NoSuchElementException;// 链表节点类class ListNode { int val; ListNode next; // 构造方法 ListNode(int val) { this.val = val; this.next = null; }}// 单链表类public class SinglyLinkedList { // 头节点 private ListNode head; // 链表长度 private int size; // 构造方法，初始化空链表 public SinglyLinkedList() { head = null; size = 0; } // 1. 在链表头部添加元素 public void addFirst(int val) { ListNode newNode = new ListNode(val); newNode.next = head; head = newNode; size++; } // 2. 在链表尾部添加元素 public void addLast(int val) { ListNode newNode = new ListNode(val); // 如果链表为空，直接让头节点指向新节点 if (head == null) { head = newNode; } else { // 找到最后一个节点 ListNode current = head; while (current.next != null) { current = current.next; } current.next = newNode; } size++; } // 3. 在指定索引位置添加元素 public void add(int index, int val) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(\"索引越界: \" + index); } // 索引为0，相当于在头部添加 if (index == 0) { addFirst(val); return; } // 索引为size，相当于在尾部添加 if (index == size) { addLast(val); return; } // 找到要插入位置的前一个节点 ListNode prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } // 创建新节点并插入 ListNode newNode = new ListNode(val); newNode.next = prev.next; prev.next = newNode; size++; } // 4. 删除头节点 public int removeFirst() { if (isEmpty()) { throw new NoSuchElementException(\"链表为空，无法删除\"); } int val = head.val; head = head.next; size--; return val; } // 5. 删除尾节点 public int removeLast() { if (isEmpty()) { throw new NoSuchElementException(\"链表为空，无法删除\"); } // 如果只有一个节点 if (head.next == null) { int val = head.val; head = null; size--; return val; } // 找到倒数第二个节点 ListNode prev = head; while (prev.next.next != null) { prev = prev.next; } int val = prev.next.val; prev.next = null; size--; return val; } // 6. 删除指定索引位置的节点 public int remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界: \" + index); } // 索引为0，相当于删除头节点 if (index == 0) { return removeFirst(); } // 找到要删除节点的前一个节点 ListNode prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } int val = prev.next.val; prev.next = prev.next.next; size--; return val; } // 7. 查找指定索引位置的元素 public int get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界: \" + index); } ListNode current = head; for (int i = 0; i < index; i++) { current = current.next; } return current.val; } // 8. 修改指定索引位置的元素 public void set(int index, int val) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(\"索引越界: \" + index); } ListNode current = head; for (int i = 0; i < index; i++) { current = current.next; } current.val = val; } // 9. 查找元素的索引 public int indexOf(int val) { ListNode current = head; int index = 0; while (current != null) { if (current.val == val) { return index; } current = current.next; index++; } // 未找到返回-1 return -1; } // 10. 判断链表是否包含某个元素 public boolean contains(int val) { return indexOf(val) != -1; } // 11. 反转链表 public void reverse() { // 空链表或只有一个节点，无需反转 if (head == null || head.next == null) { return; } ListNode prev = null; ListNode current = head; ListNode next = null; while (current != null) { next = current.next; // 保存下一个节点 current.next = prev; // 反转指针 prev = current; // 移动prev current = next; // 移动current } head = prev; // 更新头节点 } // 12. 判断链表是否为空 public boolean isEmpty() { return size == 0; } // 13. 获取链表长度 public int size() { return size; } // 14. 清空链表 public void clear() { head = null; size = 0; } // 15. 打印链表元素 public void print() { if (isEmpty()) { System.out.println(\"链表为空\"); return; } StringBuilder sb = new StringBuilder(); ListNode current = head; while (current != null) { sb.append(current.val); if (current.next != null) { sb.append(\" -> \"); } current = current.next; } System.out.println(sb.toString()); } // 测试方法 public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); // 测试添加元素 list.addLast(1); list.addLast(2); list.addLast(3); list.addFirst(0); list.add(2, 5); System.out.print(\"添加元素后: \"); list.print(); // 输出: 0 -> 1 -> 5 -> 2 -> 3 // 测试获取和修改元素 System.out.println(\"索引2处的元素: \" + list.get(2)); // 输出: 5 list.set(2, 10); System.out.print(\"修改元素后: \"); list.print(); // 输出: 0 -> 1 -> 10 -> 2 -> 3 // 测试查找元素 System.out.println(\"元素10的索引: \" + list.indexOf(10)); // 输出: 2 System.out.println(\"是否包含元素2: \" + list.contains(2)); // 输出: true // 测试反转链表 list.reverse(); System.out.print(\"反转后: \"); list.print(); // 输出: 3 -> 2 -> 10 -> 1 -> 0 // 测试删除元素 list.remove(2); System.out.print(\"删除索引2处的元素后: \"); list.print(); // 输出: 3 -> 2 -> 1 -> 0 list.removeFirst(); list.removeLast(); System.out.print(\"删除头节点和尾节点后: \"); list.print(); // 输出: 2 -> 1 // 测试链表长度 System.out.println(\"链表长度: \" + list.size()); // 输出: 2 }}代码解析
这个单链表实现包含了以下核心部分：
1.节点类（ListNode）：
每个节点包含一个值（val）和一个指向下一个节点的引用（next）
2.链表类（SinglyLinkedList）：
包含头节点（head）和链表长度（size）两个成员变量，实现了一系列常用操作方法
3.主要方法说明：
增：addFirst()、addLast()、add()
删：removeFirst()、removeLast()、remove()
改：set()
查：get()、indexOf()、contains()
其他：reverse()（反转链表）、isEmpty()、size()等
4.反转链表的实现：
使用迭代方式，通过三个指针（prev、current、next）完成反转
时间复杂度 O (n)，空间复杂度 O (1)
LinkedList的使用
什么是LinkedList
LinkedList 是 Java 集合框架中一个重要的实现类，基于双向链表数据结构实现，继承自 AbstractSequentialList 并实现了 List、Deque 等接口。它不仅可以作为普通链表使用，还能当作队列（Queue）、双端队列（Deque）或栈（Stack）使用，功能十分灵活
注意⚠️：
1.LinkedList实现了List接口
2.LinkedList底层使用了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList在任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5.LinkedList比较适合任意位置插入的场景
LinkedList的使用
构造方法和常见使用方法：
LinkedList()LinkedList(Collection c)boolean add(E e)truevoid add(int index, E element)boolean addAll(Collection c)void addFirst(E e)void addLast(E e)add(E e) 功能相同）boolean offer(E e)add(E e)，在尾部添加元素，成功返回 trueboolean offerFirst(E e)addFirst(E e)，在头部添加元素，成功返回 trueboolean offerLast(E e)addLast(E e)，在尾部添加元素，成功返回 trueE get(int index)E getFirst()NoSuchElementException）E getLast()NoSuchElementException）E peek()peekFirst()，返回头部元素（若为空，返回 null）E peekFirst()null）E peekLast()null）E set(int index, E element)E remove()removeFirst()，删除并返回头部元素（若为空，抛出异常）E remove(int index)boolean remove(Object o)o 相等的元素，成功返回 trueE removeFirst()NoSuchElementException）E removeLast()NoSuchElementException）E poll()pollFirst()，删除并返回头部元素（若为空，返回 null）E pollFirst()null）E pollLast()null）int indexOf(Object o)o 相等的元素的索引，未找到返回 -1int lastIndexOf(Object o)o 相等的元素的索引，未找到返回 -1boolean contains(Object o)o，包含返回 true具体例子：
import java.util.LinkedList;import java.util.ArrayList;import java.util.NoSuchElementException;public class LinkedListMethodsDemo { public static void main(String[] args) { // 1. 构造方法示例 LinkedList<String> list = new LinkedList<>(); // 空构造 ArrayList<String> arrList = new ArrayList<>(); arrList.add(\"Java\"); arrList.add(\"Python\"); LinkedList<String> listFromCol = new LinkedList<>(arrList); // 从集合构造 System.out.println(\"从集合构造的LinkedList: \" + listFromCol); // 2. 添加元素方法 list.add(\"Apple\"); // 尾部添加 list.add(0, \"Banana\"); // 指定索引添加 list.addAll(listFromCol); // 添加另一个集合 list.addFirst(\"Grape\"); // 头部添加 list.addLast(\"Orange\"); // 尾部添加 list.offer(\"Mango\"); // 等价于add() list.offerFirst(\"Pineapple\"); // 等价于addFirst() System.out.println(\"添加元素后: \" + list); // 3. 获取元素方法 System.out.println(\"get(2)获取索引2的元素: \" + list.get(2)); System.out.println(\"getFirst()获取头部元素: \" + list.getFirst()); System.out.println(\"getLast()获取尾部元素: \" + list.getLast()); System.out.println(\"peek()获取头部元素: \" + list.peek()); System.out.println(\"peekLast()获取尾部元素: \" + list.peekLast()); // 4. 修改元素方法 String oldVal = list.set(3, \"Strawberry\"); // 修改索引3的元素 System.out.println(\"修改前的值: \" + oldVal + \"，修改后列表: \" + list); // 5. 删除元素方法 list.remove(1); // 删除索引1的元素 list.remove(\"Apple\"); // 删除指定元素 String first = list.removeFirst(); // 删除头部元素 String last = list.removeLast(); // 删除尾部元素 System.out.println(\"删除的头部元素: \" + first + \"，删除的尾部元素: \" + last); System.out.println(\"删除后列表: \" + list); String polled = list.poll(); // 等价于removeFirst() System.out.println(\"poll()删除的元素: \" + polled + \"，操作后列表: \" + list); // 6. 查找判断方法 System.out.println(\"Java的索引位置: \" + list.indexOf(\"Java\")); System.out.println(\"是否包含Python: \" + list.contains(\"Python\")); System.out.println(\"最后一个Python的索引: \" + list.lastIndexOf(\"Python\")); }}LinkedList的遍历
各遍历方式对比及注意事项：
import java.util.Iterator;import java.util.LinkedList;import java.util.ListIterator;public class LinkedListTraversal { public static void main(String[] args) { // 创建并初始化LinkedList LinkedList<String> fruits = new LinkedList<>(); fruits.add(\"Apple\"); fruits.add(\"Banana\"); fruits.add(\"Cherry\"); fruits.add(\"Date\"); System.out.println(\"原始链表: \" + fruits); // 1. 普通for循环（通过索引遍历） System.out.println(\"\\n1. 普通for循环遍历:\"); for (int i = 0; i < fruits.size(); i++) { System.out.print(fruits.get(i) + \" \"); } // 2. 增强for循环（foreach） System.out.println(\"\\n\\n2. 增强for循环遍历:\"); for (String fruit : fruits) { System.out.print(fruit + \" \"); } // 3. 迭代器（Iterator） System.out.println(\"\\n\\n3. Iterator遍历:\"); Iterator<String> iterator = fruits.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + \" \"); } // 4. 列表迭代器（ListIterator）- 支持双向遍历 System.out.println(\"\\n\\n4. ListIterator双向遍历:\"); System.out.print(\"正向遍历: \"); ListIterator<String> listIterator = fruits.listIterator(); while (listIterator.hasNext()) { System.out.print(listIterator.next() + \" \"); } System.out.print(\"\\n反向遍历: \"); while (listIterator.hasPrevious()) { System.out.print(listIterator.previous() + \" \"); } // 5. forEach()方法（Java 8+，使用Lambda表达式） System.out.println(\"\\n\\n5. forEach()方法遍历:\"); fruits.forEach(fruit -> System.out.print(fruit + \" \")); // 6. 迭代器遍历并删除元素（安全删除方式） System.out.println(\"\\n\\n6. 迭代器遍历并删除元素:\"); Iterator<String> iter = fruits.iterator(); while (iter.hasNext()) { String fruit = iter.next(); if (fruit.equals(\"Banana\")) { iter.remove(); // 安全删除当前元素 } } System.out.println(\"删除Banana后: \" + fruits); }}ArrayList和LinkedList区别
以下是ArrayList和LinkedList的主要区别，通过表格形式呈现：
