从0到1手撕双向链表，再到LinkedList源码拆解，这篇数据结构干货让你直接逆袭成大佬
【前言】
在Java开发中， LinkedList 是集合框架里的重要成员，其底层基于双向链表实现。对于开发者来说，搞清楚双向链表的工作机制，能让我们更精准地运用 LinkedList ，还能提升对数据结构选型的把控力。本文先带你吃透双向链表的模拟实现，涵盖节点设计、各类插入删除操作；再深入 LinkedList 的源码，解析它的构造、方法和遍历逻辑；最后对比它与 ArrayList 的差异，助力你在实际开发中做出更优的技术选择。
一、双向链表
双向链表与单向链表相比，多了一个前驱prev，但解决了单向链表很多缺点：单向链表的每个节点==仅存储后继节点地址==，这导致其在实际应用中存在明显==局限==：
==遍历方向单一==：只能从表头（head）向表尾（tail）遍历，无法反向查找。
==删除操作低效==：若要删除指定节点，需先从头遍历找到其前驱节点，时间复杂度为O(n)。
==表尾操作不便==：无法直接获取表尾节点的前驱，若需在表尾插入后修改前驱指针，需重新遍历。
双向链表通过在节点中增加前驱节点地址域，解决了以上问题，so在实际开发中，使用更多的是双向链表
二、双向链表的模拟实现
1.节点类
==val数据，next后继，prev前驱==，双向链表的前驱节点，可以找到前一个节点，为了方便从后往前遍历，我们使用last标记最后一个节点
static class ListNode{
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
2.头插法
先创建一个新节点node，如果链表为空，head和last都指向新节点，当链表不为空时，让新节点的next指向头节点（先绑定后面），然后将头节点的前驱prev赋值为新节点的地址，最后让head指向新的节点
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
3.尾插法
跟头插法一样，创建一个节点，判断链表是否为空，为空就让head和last都指向新节点，当链表不为空时，让最后一个节点的next指向新的节点（先绑定），然后让新节点的前驱指向前一个节点的地址，最后让last指向新节点
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
4.指定位置插入
双向链表可以找到前一个节点，所以可以让==cur==直接走到想要插入的位置，先判断位置是否合法，然后开始插入，先绑定后面让新节点的next指向cur节点的地址，然后让前一个节点的next指向新的节点的地址，在将新节点的前驱改为cur的前驱，cur的前驱改为新节点
public void addIndex(int index, int data) {
//检查index的合法性
check(index);
//特殊位置处理
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
//指定插入
ListNode cur = searchIndex(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//寻找位置
private ListNode searchIndex(int index) {
ListNode cur = head;
while (index!=0){
cur = cur.next;
index--;
}
return cur;
}
//自定义异常
private void check(int index) {
if (index < 0 || index > size()) {
throw new check("index位置不合法" + index);
}
}
5.删除值为key的节点
先遍历，找到所要删除的那个节点，当cur走到要删除的节点时，常规操作：==cur.next.prev = cur.prev; cur.prev.next = cur.next==;但还有其他情况：比如要删除的是头节点或者尾节点，只要一个节点的情况，具体操作看下面的代码详解
public void remove(int key) {
ListNode cur = head;
while (cur != null){
if (cur.val == key){
//开始删除
if(cur == head){
//删除的时头节点
head = head.next;
//如果只有一个节点，head为空,它的前驱就会空指针异常，所以判断一下
if(head!=null) {
head.prev = null;
}
}else {
//不是头节点
if(cur == last){
//删除的是尾节点
cur.prev.next = cur.next;
last = last.prev;
}else {
//正常情况：中间节点
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
return;
}
cur = cur.next;
}
}
6.删除所有值为key的节点
只要将上面的代码中return去掉，就能删除所有值为key的节点，==删完一个后不返回，继续遍历==，直到全部删除
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null){
if (cur.val == key){
//开始删除
if(cur == head){
//删除的时头节点
head = head.next;
//如果只有一个节点，head为空,它的前驱就会空指针异常，所以判断一下
if(head!=null) {
head.prev = null;
}
}else {
//不是头节点
if(cur == last){
//删除的是尾节点
cur.prev.next = cur.next;
last = last.prev;
}else {
//正常情况：中间节点
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
}
cur = cur.next;
}
}
7.清空链表
【方法一：】直接将头和尾置空
public void clear() {
head = last = null;
}
【方法二：】将一个一个的节点置空
public void clear() {
ListNode cur = head;
while (cur != null){
ListNode curN = cur.next;
cur.prev = null;
cur.next = null;
cur =curN;
}
head = null;
last = null;
}
二、LinkedList
1.LinkdeList的概念
LinkedList使用双向链表结构，实现了List接口。在任意位置插入和删除元素时效率较高，时间复杂度为O（1）。
2.构造方法
方法说明表格
| 方法签名 | 描述 |
|---|---|
LinkedList() |
无参构造方法，创建一个空链表。 |
public LinkedList(Collection<? extends E> c) |
使用其他集合容器中的元素构造List |
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new ArrayList<>();
list.add(1);//默认尾插
list.add(11);
list.add(12);
list.add(13);
System.out.println(list);
}
3.LinkedList常用方法
| 方法 | 解释 |
|---|---|
boolean add(E e) |
在列表尾部插入元素e |
void add(int index, E element) |
将元素e插入到指定index位置 |
boolean addAll(Collection<? extends E> c) |
将集合c中所有元素插入到列表尾部 |
E remove(int index) |
删除并返回index位置的元素 |
boolean remove(Object o) |
删除列表中首次遇到的指定对象o |
E get(int index) |
获取index位置的元素 |
E set(int index, E element) |
将index位置的元素替换为element并返回旧值 |
void clear() |
清空列表中的所有元素 |
boolean contains(Object o) |
判断列表中是否包含对象o |
int indexOf(Object o) |
返回第一个o对象的下标，未找到返回-1 |
int lastIndexOf(Object o) |
返回最后一个o对象的下标，未找到返回-1 |
List<E> subList(int fromIndex, int toIndex) |
截取从fromIndex到toIndex的子列表 |
4.LinkedList遍历
4.1 直接打印
System.out.println(list);
4.2 for-each遍历
for(Integer x : list){
System.out.println(x+" ");
}
4.3 迭代器遍历
//迭代器遍历
Iterator<Integer> it = list.iterator();
while (it.hasNext()){
System.out.println(it.next()+" ");
}
//迭代器遍历：专门遍历List
ListIterator<Integer> listIterator = list.listIterator();//可以给参数，从index开始打印
while (listIterator.hasNext()){
System.out.println(listIterator.next()+" ");
}
//反向迭代器
ListIterator<Integer> listIterator1 = list.listIterator();//可以给参数，从index开始打印
while (listIterator.hasPrevious()){
System.out.println(listIterator.next()+" ");
}
5.ArrayList和LinkList的区别
| 不同点 | ==ArrayList== | ==LinkedList== |
|---|---|---|
| 存储空间 | 物理上连续 | 逻辑上连续，物理上不连续 |
| 随机访问 | 支持O(1)时间复杂度 | 不支持，需遍历O(N)时间复杂度 |
| 头插操作 | 需搬移元素，效率低O(N) | 修改引用指向，效率高O(1) |
| 插入扩容 | 空间不足时需扩容 | 无容量概念，动态增加节点 |
| 应用场景 | 元素高效存储+频繁随机访问 | 频繁在任意位置插入/删除 |
三、总结
本文围绕==双向链表==和==LinkedList== 展开了系统讲解。
- 双向链表凭借“每个节点保存前驱和后继引用”的结构，在插入、删除操作上有着O(1)的时间复杂度优势。
- LinkedList 作为双向链表的Java实现，不仅提供了如 addFirst 、 removeLast 等丰富方法，支持迭代器、增强for等多种遍历方式，还能充当队列、栈使用。和 ArrayList 相比， LinkedList 适合频繁进行插入删除的场景， ArrayList 则更适合元素存储和随机访问的场景。掌握这些知识，能让你在面对不同业务场景时，合理选择数据结构，写出高效且易维护的代码。
- 点赞
- 收藏
- 关注作者
评论（0）