目录一,链表LinkedList1.1链表的概念1.2链表的分类二..链表的实现手动模拟2.1无头单向非循环链表以int为例2.2无头双向链表三.LinkedList的使用3.1什么是LinkedList3.2构造方法3.3常用方法与ArrayList相似但是效率不同3.4遍历方法四.ArrayList与LinkedList对比五,总结一,链表LinkedList1.1链表的概念链表是一种物理存储结构上非连续的存储结构数据元素的逻辑顺序通过链表中的引用链接次序实现。在逻辑上链表是一条连续的链条在物理内存上节点可能散布在不同的地址每个节点通过存储下一个节点的地址来实现“串联”。特点节点动态申请从堆上分配空间利用率高无容量上限只要内存够。插入/删除元素只需要修改相邻节点的引用无需移动元素时间复杂度O(1)前提是已经知道插入/删除的位置不知道的话查找时间复杂度为O(N)。1.2链表的分类实际链表结构非常多样常见的分类组合可形成8种链表维度类型方向单向链表/双向链表头节点带头/不带头循环循环/非循环我们要重点掌握两种无头单向非循环链表结构简单常用作其他数据结构的子结构无头双向链表Java集合框架中LinkedList的底层实现JDK1.6之后为双向循环链表带头vs不带头头节点是一个不存储有效数据的哨兵节点可以简化插入/删除的边界处理。循环/非循环循环链表的尾节点指向头节点方便从任意节点遍历整个链表。二..链表的实现手动模拟2.1无头单向非循环链表以int为例// 节点类 class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val val; } } public class SingleLinkedList { private ListNode head; // 头节点引用 // 头插法 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(索引非法); } if (index 0) { addFirst(data); return; } ListNode prev findIndexPrevNode(index); ListNode newNode new ListNode(data); newNode.next prev.next; prev.next newNode; } private ListNode findIndexPrevNode(int index) { ListNode cur head; for (int i 0; i index - 1; i) { cur cur.next; } return cur; } // 查找是否包含关键字key public boolean contains(int key) { ListNode cur head; while (cur ! null) { if (cur.val key) return true; cur cur.next; } return false; } // 删除第一次出现的关键字key public void remove(int key) { if (head null) return; if (head.val key) { head head.next; return; } ListNode cur head; while (cur.next ! null) { if (cur.next.val key) { cur.next cur.next.next; return; } cur cur.next; } } // 删除所有值为key的节点 public void removeAllKey(int key) { if (head null) return; // 处理头节点 while (head ! null head.val key) { head head.next; } if (head null) return; ListNode prev head; ListNode cur head.next; while (cur ! null) { if (cur.val key) { prev.next cur.next; cur cur.next; } else { prev cur; cur cur.next; } } } // 获取链表长度 public int size() { int count 0; ListNode cur head; while (cur ! null) { count; cur cur.next; } return count; } // 清空链表 public void clear() { head null; // 所有节点变为不可达GC回收 } // 打印链表 public void display() { ListNode cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } }2.2无头双向链表class DoubleListNode { public int val; public DoubleListNode prev; public DoubleListNode next; public DoubleListNode(int val) { this.val val; } } public class MyLinkedList { private DoubleListNode head; // 头节点 private DoubleListNode tail; // 尾节点 // 头插 public void addFirst(int data) { DoubleListNode newNode new DoubleListNode(data); if (head null) { head tail newNode; } else { newNode.next head; head.prev newNode; head newNode; } } // 尾插 public void addLast(int data) { DoubleListNode newNode new DoubleListNode(data); if (head null) { head tail newNode; } else { tail.next newNode; newNode.prev tail; tail newNode; } } // 任意位置插入下标0开始 public void addIndex(int index, int data) { if (index 0 || index size()) throw new IndexOutOfBoundsException(); if (index 0) { addFirst(data); return; } if (index size()) { addLast(data); return; } DoubleListNode cur findNode(index); DoubleListNode newNode new DoubleListNode(data); newNode.prev cur.prev; newNode.next cur; cur.prev.next newNode; cur.prev newNode; } private DoubleListNode findNode(int index) { DoubleListNode cur head; for (int i 0; i index; i) { cur cur.next; } return cur; } // 删除第一次出现的key public void remove(int key) { DoubleListNode 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 if (cur tail) { tail tail.prev; tail.next null; } else { cur.prev.next cur.next; cur.next.prev cur.prev; } return; } cur cur.next; } } // 删除所有key public void removeAllKey(int key) { DoubleListNode 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 if (cur tail) { tail tail.prev; tail.next null; } else { cur.prev.next cur.next; cur.next.prev cur.prev; } } cur cur.next; } } public int size() { int count 0; DoubleListNode cur head; while (cur ! null) { count; cur cur.next; } return count; } public void display() { DoubleListNode cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } public void clear() { head tail null; } }三.LinkedList的使用3.1什么是LinkedListLinkedList是java集合框架中List接口的双向链表实现。它没有RandomAccess接口因此不支持高效随机访问get(int index)时间复杂度O(N)。特点任意位置插入/删除效率高O(1),前提是已经持有节点引用实现了Deque接口可以用作双端队列内存不连续对CPU缓存不友好相比ArrayList占用更多内存每个节点存储两个引用3.2构造方法LinkedList() :构造空链表LinkedList(Collection? extends E c) 用已有集合的元素构造链表// 常用写法接口引用实现类 ListString list new LinkedList(); // 也可以用Collection初始化 ArrayListString arrayList new ArrayList(); arrayList.add(A); ListString linkedList new LinkedList(arrayList);3.3常用方法与ArrayList相似但是效率不同方法描述boolean add(E e)尾部添加O(1)void add(int index,E element)指定位置插入需要先遍历O(N)E remove(int index)删除指定位置元素O(N)boolean remove(Object o)删除第一个匹配的元素E get(int index)获取元素O(N)E set(int index,E element)修改元素O(N)int indexOf(Object o)返回首次出现位置O(N)int lastIndexOf(Object o)返回最后出现位置O(N)3.4遍历方法LinkedListInteger list new LinkedList(); list.add(1); list.add(2); list.add(3); // 1. foreach for (Integer num : list) { System.out.print(num ); } // 2. 迭代器正向 IteratorInteger it list.iterator(); while (it.hasNext()) { System.out.print(it.next() ); } // 3. 列表迭代器支持反向 ListIteratorInteger lit list.listIterator(list.size()); while (lit.hasPrevious()) { System.out.print(lit.previous() ); }四.ArrayList与LinkedList对比特性ArrayListLinkedList底层结构动态数组双向链表物理存储连续内存非连续随机访问O(1)O(N)头部插入/删除O(N)O(1)中间插入/删除O(N)O(1)尾部插入/删除O(1)O(1)内存占用较小较大缓存友好性高数组连续CPU预读低实现接口RandomAccess支持快速随机访问Deque双端队列适用场景频繁按索引访问主要在尾部操作频繁在头/中插入删除需要双端队列功能五,总结链表的基本概念与分类手动实现单向链表和双向链表的核心方法LinkedList的构造常用方法遍历方式