LinkedList深入讲解
本文介绍了Java中LinkedList的模拟实现，主要包含双向链表的基础结构和核心方法。通过定义IList接口，实现了包括头插(addFirst)、尾插(addLast)、任意位置插入(addIndex)、查找(contains)、删除(remove/removeAllKey)等基本操作。重点展示了节点插入时的指针调整过程，并处理了链表为空和不为空两种场景。文章还包含下标合法性检查的异常处理，以
·
无头双向链表的基础结构
例子
一 : LinkedList的模拟实现
1.1 IList接口
public interface IList<T> {
// 头插法：在链表头部插入数据
void addFirst(T data) ;
// 尾插法：在链表尾部插入数据
void addLast(T data) ;
// 任意位置插入：第一个节点为0号下标
void addIndex(int index, T data) ;
// 查找：判断关键字key是否存在
boolean contains(T key) ;
// 删除：移除第一次出现的key节点
void remove(T key);
// 删除：移除所有值为key的节点
void removeAllKey(T key) ;
// 统计：获取链表长度
int size() ;
// 清空：释放链表所有节点
void clear() ;
// 遍历：打印链表所有元素
void display() ;
}
1.2 基础结构定义
public class MyLinkedList<T> implements IList<T>{
//静态内部类:链表节点
static class ListNode<T>{
public T val;//数据域
public ListNode<T> prev;//引用域(上一个节点的引用)
public ListNode<T> next;//引用域(下一个节点的引用)
public ListNode(T val) {
this.val = val;
}
}
public ListNode<T> head;//链表的头引用
public ListNode<T> last;//链表的尾引用
@Override
public void addFirst(T data) {
}
@Override
public void addLast(T data) {
}
@Override
public void addIndex(int index, T data) {
}
@Override
public boolean contains(T key) {
return false;
}
@Override
public void remove(T key) {
}
@Override
public void removeAllKey(T key) {
}
@Override
public int size() {
return 0;
}
@Override
public void clear() {
}
@Override
public void display() {
}
}
(1) void display()
public void display() {
ListNode<T> cur = this.head;
while(cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
(2) void addFirst(T data)
链表不为空时
链表为空时
public void addFirst(T data) {
ListNode<T> node = new ListNode<>(data);
if(this.head == null) {
this.head = node;
this.last = node;
}else{
node.next = this.head;// 1. 新节点的 next 指向当前的头
this.head.prev = node;// 2. 当前头的 prev 指向新节点
this.head = node;// 3. 更新 head 指针指向新节点
}
}
(3) void addLast(T data)
链表不为空时
链表为空时
public void addLast(T data) {
ListNode<T> node = new ListNode<>(data);
if(this.head == null) {
this.head = node;
this.last = node;
}else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
(3) boolean contains(T key)
public boolean contains(T key) {
ListNode<T> cur = this.head;
while(cur != null) {
if(cur.val.equals(key)){
return true;
}
cur = cur.next;
}
return false;
}
(4) int size()
public int size() {
ListNode<T> cur = this.head;
int count = 0;
while(cur != null) {
count++;
cur = cur.next;
}
return count;
}
下标不合法异常
public class IllegalIndexException extends RuntimeException{
public IllegalIndexException() {
}
public IllegalIndexException(String message) {
super(message);
}
}
(5) void addIndex(int index, T data)
public void addIndex(int index, T data) {
int len = size();
if(index < 0 || index > len) {
throw new IllegalIndexException("下标不合法异常");
}
//头插
if(index == 0) {
addFirst(data);
return;
}
//尾插
if(index == len) {
addLast(data);
return;
}
//中间位置插
ListNode<T> cur = search(index);
ListNode<T> node = new ListNode<>(data);//实例化一个节点
//修改指向
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
/**
* 找到index位置节点
* @param index
* @return
*/
private ListNode<T> search(int index) {
ListNode<T> cur = this.head;
int count = 0;
while(count < index) {
count++;
cur = cur.next;
}
return cur;
}
(6) void remove(T key)
1.要删除的元素在头节点
(1)有很多节点
(2)只有一个节点
2.要删除的元素在中间位置
3.要删除的元素在尾节点
public void remove(T key) {
// 定义当前节点，从头开始遍历
ListNode<T> cur = this.head;
// 1. 遍历链表，查找要删除的节点
while (cur != null) {
// 找到目标节点（值相等）
if (cur.val.equals(key)) {
// ===== 情况1：删除的是头节点 =====
if (cur == this.head) {
// 头指针后移
this.head = this.head.next;
// 如果删除后链表为空
if (this.head == null) {
this.last = null; // 尾节点也置空
} else {
this.head.prev = null; // 新头节点的 prev 置空
}
} else {
// ===== 情况2：删除的是尾节点 =====
if (cur.next == null) {
// 尾指针前移
this.last = this.last.prev;
// 新尾节点 next 置空
this.last.next = null;
} else {
// ===== 情况3：删除的是中间节点 =====
// 前一个节点指向后一个节点
cur.prev.next = cur.next;
// 后一个节点指向前一个节点
cur.next.prev = cur.prev;
}
}
// 删除完成，直接返回（只删除一个）
return;
}
// 继续遍历下一个节点
cur = cur.next;
}
}
(7) void removeAllKey(T key)
public void removeAllKey(T key) {
// 当前节点，从头开始遍历
ListNode<T> cur = this.head;
// 1. 遍历整个链表（删除所有等于 key 的节点）
while (cur != null) {
// 判断当前节点是否是要删除的节点
if (cur.val.equals(key)) {
// ===== 情况1：删除的是头节点 =====
if (cur == this.head) {
// 头指针后移
this.head = this.head.next;
// 如果删除后链表为空
if (this.head == null) {
this.last = null; // 尾节点也置空
} else {
this.head.prev = null; // 新头节点 prev 置空
}
} else {
// ===== 情况2：删除的是尾节点 =====
if (cur.next == null) {
// 尾指针前移
this.last = this.last.prev;
// 新尾节点的 next 置空
this.last.next = null;
} else {
// ===== 情况3：删除的是中间节点 =====
// 前驱节点指向后继节点
cur.prev.next = cur.next;
// 后继节点指向前驱节点
cur.next.prev = cur.prev;
}
}
}
// 继续遍历下一个节点
cur = cur.next;
}
}
(8) void clear()
public void clear() {
// 从头节点开始遍历整个链表
ListNode<T> cur = this.head;
// 1. 逐个节点断开引用，帮助 GC 回收
while (cur != null) {
// 先保存下一个节点（避免断链后找不到后续节点）
ListNode<T> nextNode = cur.next;
// 将当前节点的数据置空
cur.val = null;
// 断开前驱指针
cur.prev = null;
// 断开后继指针
cur.next = null;
// 移动到下一个节点
cur = nextNode;
}
// 2. 将头尾指针置空，表示链表已清空
this.head = null;
this.last = null;
}
二: LinkedList详解
2.1 LinkedList 的构造方法
| 方法 | 解释 |
|---|---|
| LinkedList( ) | 无参构造，创建一个空的 LinkedList |
| LinkedList(Collection<? extends E> c) | 创建一个包含指定集合中所有元素的链表 |
使用示例
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String[] args) {
// 构造空的 LinkedList
List<String> list1 = new LinkedList<>();
list1.add("JavaSE");
list1.add("数据结构");
list1.add("算法");
System.out.println(list1);
//构造一个包含指定集合中所有元素的链表
List<String> list2 = new LinkedList<>(list1);
System.out.println(list2);
}
}
//运行结果
[JavaSE, 数据结构, 算法]
[JavaSE, 数据结构, 算法]
2.2 LinkedList 的常用方法
LinkedList 提供了丰富的方法用于操作元素，以下是核心方法：
| 方法 | 解释 | 备注 |
|---|---|---|
| boolean add(E e) | 将元素 e 追加到链表末尾 | 成功返回 true |
| void add(int index,E element) | 在索引 index 处插入元素 element | 索引从 0 开始 |
| boolean addAll(Collection<? extends E> c) | 将集合 c 中的所有元素按顺序追加到末尾 | 只要链表改变就返回 true |
| E remove(int index) | 移除指定索引处的元素，并返回该元素 | 会触发后续元素前移 |
| boolean remove(Object o) | 移除链表中第一个与 o 相等的元素 | 依据 equals 方法判断 |
| E get(int index) | 返回指定索引处的元素 | 不改变链表结构 |
| E set(int index,E element) | 用 element 替换索引 index 处的元素，返回原值 | 属于更新操作 |
| void clear() | 移除链表中的所有元素 | 链表长度变为 0 |
| boolean contains(Object o) | 检查链表中是否包含至少一个元素 o | 返回 true/false |
| int indexOf(Object o) | 返回 o 首次出现的索引，不存在则返回 -1 | 从头向后搜索 |
| int lastIndexOf(Object o) | 返回 o 最后一次出现的索引，不存在则返回 -1 | 从后向前搜索 |
| List< E> subList(int fromIndex,int toIndex) | 返回索引从 from 到 to (左闭右开) 的视图 | 对该视图的修改会反映在原列表中 |
使用示例
public class Test {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
//默认尾插
linkedList.add("JavaSE");
linkedList.add("数据结构");
System.out.println(linkedList);//[JavaSE, 数据结构]
//尾插
linkedList.addLast("算法");
//头插
linkedList.addFirst("Java之旅");
System.out.println(linkedList);//[Java之旅, JavaSE, 数据结构, 算法]
//任意位置插入
linkedList.add(3,"Mysql");
System.out.println(linkedList);//[Java之旅, JavaSE, 数据结构, Mysql, 算法]
//删除指定索引处的元素,并返回该元素
System.out.println(linkedList.remove(0));//Java之旅
System.out.println(linkedList);//[JavaSE, 数据结构, Mysql, 算法]
linkedList.add(0,"Java之旅");
linkedList.add(1,"Java之旅");
System.out.println(linkedList);//[Java之旅, Java之旅, JavaSE, 数据结构, Mysql, 算法]
//移除链表中第一个与o相等的元素
linkedList.remove("Java之旅");
System.out.println(linkedList);//[Java之旅, JavaSE, 数据结构, Mysql, 算法]
//返回指定索引处的元素
System.out.println(linkedList.get(2));//数据结构
//用 element 替换索引 index 处的元素，返回原值
System.out.println(linkedList.set(0, "Java成神之路"));//Java之旅
System.out.println(linkedList);//[Java成神之路, JavaSE, 数据结构, Mysql, 算法]
//检查链表中是否包含至少一个元素 o
System.out.println(linkedList.contains("数据结构"));//true
// 返回 o 首次出现的索引，不存在则返回 -1
System.out.println(linkedList.indexOf("数据结"));//-1
System.out.println(linkedList.indexOf("数据结构"));//2
// 返回 o 最后一次出现的索引，不存在则返回 -1
System.out.println(linkedList);//[Java成神之路, JavaSE, 数据结构, Mysql, 算法]
System.out.println(linkedList.lastIndexOf("数据结构"));//2
linkedList.add(3,"数据结构");
System.out.println(linkedList);//[Java成神之路, JavaSE, 数据结构, 数据结构, Mysql, 算法]
System.out.println(linkedList.lastIndexOf("数据结构"));//3
System.out.println(linkedList.lastIndexOf("数控技术"));//-1
//返回索引从 from 到 to (左闭右开) 的视图
List<String> temp = linkedList.subList(1,4);
System.out.println(temp);//[JavaSE, 数据结构, 数据结构]
temp.remove("数据结构");
System.out.println(temp);//[JavaSE, 数据结构]
System.out.println(linkedList);//[Java成神之路, JavaSE, 数据结构, Mysql, 算法] 对该视图的修改会反映在原列表中
LinkedList<String> linkedList2 = new LinkedList<>();
//将集合 c 中的所有元素按顺序追加到末尾
linkedList2.addAll(linkedList);
System.out.println(linkedList2);//[Java成神之路, JavaSE, 数据结构, Mysql, 算法]
//移除链表中的所有元素
linkedList2.clear();
System.out.println(linkedList2);//[]
}
}
2.3 LinkedList 的遍历方式
public class Test {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
// 1. foreach 遍历
for (int x : linkedList) {
System.out.print(x + " ");
}
System.out.println(); // 1 2 3 4
// 2. ListIterator迭代器正向遍历
ListIterator<Integer> list = linkedList.listIterator();
while(list.hasNext()) {
System.out.print(list.next() + " ");//1 2 3 4
}
System.out.println();
// 3. ListIterator迭代器反向遍历
while(list.hasPrevious()) {
System.out.print(list.previous() + " ");//4 3 2 1
}
System.out.println();
// 4.for循环
for (int i = 0; i < linkedList.size(); i++) {
System.out.print(linkedList.get(i) + " ");//1 2 3 4
}
System.out.println();
// 5.Iterator迭代器遍历
Iterator<Integer> it = linkedList.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");//1 2 3 4
}
System.out.println();
}
}
2.4 ArrayList 与 LinkedList 的区别
| 维度 | ArrayList(基于数组) | LinkedList(基于双向链表) |
|---|---|---|
| 底层数据结构 | Object[ ] | 双向链表(每个节点存储数据,前驱和后继指针) |
| 随机访问 | 高效(O(1)) | 低效(O(n)),需要从头或尾遍历 |
| 中间增删 | 低效(O(n)),需要移动大量元素 | 高效(O(n),找到位置后),只需修改指针 |
| 首尾增删 | 尾部高效(平摊O(1),末尾操作),但可能涉及到扩容 | 高效O(1),直接修改头尾指针 |
| 线程安全 | 非线程安全 | 非线程安全 |
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
19
0- 0
已为社区贡献2条内容
所有评论(0)