当前位置： 首页 > article >正文

【Java---数据结构】链表 LinkedList

article 2025/3/9 22:25:23

1. 链表的概念

链表用于存储一系列元素，由一系列节点组成，每个节点包含两部分：数据域和指针域。

数据域：用于存储数据元素

指针域：用于指向下一个节点的地址，通过指针将各个节点连接在一起，形成一个链式结构。

注意：

链表在逻辑上是连续的，空间上并不是连续的

根据指针的连接方式，链表可以分为单向链表和双向链表

注意：

单向链表和双向链表的结点存在差异

2. 单向链表

单向链表是链表的一种，它的每个节点除了存储数据外，还包含一个指针指向下一个节点地址

2.1 单向列表的节点

每个节点只有一个指针，指向下一个节点。

最后一个节点的指针指向null，表示链表结束。

代码实现：

class ListNode{
    int val;
     ListNode next;//next指向新的节点

    public ListNode(int val) {
        this.val = val;
    }

}

注意： 

结点一般都是从堆上申请出来，每次在堆上申请的空间，按照一种策略来进行分配，多次申请出来的空间，可能连续，也可能不连续

2.2 链表的创建

1. 创建一个节点

2.创建第二个节点，让第一个节点的指针域存放第一个节点的地址，以此类推，可以创建出链表

代码实现：

 public void createList(){
        //创建节点
        ListNode listNode = new ListNode(15);
        ListNode listNode1 = new ListNode(56);
        ListNode listNode2 = new ListNode(45);
        ListNode listNode3 = new ListNode(88);

        //节点连接
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        this.head = listNode;
    }

注意：

不要忘记标注链表的头节点，当输出头节点时，会输出整个链表的数据

2.3 链表的种类

2.4 链表的基本操作

2.4.1 增加

（1）头插法

主要操作：

  1. 将新创建的节点的指针域更改为头节点的地址 
  2. 将头节点的位置进行改变
public void addFirst(int data){
        //代码不能交换
        //必须先绑定信息
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }

 注意：代码的先后顺序不能颠倒，否则获取不到listNode.next的位置 

（2）尾插法

主要操作：

  1. 将最后一个节点的指针域指向新节点的地址 

特殊情况：

  1. 链表内没有一个节点，那么让新节点成为头节点

代码实现：

    public void addLast(int data){
        ListNode listNode  = new ListNode(data);

        ListNode cur = head;
        if(cur==null){
            head = listNode;
            return ;
        }
        while(cur.next!=null){//关注next的指向,找到最后一个节点
            cur = cur.next;
        }
        cur.next = listNode;

    }
（3）固定位置插入

主要操作：

  1. 找到要插入位置的前一个位置（cur）
  2. 让新节点的指针域指向要插入位置的旧节点
  3. 让cur指针域指向新节点的地址

注意：第二步和第三步不能交换位置，如果交换，会导致cur的位置发生改变，导致无法找到要插入位置的地址

代码实现：

public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("位置有问题");
            return;
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return ;
        }
        ListNode cur = head;
        int count = 0;
        ListNode listNode = new ListNode(data);
        while(count<index-1){
            cur =cur.next;
            count++;
        }
        //不能互换位置
        listNode.next = cur.next;
        cur.next = listNode;
    }

注意：

不要忘记检查，插入的位置是否合法

 如果插入的位置为0；那么意味着头插法，位置为元素的长度，那么就是尾插法

2.4.2 删除

（1）删除第一个出现的元素

主要步骤：

  1. 找到你要删除元素的前一个节点
  2. 找到你要删除的节点
  3. 进行删除操作

代码实现：

    public void remove(int data){
        if(head ==null){
            return;
        }
        if(head.val ==data){
            head = head.next;
            return;
        }
        //1.找到你要删除的前一个节点
        ListNode cur = head;
        int count = 0;
        while(cur.next!=null){
            if(cur.next.val == data){
                break;
            }
            count++;
            cur= cur.next;
        }
        //找到要删除的节点
        ListNode del = head;
        int delindex = 0;
        while (del!=null){
            if(del.val ==data){
                break;
            }
            delindex++;
            del = del.next;
        }
        //删除操作
        cur.next = del.next;
    }

 注意：删除的具体操作就是：删除节点的前一个节点的指向发生改变，指向删除元素的指向

（2）删除出现的所有元素

主要步骤：

  1. 初始化两个节点，cur节点进行判断值是否相同，previous是cur节点的前一个结点，方便进行删除操作
  2. 进行遍历链表，找到相同的值，则进行删除操作，反之将两个节点都向后移动一位

代码实现：

        if(head ==null){
            return;
        }
        ListNode cur = head.next;
        ListNode previous = head;
        while(cur!=null){
            if(cur.val==data){
                previous.next = cur.next;
                cur = cur.next;
            }else{
                previous = cur;//注意，小心写成 previous.next = cur;//错误
                cur = cur.next;
            }
        }
        if(head.val ==data){
            head = head.next;
        }
    }

注意：不要忘记对头节点进行判断

2.4.3 查看

（1）查看链表是否存在元素
    public boolean contains(int value){
        ListNode cur = head;
        while(cur!=null){
            if(cur.val==value){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

 主要步骤：

采用遍历的形式，如果找到元素，则返回true，反之，返回false

2.4.4 获取链表长度

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

 2.4.5 清空链表

void clear(){
        ListNode cur  = head;
        ListNode curNext ;
        while(cur!=null){
            curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
}

注意： 遍历链表逐个释放节点的引用，让每个节点不再被引用

3. 快慢指针

思想：通过使用两个速度不同的指针（快指针和慢指针）来遍历数据结构，从而实现特定的功能

注意：本质就是利用指针的移动速度差异来解决问题

常见的解决情况：

（1）找出中间的节点

    ListNode findListNode(Text_2 list){
        ListNode mid = head;
        if(head == null){
            return null;
        }
        if(head.next ==null){
            return head;
        }
        int count = size(list);
        int midCount = count/2;
        while (midCount>0){
            mid = mid.next;
            midCount--;
        }
        return mid;
    }

这是解决这种问题，我们第一个想到的方法，需要遍历两次链表，获取长度和中间节点 ，复杂度高，下面是我们引用了快慢指针：

    ListNode findListNode1(){
   
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){//不能交换
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

核心思想：使用快慢双指针，快的是慢的二倍；那么快的到了，慢的一定就在中间

（2）找出倒数第k个节点

    ListNode findListNode(int k){

        if(head ==null){
            return null;
        }
        if(k<=0||k>size()){
            System.out.println("k取值不对");
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        int count = k-1;

        while (count>0){
            fast = fast.next;
            count--;
        }
        while(fast!=null&&fast.next!=null){
            fast =fast.next;
            slow =slow.next;
        }
        return slow;
    }

核心思想：快的比慢的先走了k-1个，然后每次都移动一个， 那么快的到了，满的就是倒数第k个.

先走k-1个，因为下标从0开始

4. 双向链表

双向链表是链表的一种，它的每个节点除了存储数据外，还包含两个指针：一个指向前一个节点，另一个指向下一个节点

4.1 双向列表的节点

注意：

由于有前驱指针，删除和插入操作更高效。

每个节点需要额外存储一个指针，因此比单向链表占用更多内存。

可以从头节点向后遍历，也可以从尾节点向前遍历。

代码实现：

class ListNode{
    int val;
    ListNode prev;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

4.2 LinkedList

在 Java 中，LinkedList是java.util 包中的一个类，LinkedList的底层使用了双向链表

4.3 LinkedList的使用

4.3.1 LinkedList的构造

（1）无参构造
        //调用无参构造
        List<Integer> list =new LinkedList<>();
（2）利用Collection构建
        List<Integer> list1 =new LinkedList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        System.out.println(list1);

        List<Integer> list2 = new LinkedList<>(list1);
        list2.add(2);
        System.out.println(list2);

 注意：会继承传入实例对象的所有元素，并且元素的顺序也会保持一致

4.3.2  LinkedList的常用API

boolean add(E e)

尾插

void add(int index, E element)

在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)

截取顺序表的一部分

（1）增加
public class Add {
    public static void main(String[] args) {
        //尾插法
        LinkedList<Integer> list =new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list);

        //插入固定位置
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(0,1);
        list1.add(0,6);
        list1.add(1,9);
        System.out.println(list1);

        //尾插所有元素
        Integer[] array = {9,99,999};
        list.addAll(Arrays.asList(array));
        System.out.println(list);
    }
}
（2）删除
public class Remove {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        //删除下标的数
        list.remove(2);
        System.out.println(list);

        //删除第一个出现的数
        list.remove(new Integer(2));
        System.out.println(list);

    }
}
（3）修改
public class Set {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        list.set(1,999);
        System.out.println(list);
    }
}
（4）获取
public class Get {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        int x = list.get(2);
        System.out.println(x);
    }
}
（5）清空
public class Clear {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        list.clear();
        System.out.println(list);
    }
}
（6）查找
public class Contains {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
//        判断元素是否在表中
        Boolean x = list.contains(2);
        System.out.println(x);
//      返回第一个元素所在的下标
        int a = list.indexOf(2);
        System.out.println(a);
//      返回最后一个元素所在的下标
        int b = list.lastIndexOf(2);
        System.out.println(b);

    }
}
（7）截取
public class Sublist {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(6);
        list.add(9);

//        LinkedList<Integer> list1 = new LinkedList<>(list.subList(1,4));//创建新的对象，进行操作，不会影响原来列表的数据
        //subList返回值是List类型
        List<Integer> list1 = list.subList(1,4);
        list1.add(999);
        list1.add(888);
        list1.set(0,111);

        System.out.println(list1);

        System.out.println(list);
    }
}

 4.3.3 LinkedList的遍历

（1）for循环遍历
        //1.
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
（2）for-each遍历
        //2
        for (int x : list){
            System.out.print(x+" ");
        }
（3）使用迭代器

正向遍历

        //3
        Iterator<Integer> iterator = list.listIterator();//传数据
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();

反向遍历

        //4
        ListIterator<Integer> listIterator = list.listIterator(list.size());
        while (listIterator.hasPrevious()){
            System.out.print(listIterator.previous()+" ");
        }
        System.out.println();

注意：

（从前往后）while循环中的判断条件表示：是否存在下一个元素，如果存在，则获取迭代器的下一个元素并输出，因为 next 方法，所以在每次调用后进行移动1位

5. ArrayList和LinkedList的区别

差别

ArrayList

LinkedList

底层实现

基于动态数组实现

基于双向链表实现

访问效率

随机访问效率高

随机访问效率低

插入和删除效率

尾部插入和删除效率高

中间或头部插入和删除效率低

任意位置插入和删除效率高

内存占用

内存占用较少，因为只需要存储数据和数组容量。

可能存在内存浪费，因为数组会预留一定的容量

内存占用较多，因为每个节点需要存储数据以及前后指针。

总结：

ArrayList  适合频繁访问元素的场景，例如随机读取数据，适合元素数量相对固定的场景。

LinkedList 适合频繁插入和删除的场景，例如实现栈、队列，适合元素数量动态变化的场景。


http://www.kler.cn/a/571534.html

相关文章：

  • CSS中各个元素的显示模式(块级/行内元素分类)
  • mysql唯一索引下插入数据死锁过程分析
  • 机器学习--特征选择
  • 每日OJ_牛客_游游的字母串_枚举_C++_Java
  • 高效卸载神器：深度体验分享
  • 探秘基带算法：从原理到5G时代的通信变革【三】Turbo 编解码
  • 【OpenCV C++】以时间命名存图，自动检查存储目录，若不存在自动创建， 按下空格、回车、Q、S自动存图
  • 爬虫逆向实战小记——解决webpack实记
  • 【借助 DeepSeek 之力：自动化 Web 渗透测试脚本编写与实战】
  • 大模型学习笔记------Llama 3模型架构简介
  • Python--面向对象高级（上）
  • Pycharm（四）：集合的操作
  • leetcode242 哈希表
  • 设计模式说明
  • 10款常用的FTP传输客户端工具：选择与使用指南
  • Redis 实现延迟队列的方案
  • Dijkstra最短路算法详解与蓝桥杯/ACM真题实战
  • 复古半色调褶皱划痕y2k照片效果ps特效滤镜样机 Folded Retrofuturistic Comics Risograph Effect
  • 江协科技/江科大-51单片机入门教程——P[2-2] LED闪烁P[2-3] LED流水灯
  • 【零基础到精通Java合集】第二十集：Java内存模型-堆、栈、方法区