从0到1手撕双向链表，再到LinkedList源码拆解，这篇数据结构干货让你直接逆袭成大佬
🎁个人主页：User_芊芊君子
🎉欢迎大家点赞👍评论📝收藏⭐文章
🔍系列专栏：Java.数据结构
【前言】
在Java开发中， LinkedList 是集合框架里的重要成员，其底层基于双向链表实现。对于开发者来说，搞清楚双向链表的工作机制，能让我们更精准地运用 LinkedList ，还能提升对数据结构选型的把控力。本文先带你吃透双向链表的模拟实现，涵盖节点设计、各类插入删除操作；再深入 LinkedList 的源码，解析它的构造、方法和遍历逻辑；最后对比它与 ArrayList 的差异，助力你在实际开发中做出更优的技术选择。
文章目录：
一、双向链表
双向链表与单向链表相比，多了一个前驱prev，但解决了单向链表很多缺点：单向链表的每个节点仅存储后继节点地址，这导致其在实际应用中存在明显局限：
遍历方向单一：只能从表头（head）向表尾（tail）遍历，无法反向查找。删除操作低效：若要删除指定节点，需先从头遍历找到其前驱节点，时间复杂度为O(n)。表尾操作不便：无法直接获取表尾节点的前驱，若需在表尾插入后修改前驱指针，需重新遍历。
双向链表通过在节点中增加前驱节点地址域，解决了以上问题，so在实际开发中，使用更多的是双向链表
二、双向链表的模拟实现
1.节点类
val数据，next后继，prev前驱，双向链表的前驱节点，可以找到前一个节点，为了方便从后往前遍历，我们使用last标记最后一个节点
staticclassListNode{publicint val;publicListNode next;publicListNode prev;publicListNode(int val){this.val = val;}}publicListNode head;publicListNode last;2.头插法
先创建一个新节点node，如果链表为空，head和last都指向新节点，当链表不为空时，让新节点的next指向头节点（先绑定后面），然后将头节点的前驱prev赋值为新节点的地址，最后让head指向新的节点
publicvoidaddFirst(int data){ListNode node =newListNode(data);if(head ==null){ head = node; last = node;}else{ node.next = head; head.prev = node; head = node;}}3.尾插法
跟头插法一样，创建一个节点，判断链表是否为空，为空就让head和last都指向新节点，当链表不为空时，让最后一个节点的next指向新的节点（先绑定），然后让新节点的前驱指向前一个节点的地址，最后让last指向新节点
publicvoidaddLast(int data){ListNode node =newListNode(data);if(head ==null){ head = node; last = node;}else{ last.next = node; node.prev = last; last = node;}}4.指定位置插入
双向链表可以找到前一个节点，所以可以让cur直接走到想要插入的位置，先判断位置是否合法，然后开始插入，先绑定后面让新节点的next指向cur节点的地址，然后让前一个节点的next指向新的节点的地址，在将新节点的前驱改为cur的前驱，cur的前驱改为新节点
publicvoidaddIndex(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 =newListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node;}//寻找位置privateListNodesearchIndex(int index){ListNode cur = head;while(index!=0){ cur = cur.next; index--;}return cur;}//自定义异常privatevoidcheck(int index){if(index <0|| index >size()){thrownewcheck("index位置不合法"+ index);}}5.删除值为key的节点
先遍历，找到所要删除的那个节点，当cur走到要删除的节点时，常规操作：cur.next.prev = cur.prev; cur.prev.next = cur.next;但还有其他情况：比如要删除的是头节点或者尾节点，只要一个节点的情况，具体操作看下面的代码详解
publicvoidremove(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的节点，删完一个后不返回，继续遍历，直到全部删除
publicvoidremoveAllKey(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.清空链表
【方法一：】直接将头和尾置空
publicvoidclear(){ head = last =null;}【方法二：】将一个一个的节点置空
publicvoidclear(){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 |
publicstaticvoidmain(String[] args){LinkedList<Integer> list =newLinkedList<>();List<Integer> list1 =newLinkedList<>();List<Integer> list2 =newArrayList<>(); 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()+" ");}//迭代器遍历：专门遍历ListListIterator<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 则更适合元素存储和随机访问的场景。掌握这些知识，能让你在面对不同业务场景时，合理选择数据结构，写出高效且易维护的代码。
