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

数据结构(Java版)第九期：LinkedList与链表

article 2025/1/16 15:55:25

专栏：数据结构(Java版)

个人主页：手握风云

目录

一、LinkedList的模拟实现

1.1. 头插法

1.2. 尾插法

1.3. 插入中间节点

1.4. 删除某个节点

1.5. 删除所有为key的元素

二、LinkedList的使用

2.1. 什么是LinkedList

2.2. LinkedList的使⽤

三、ArrayList和LinkedList的区别

一、LinkedList的模拟实现

        在前几期当中，我们实现的都是单向链表，这次我们要实现的是双向链表。双向链表每个节点包含三个域，分别是val，储存数据；prev储存上一个节点的地址；next，储存下一个节点的地址。（如下图所示）

        对于双向链表的实现，我们新建一个MyLinkedList类，新建一个接口IList，在类里面重写IList里面的方法。

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode head;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//链表的头
    public ListNode last;//链表的尾

    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

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

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

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

    @Override
    public void display() {

    }

    @Override
    public void clear() {

    }
}

public interface IList {
    //头插法
    public void addFirst(int data);

    //尾插法
    public void addLast(int data);

    //任意位置插⼊第⼀个数据节点为0号下标
    public void addIndex(int index,int data);

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key);

    //删除第⼀次出现关键字为key的节点
    public void remove(int key);

    //删除所有值为key的节点
    public void removeAllKey(int key);

    //得到单链表的⻓度
    public int size();

    public void display();

    public void clear();
}

1.1. 头插法

        对于实现尾插的方法其实很简单，把新的节点的next存储下一个节点的地址，同时旧的头节点的prev也要存储新的头节点的地址。

@Override
    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;
        }
    }

 @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }
public class Main {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(50);
        myLinkedList.addFirst(40);
        myLinkedList.addFirst(30);
        myLinkedList.addFirst(20);
        myLinkedList.addFirst(10);
        myLinkedList.addFirst(5);
        myLinkedList.display();
    }
}

    我们顺带也可以完成对链表长度和是否含有某个元素的实现

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

public class Main {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(20);
        myLinkedList.addLast(30);
        myLinkedList.addLast(40);
        myLinkedList.addLast(50);
        myLinkedList.addLast(60);
        System.out.println(myLinkedList.size());

    }
}
@Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

1.2. 尾插法

      尾插法与头插法极其类似，这里不再过多叙述。

@Override
    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;
        }
    }
public class Main {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(20);
        myLinkedList.addLast(30);
        myLinkedList.addLast(40);
        myLinkedList.addLast(50);
        myLinkedList.addLast(60);
        myLinkedList.display();
    }
}

1.3. 插入中间节点

 

       如图所示，我们需要用到4个引用，大致过程可以通过4行代码来实现。先绑定后面，要注意修改每一个引用的时候，不能因为修改了前面而影响了后面。

node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
@Override
    public void addIndex(int index, int data) {
        int len = size();
        if(index<0 || index>len){
            throw new RuntimeException("双向链表位置不合法:"+index);
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == len){
            addLast(data);
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndex(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    private ListNode findIndex(int index){
        ListNode cur = head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

1.4. 删除某个节点

    如果说，我们删除的只是中间的某个节点，我们只需要两行代码就能实现。

cur.prev.next = cur.next;
cur.next.prev = cur.prev;

       但是我们要删除的是头节点或者尾结点呢？我们可以先让head向前走一步，再把head.prev置为空，同理last节点也可以。

@Override
    public void remove(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                //删除头节点
                if(cur == head){
                    head = head.next;
                    head.prev = null;
                }else{
                    //删除尾结点
                    if(cur == last){
                        last = last.prev;
                        last.next = null;
                    }else{
                        //删除中间节点
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }
    }

        这么看我们的代码好像没问题，但我们需要考虑一个问题，如果说链表只有一个节点呢？就会抛出下图这样一个异常，我们只需要把last也手动置为空。

完整代码：

@Override
    public void remove(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                //删除头节点
                if(cur == head){
                    head = head.next;
                    if(head == null){
                        last = null;
                        return;
                    }
                    head.prev = null;
                }else{
                    //删除尾结点
                    if(cur == last){
                        last = last.prev;
                        last.next = null;
                    }else{
                        //删除中间节点
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }
    }

1.5. 删除所有为key的元素

        我们只需要对上一个方法进行一点改动就可以实现。我们让cur只遍历一遍链表，每次cur走完if语句之后直接去指向下一个节点。

@Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                //删除头节点
                if(cur == head){
                    head = head.next;
                    if(head == null){
                        last = null;
                        return;
                    }
                    head.prev = null;
                }else{
                    //删除尾结点
                    if(cur == last){
                        last = last.prev;
                        last.next = null;
                    }else{
                        //删除中间节点
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

二、LinkedList的使用

2.1. 什么是LinkedList

     从上面的图中可以看到LinkedList实现了众多的接口来帮助我们实现各种各样的功能，这里我们主要看List的接口。我们看一下LinkedList里面的源码

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.2. LinkedList的使⽤

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.addFirst(10);
        linkedList.addLast(20);
        System.out.println(linkedList);
    }
}

       我们通过LinkedList创建对象的时候，就可以直接调用以上方法。我们看一下addFirst和addLast的源码。

    public void addFirst(E e) {
        linkFirst(e);
    }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

    我们可以看到，代码的思路与我们上面自己实现的基本一致。我们同样可以初始化一个ArrayList。下面是一些常用方法：

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);//表示尾插
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        list1.add(6);
        list1.add(3,100);//在下标为3的位置插入100
        System.out.println(list1);

        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(11);
        list2.add(22);
        list2.add(33);
        list1.addAll(2,list2);
        System.out.println(list1);

        list1.remove(2);//删除下标为2的元素
        list1.removeFirst();//删除头元素
        list1.removeLast();//删除尾元素
        System.out.println(list1);

        System.out.println(list1.get(2));//获取下标为2的元素
        list1.set(0,20);
        System.out.println(list1);//将下标为0的元素设置为20
    }
}

三、ArrayList和LinkedList的区别

不同点ArrayListLinkedList
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持O(n)
头插需要搬移元素，效率低O(n)只需要改变指向，时间复杂度O(1)
插入空间不够时需要扩容没有容量的概念

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

相关文章：

  • SpringBoot入门实现简单增删改查
  • 【Vue】分享一个快速入门的前端框架以及如何搭建
  • 【STM32】HAL库USB实现软件升级DFU的功能操作及配置
  • 使用docker-compose安装Redis的主从+哨兵模式
  • 【论文阅读】SDA-FC: Bridging federated clustering and deep generative model
  • Vue3组件设计模式:高可复用性组件开发实战
  • 《Java核心技术II》实现服务器
  • vue3 父组件调用子组件方法
  • 在 WSL Ubuntu 上安装 ProxySQL 并配置 主从同步，读写分离，延迟检测
  • C++并发编程之掩藏任务延迟与提高响应性的应用说明
  • Windows MFC 管理员权限DragAcceptFiles无效 处理方法
  • JavaSwing游戏开发之Camera原理
  • Java 输入输出流(上)
  • Gitlab流水线配置
  • Java 后端整合 Swagger + Knife4j 接口文档
  • 学员答疑：安卓分屏窗口的TouchableRegion设置流程追踪
  • 【STM32】存储分析深入——堆栈与map文件
  • C++进阶(四)--set和map的介绍与使用
  • 【落羽的落羽 C语言篇】文件操作
  • stack_queue的底层,模拟实现,deque和priority_queue详解
  • 深入探讨DICOM医学影像中的MPPS服务及其具体实现
  • 【原创】大数据治理入门（4）《保护数据隐私：大数据治理的最佳实践》入门必看 高赞实用
  • 战场物联网：通信挑战与最新解决方案综述
  • BUUCTF[ACTF新生赛2020]easyre
  • ubuntu22.04：解决google chrome 访问百度页面加载慢的问题
  • C++ 并发编程之std::find的并发版本