LinkedList深入讲解

2401_88691476

926人浏览 · 2026-02-25 15:40:31

2401_88691476 · 2026-02-25 15:40:31 发布

文章目录

一、LinkedList的模拟实现
二、LinkedList详解

作者:当战神遇到编程
文章专栏:数据结构
欢迎大家点赞👍评论📝收藏⭐文章

在这里插入图片描述

在这里插入图片描述
无头双向链表的基础结构

例子

一、LinkedList的模拟实现

1.1 IList接口

public interface IList<T> {

    // 遍历：打印链表所有元素
    void display();
    
    // 统计：获取链表长度
    int size();

    // 头插法：在链表头部插入数据
    void addFirst(T data) ;

    // 尾插法：在链表尾部插入数据
    void addLast(T data) ;

    // 任意位置插入：第一个节点为0号下标
    void add(int index, T data) ;

    // 查找：判断关键字key是否存在
    boolean contains(T key) ;

    // 删除：移除第一次出现的key节点
    boolean remove(T key);

    // 删除：移除所有值为key的节点
    boolean removeAllKey(T key) ;

    // 清空：释放链表所有节点
    void clear() ;
}

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 display() {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void addFirst(T data) {

    }

    @Override
    public void addLast(T data) {

    }

    @Override
    public void add(int index, T data) {

    }

    @Override
    public boolean contains(T key) {
        return false;
    }

    @Override
    public boolean remove(T key) {
        return false;
    }
    
    @Override
    public boolean removeAllKey(T key) {

    }

    @Override
    public void clear() {

    }
}

1.3 各方法实现

(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) int size()

public int size() {
        ListNode<T> cur = this.head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
}

(3) 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;
            return;
        }
        //链表不为空
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
}

(4) 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;
            return;
        }
        //链表不为空
        last.next = node;
        node.prev = this.last;
        this.last = node;
}

(5) void add(int index, T data)

在这里插入图片描述

public void add(int index, T data) {
        int len = size();

        if(index < 0 || index > len) {
            throw new IndexOutOfBoundsException("添加元素位置异常");
        }
        //头插
        if(index == 0) {
            addFirst(data);
            return;
        }

        if(index == len) {
            addLast(data);
            return;
        }

        //在中间位置插
        ListNode<T> node = new ListNode<>(data);
        ListNode<T> cur = search(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
}

private ListNode<T> search(int index) {
        ListNode<T> cur = this.head;
        int count = 0;
        while(count < index) {
            cur = cur.next;
            count++;
        }
        return cur;
}

(6) 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;
}

(7) boolean remove(T key)

1.要删除的元素在头节点
(1)有很多节点
在这里插入图片描述
(2)只有一个节点

2.要删除的元素在中间位置

3.要删除的元素在尾节点
在这里插入图片描述

public boolean remove(T key) {
        ListNode<T> cur = this.head;
        while(cur != null) {
            //要删除的是头节点
          if(cur.val.equals(key)) {
              if(cur == this.head) {
                  this.head  = this.head.next;
                  if(this.head == null) {
                      this.last = null;
                  }else {
                      this.head.prev = null;
                  }
              } else {
                  //要删除的是尾节点
                  if (cur == this.last) {
                      this.last = cur.prev;
                      this.last.next = null;
                  }else {
                      cur.prev.next = cur.next;
                      cur.next.prev = cur.prev;
                  }
              }
              return true;
          }
          cur = cur.next;
        }
        return false;
}

(8) boolean removeAllKey(T key)

public boolean removeAllKey(T key) {
        ListNode<T> cur = this.head;
        boolean removed = false;

        while(cur != null) {
            if(cur.val.equals(key)) {
                // 删除头节点
                if(cur == this.head) {
                    this.head = this.head.next;

                    if(this.head == null) {
                        this.last = null;
                    } else {
                        this.head.prev = null;
                    }
                }
                // 删除尾节点
                else if(cur == this.last) {
                    this.last = cur.prev;
                    this.last.next = null;
                }
                // 删除中间节点
                else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                removed = true;
            }
            cur = cur.next;
        }
        return removed;
}

(9) 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),直接修改头尾指针
线程安全	非线程安全	非线程安全

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

项目拆解（二）：模型输出是‘野‘的——三层兜底+重分析，把AI变成可靠零件

前两层都过了，数据入库了，最后一步是上屏。但这里还有坑——模型在"无风险"时会返回什么？真机实测：它返回了[""]，甚至[" "]（带空格的空串）。前端直接渲染，用户看到一个红色的空警告框，吓一跳。?${esc">无，这段代码挺干净</span>'">无，这段代码挺干净</span>'先t.trim()再。只挡不住[" "]（带空格的字符串是真值），必须先清空格再过滤。这是真机踩出来的：第一次只写