代码探险家

这个屌丝很懒，什么也没留下！

热门标签

带你深入探索Java中的LinkedList和链表的奥秘

作者：代码探险家 | 2024-07-14 03:35:21

踩

引言

在 Java 编程语言中，链表是一种基本的数据结构，它提供了一种灵活的方式来存储和管理数据。Java 中的 LinkedList 类是链表实现的一个典型例子，它是 Java 集合框架的一部分。在这篇博客中，我们将深入探讨 LinkedList 和链表的概念、特点以及如何在 Java 中使用它们。

链表的概念

链表是一种线性数据结构，由一系列节点（Node）组成，每个节点包含两个主要元素：数据和下一个节点的地址。链表的节点不必在内存中连续存储，它们可以分散存放，并通过存储在节点内的下一个节点的地址连接起来形成一个序列。

链表的结构

请注意：

链式结构在逻辑上是连续的，但在物理空间上是不一点连续。
节点的数据存储在堆区而不是栈区，这一点与顺序表相同（数组存储在栈区）。
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

单向/双向

单向链表 (Singly Linked List)

单向链表的每个节点包含：

val 域：存储数据元素。
next 域：存储下一个节点的地址。

双向链表 (Doubly Linked List)

双向链表在单向链表的基础上增加了一个指向前一个节点的指针。

因此每个节点包含：

val 域：存储数据元素。
next 域：存储下一个节点的地址。
prev 域：存储上一个节点的地址。

带头/不带头

带头链表（用单向链表来演示）

就是多了个节点用来记录链表头节点的地址。

不带头链表（用单向链表来演示）

跟前面的单向链表一样，因为就是无头单链表

循环/非循环

循环链表（用单向链表来演示）

就是把链表的最后一个节点用来存头节点的地址。

非循环链表（用单向链表来演示）

跟前面的单向链表和无头链表一样，因为就是无头单向链表。

以上情况组合起来共有8种链表结构，不过大家不用担心，我们只需重点掌握两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
无头双向链表：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。

链表的知识是一通百通的，其他情况大家不用担心，学完自然就懂了。

链表的实现

无头单向链表的实现（未使用泛型）

1.跟顺序表一样，我们先创建一个接口类 IList


public interface IList {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    void clear();
    void display();
}

这个接口类也可以不创建，但为了避免漏写功能还是建议创建。

2.创建 MySingleList 类并让它实现IList类中的方法


public class MySingleList implements IList {
    static class ListNode {
        public int val;
        public ListNode next;
 
        public ListNode(int val) {
            this.val = val;
        }
    }
 
    public ListNode head;//用来保存头节点地址
 
//    public void createList() {
//        ListNode listNode1 = new ListNode(1);
//        ListNode listNode2 = new ListNode(2);
//        ListNode listNode3 = new ListNode(3);
//        ListNode listNode4 = new ListNode(4);
//        ListNode listNode5 = new ListNode(5);
//
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
//
//        this.head = listNode1;
//    }
 
    //头插法
    @Override
    public void addFirst(int data) {
        ListNode listNode = new ListNode(data);
//        if (this.head == null) {
//            this.head = listNode;
//            return;
//        }
        listNode.next = this.head;
        this.head = listNode;
    }
    
    //尾插法
    @Override
    public void addLast(int data) {
        ListNode listNode = new ListNode(data);
        ListNode tmp = this.head;
        if (tmp == null) {
            this.head = listNode;
        } else {
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = listNode;
        }
    }
 
    //任意位置插入,第一个数据节点为0号下标
    @Override
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            throw new IndexIllegality("插入元素位置异常:" + index);
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode tmp = searchPrev(index);
        ListNode listNode = new ListNode(data);
        listNode.next = tmp.next;
        tmp.next = listNode;
    }
    
    //查找是否包含关键字key是否在单链表当中
    private ListNode searchPrev(int index) {
        ListNode tmp = this.head;
        while (index - 1 != 0) {
            tmp = tmp.next;
            --index;
        }
        return tmp;
    }
    
    //查找是否包含关键字key是否在单链表当中
    @Override
    public boolean contains(int key) {
        ListNode tmp = this.head;
        while (tmp != null) {
            if (tmp.val == key) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    
    //删除第一次出现关键字为key的节点
    @Override
    public void remove(int key) {
//        if (this.head == null) {
//            System.out.println("当前链表无数据，无法进行删除！");
//            return;
//        }
        if (isEmpty()) {
            return;
        }
 
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
 
        ListNode tmp = findPrev(key);
        if (tmp == null) {
            System.out.println("要删除的数不存在！");
            return;
        }
        ListNode del = tmp.next;
        tmp.next = del.next;
    }
    
    //判断链表是否为空，仅做内部支持
    private boolean isEmpty() {
        if (this.head == null) {
            System.out.println("当前链表无数据，无法进行删除！");
            return true;
        }
        return false;
    }
    
    //根据key来查找前驱节点的地址，仅做内部支持
    private ListNode findPrev(int key) {
        ListNode tmp = this.head;
        while (tmp.next != null) {
            if (tmp.next.val == key) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
    
    //删除所有值为key的节点
    @Override
    public void removeAllKey(int key) {
        if (isEmpty()) {
            return;
        }
        ListNode prev = this.head;
        ListNode tmp = this.head.next;
        while (tmp != null) {
            if (tmp.val == key) {
                prev.next = tmp.next;
            } else {
                prev = tmp;
            }
            tmp = tmp.next;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }
    
    //获得单链表的长度
    @Override
    public int size() {
        int count = 0;
        ListNode tmp = this.head;
        while (tmp != null) {
            ++count;
            tmp = tmp.next;
        }
        return count;
    }
    
    //销毁链表
    @Override
    public void clear() {
        ListNode tmp = this.head;
        this.head = null;
        while (tmp != null) {
            ListNode cur = tmp.next;
            tmp.next = null;
            tmp = cur;
        }
    }
 
    //打印全部链表，仅做测试
    @Override
    public void display() {
        ListNode tmp = this.head;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }
    
    //从指定的节点开始打印链表，仅做测试
    public void display(ListNode newHead) {
        ListNode tmp = newHead;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }
    
    //逆置链表，仅做测试
    public ListNode reverseList() {
        //为空
        if (this.head == null) {
            return null;
        }
        //只有一个节点
        if (this.head.next == null) {
            return this.head;
        }
        ListNode tmp = this.head.next;
        this.head.next = null;
        while (tmp != null) {
            ListNode tmpNext = tmp.next;
            tmp.next = this.head;
            this.head = tmp;
            tmp =tmpNext;
        }
        return this.head;
    }
}

抛异常部分请自行完成，或用if语句代替。

LinkedList 的模拟实现（未使用泛型）

创建 MyLinkedList 类并让它实现 IList 类中的方法

MyLinkedList 同样接入 IList 接口就行，不用再写一个接口类。LinkedList 实际上是无头双向链表，因此我们实现这个无头双向链表即可。


public class MyLinkedList implements IList {
    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;//用来保存尾节点地址
    
    //头插法
    @Override
    public void addFirst(int data) {
        ListNode tmp = new ListNode(data);
        if (this.head == null) {
            this.head = tmp;
            this.last = tmp;
        } else {
            tmp.next = this.head;
            this.head.prev = tmp;
            this.head = tmp;
        }
    }
    
    //尾插法
    @Override
    public void addLast(int data) {
        ListNode tmp = new ListNode(data);
        if (this.last == null) {
            this.head = tmp;
            this.last = tmp;
        } else {
            last.next = tmp;
            tmp.prev = this.last;
            this.last = tmp;
        }
    }
    
    //任意位置插入,第一个数据节点为0号下标
    @Override
    public void addIndex(int index, int data) throws IndexIllegality {
        int len = size();
        if (index < 0 || index > len) {
            throw new IndexIllegality("插入元素位置异常:" + index);
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == len) {
            addLast(data);
            return;
        }
        ListNode tmp = findIndex(index);
        ListNode listNode = new ListNode(data);
        listNode.next = tmp;
        tmp.prev.next = listNode;
        listNode.prev = tmp.prev;
        tmp.prev = listNode;
    }
    
    //查找指定下标（实际上是没有下标的）的节点地址，仅做内部支持
    private ListNode findIndex(int index) {
        ListNode tmp = this.head;
        while (index != 0) {
            tmp = tmp.next;
            --index;
        }
        return tmp;
    }
    
    //查找是否包含关键字key是否在单链表当中
    @Override
    public boolean contains(int key) {
        ListNode tmp = this.head;
        while (tmp != null) {
            if (tmp.val == key) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    
    //删除第一次出现关键字为key的节点
    @Override
    public void remove(int key) {
        if (isEmpty()) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            if (this.head != null) {
                this.head.prev = null;
            }
            return;
        }
        if (this.last.val == key) {
            this.last = this.last.prev;
            if (this.last != null) {
                this.last.next = null;
            }
            return;
        }
        ListNode tmp = findKey(key);
        if (tmp == null) {
            System.out.println("要删除的数不存在！");
            return;
        }
        tmp.prev.next = tmp.next;
        tmp.next.prev = tmp.prev;
    }
    
    //根据key查找节点地址，仅做内部支持
    private ListNode findKey(int key) {
        ListNode tmp = this.head;
        while (tmp != null) {
            if (tmp.val == key) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
 
    //判断链表是否为空，仅做内部支持
    private boolean isEmpty() {
        if (this.head == null) {
            System.out.println("当前链表无数据，无法进行删除！");
            return true;
        }
        return false;
    }
    
    //删除所有值为key的节点
    @Override
    public void removeAllKey(int key) {
        ListNode tmp = this.head;
        while (tmp != null) {
            if (tmp.val == key) {
                if (tmp == this.head) {
                    this.head = this.head.next;
                    if (this.head == null) {
                        this.last = null;
                    } else {
                        this.head.prev = null;
                    }
                } else {
                    tmp.prev.next = tmp.next;
                    if (tmp.next == null) {
                        this.last = this.last.prev;
                    } else {
                        tmp.next.prev = tmp.prev;
                    }
                }
            }
            tmp = tmp.next;
        }
    }
    
    //获得单链表的长度
    @Override
    public int size() {
        ListNode tmp = this.head;
        int count = 0;
        while (tmp != null) {
            ++count;
            tmp = tmp.next;
        }
        return count;
    }
    
    //销毁链表
    @Override
    public void clear() {
        ListNode tmp = this.head;
        this.head = null;
        this.last = null;
        while (tmp != null) {
            ListNode cur = tmp.next;
            tmp.next = null;
            tmp.prev = null;
            tmp = cur;
        }
    }
    
    //打印全部链表，仅做测试
    @Override
    public void display() {
        ListNode tmp = this.head;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }
}

跟上面一样，抛异常部分请自行完成，或用if语句代替。

LinkedList 是什么

LinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList 也实现了 List 接口，具体如下：

请注意：

LinkedList 实现了 List 接口。
LinkedList 的底层使用了双向链表。
LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问。
LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)。
LinkedList 比较适合任意位置插入的场景。

LinkedList的使用

LinkedList的构造

方法	解释
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	使用其他集合容器中元素构造 List


public static void main(String[] args) {
    List<Integer> list1 = new LinkedList<>();//通过接口new
    LinkedList<String> list2 = new LinkedList<>();//直接new
    List<String> list3 = new java.util.ArrayList<>();//使用其他集合容器中元素构造List
 
    list2.add("Java");
    
    //使用ArrayList构造LinkedList
    List<String> list4 = new LinkedList<>(list3);
    //使用LinkedList构造LinkedList
    List<String> list5 = new LinkedList<>(list2);
}

个人推荐使用第一种和第二种方法。

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 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分 list

LinkedList 的遍历

代码演示如下：


public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();//通过List接口来new一个LinkedList
        list.add(1);
        list.add(2);
        list.add(3);
 
        //使用for循环
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
 
        //使用for-each（增强for循环）
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();
 
        //使用迭代器
        Iterator<Integer> it = list.listIterator();//迭代器
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
        
        //使用反向迭代器---反向遍历
        ListIterator<Integer> rit = list.listIterator(list.size());
        while (rit.hasPrevious()){
            System.out.print(rit.previous() +" ");
        }
    }

运行结果如下：

ArrayList 和 LinkedList 的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

总结

LinkedList 是 Java 中实现链表概念的一个强大工具。它提供了一系列方法来高效地进行数据的插入、删除和访问操作。了解 LinkedList 的工作原理和如何在 Java 中使用它对于开发高效的程序至关重要。无论是在学术研究还是实际开发中，LinkedList 都是一个不可或缺的组件。

以上，就是的本次要带大家深度剖析的Java中的LinkedList和链表的全部内容，感谢大家愿意花时间阅读本文！如有错误，建议，或问题均可在评论区指出！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/822982

带你深入探索Java中的LinkedList和链表的奥秘

目录

引言

链表的概念

链表的结构

单向/双向

单向链表 (Singly Linked List)

双向链表 (Doubly Linked List)

带头/不带头

带头链表（用单向链表来演示）

不带头链表（用单向链表来演示）

循环/非循环

循环链表（用单向链表来演示）

非循环链表（用单向链表来演示）

以上情况组合起来共有8种链表结构，不过大家不用担心，我们只需重点掌握两种：

链表的实现

无头单向链表的实现（未使用泛型）

1.跟顺序表一样，我们先创建一个接口类 IList

2.创建 MySingleList 类并让它实现IList类中的方法

LinkedList 的模拟实现（未使用泛型）

创建 MyLinkedList 类并让它实现 IList 类中的方法

LinkedList 是什么

LinkedList的使用

LinkedList的构造

LinkedList 的其他常用方法介绍

LinkedList 的遍历

ArrayList 和 LinkedList 的区别

总结