Java数据结构——LinkedList与链表
·
目录
一,链表（LinkedList）
1.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什么是LinkedList
LinkedList是java集合框架中List接口的双向链表实现。它没有RandomAccess接口，因此不支持高效随机访问（get(int index)时间复杂度O(N)）。
特点：
任意位置插入/删除效率高O(1),前提是已经持有节点引用
实现了Deque接口，可以用作双端队列
内存不连续，对CPU缓存不友好
相比ArrayList占用更多内存（每个节点存储两个引用）
3.2构造方法
LinkedList() :构造空链表
LinkedList(Collection<? extends E> c) ：用已有集合的元素构造链表
// 常用写法（接口引用实现类）
List<String> list = new LinkedList<>();
// 也可以用Collection初始化
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
List<String> 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遍历方法
LinkedList<Integer> list = new LinkedList<>();
list.add(1); list.add(2); list.add(3);
// 1. foreach
for (Integer num : list) {
System.out.print(num + " ");
}
// 2. 迭代器（正向）
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
// 3. 列表迭代器（支持反向）
ListIterator<Integer> lit = list.listIterator(list.size());
while (lit.hasPrevious()) {
System.out.print(lit.previous() + " ");
}四.ArrayList与LinkedList对比
| 特性 | ArrayList | LinkedList |
| 底层结构 | 动态数组 | 双向链表 |
| 物理存储 | 连续内存 | 非连续 |
| 随机访问 | O(1) | O(N) |
| 头部插入/删除 | O(N) | O(1) |
| 中间插入/删除 | O(N) | O(1) |
| 尾部插入/删除 | O(1) | O(1) |
| 内存占用 | 较小 | 较大 |
| 缓存友好性 | 高（数组连续，CPU预读） | 低 |
| 实现接口 |
RandomAccess （支持快速随机访问） |
Deque（双端队列） |
| 适用场景 |
频繁按索引访问， 主要在尾部操作 |
频繁在头/中插入删除， 需要双端队列功能 |
五,总结
链表的基本概念与分类
手动实现单向链表和双向链表的核心方法
LinkedList的构造，常用方法，遍历方式
更多推荐
9
0- 0
已为社区贡献20条内容
所有评论(0)