您现在的位置是:首页 > 正文

数据结构《LinkeList 双向链表》

2024-04-01 02:19:15阅读 3

LinkeList

LinkeList 的低层是由双向链表结构组成的,所有元素都是存放到单独的节点当中,通过地址引用将节点串联起来
因此在任意位置插入或删除元素时,都不在需要移动元素,效率较高

下面是双向链表的结构图:

在这里插入图片描述
在集合框架中,LinkedList也实现了List接口,具体如下:
在这里插入图片描述

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

LinkeList 的模拟实现

之前模拟过单向链表,所以前三个方法就不画图了,很简单

public class MyLinkedList {
   
    static class ListNode{
   
       public int val;  // 数值
       public ListNode prev;
       public ListNode next;
       // 初始化数值
        public ListNode(int val) {
   
            this.val = val;
        }
    }
    public ListNode head; //标记头节点
    public ListNode tail; //标记尾节点

    //打印双向链表的节点
    public void display(){
   
        ListNode cur = head;
        while (cur != null){
   
            System.out.println(cur.val+" ");
        }
        System.out.println();
    }

    //获取双向链表的长度
    public int size() {
   
        ListNode cur = this.head;
        int count = 0;
        while(cur != null){
   
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
   
        ListNode cur = this.head;
        while(cur != null){
   
            if(cur.val == key){
   
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

}

头插法

在双向链表的第一个节点的前面里添加一个新的节点

图解:
在这里插入图片描述
源代码:

public void addFirst(int data) {
   
        ListNode node = new ListNode(data);
        // 如果链表里没有节点的情况
        if(head == null){
   
            this.head = node;//第一个节点
            this.tail = node;// 最后一个节点
        }else {
   
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }

    }

尾插法

在双向链表的最后一个节点的后里添加一个新的节点

图解
在这里插入图片描述

源代码:

 public void addLast(int data) {
   
        ListNode node = new ListNode(data);
        // 如果链表里没有节点的情况
        if(this.head == null){
   
            this.head = node;//第一个节点
            this.tail = node;// 最后一个节点
        

网站文章

  • MapReduce案例11——影评分析1(两表联合查询)

    多表联合常用方式有两种:reduceJoin和mapjoin,其中reducejoin容易造成数据倾斜,对于并发执行的数据文件来说,常用mapjoin,在mapper阶段就完成数据连接,一般不会造成数...

    2024-04-01 02:19:08
  • 封装一个流水号ID生成器:id-spring-boot-starter

    封装一个流水号ID生成器:id-spring-boot-starter

    ID)是服务端系统的基础设施,而且ID号这个东西基本搞后端开发的程序员天天都要接触。而关于ID生成的算法现在业界首屈一指的当属Snowflake雪花算法。正是百度开源的一款基于Snowflake雪花算...

    2024-04-01 02:18:29
  • 20160527 数据分析与SAS9 对考生成绩进行频率分析

    利用分析家模块对第19名考生的成绩进行频率分析检查各科分数的频率分布:1 在分析家模块打开成绩数据集test0527_12 统计--描述性统计--频数统计--除了序号全选为input是指分析变量的显示顺序:无格式、格式化取值、在数据集中的顺序、频率降序plot是指设置条形图参数:水平显示、垂直显示table是指设置输出频率:输出频数频数百分比及累积、频数累积频数、频数及百分比、

    2024-04-01 02:18:22
  • 软考项目管理师(高级)快速通过分享

    我之前写过关于 PMP 的主题分享,关注公众号「kevinsheng」后,回复「pmp」即可查看。我参加了2018年上半年的软考(计算机与软件专业技术资格考试),报考的是信息系统项目管理师(高级),前...

    2024-04-01 02:18:14
  • Java线程池ThreadPoolExecutor使用和分析(二) - execute()原理

    Java线程池ThreadPoolExecutor使用和分析(二) - execute()原理

    相关文章目录: Java线程池ThreadPoolExecutor使用和分析(一) Java线程池ThreadPoolExecutor使用和分析(二) - execute()原理 Java线程池ThreadPoolExecutor使用和分析(三) - 终止线程池原理 execute()是 java.util.concurrent.Execut...

    2024-04-01 02:17:35
  • java的快速排序怎么写?

    答案:Java的快速排序的基本思想是:首先从待排序序列中随机选择一个元素作为基准值,然后将序列中所有小于基准值的元素放到基准值的左边,将所有大于基准值的元素放到基准值的右边,然后对基准值两边的子序列重...

    2024-04-01 02:17:28
  • 打开idea报错:com.intellij.diagnostic.PluginException: Fatal error initializing ‘com.alibaba...

    打开idea报错:com.intellij.diagnostic.PluginException: Fatal error initializing ‘com.alibaba...

    PyCharm IDE安装插件后启动报错的解决方法_IF先生的博客-CSDN博客

    2024-04-01 02:17:22
  • Java使用 Executors 创建四种线程池原理

    Java使用 Executors 创建四种线程池原理

    这四种线程池本地都是通过用不同的参数去 new ThreadPoolExecutor 实现的,也就是说想要理解好这四种线程池的原理以及应用场景,还是需要去了解ThreadPoolExecutor 。 阿里开发手册上不建议使用Executors类提供的四种线程池,会出现内存溢出的错误(OOM)。

    2024-04-01 02:17:16
  • Spring框架之注解开发

    Spring框架之注解开发

    Spring是轻代码而重配置的框架,配置比较繁重,影响开发效率,所以注解开发是一种趋势。

    2024-04-01 02:16:36
  • mysql每月的第一天的日期,当月第一天的日期和前5天的日期。的MySQL

    I need a query similar to this one:SELECT *FROM myTableWHEREDATE_FORMAT(date,'%Y-%m-%d') BETWEEN <1> AND <2>Where <1> is the date of the first day of the month and <2> is the d...

    2024-04-01 02:16:29