【数据结构】LinkedList与链表

2023-09-17 23:32:41

文章目录

1. ArrayList的缺陷

上节课已经熟悉了ArrayList的使用，并且进行了简单模拟实现。通过源码知道，ArrayList底层使用数组来存储元素：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
	// 默认容量是10
	private static final int DEFAULT_CAPACITY = 10;
	//...
	// 数组：用来存储元素
	transient Object[] elementData; // non-private to simplify nested class access
	// 有效元素个数
	private int size;
	public ArrayList(int initialCapacity) {
	if (initialCapacity > 0) {
	this.elementData = new Object[initialCapacity];
	} else if (initialCapacity == 0) {
	this.elementData = EMPTY_ELEMENTDATA;
	} else {
	throw new IllegalArgumentException("Illegal Capacity: "+
	initialCapacity);
	}
	}
//
}

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在这里插入图片描述
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向或者双向
    在这里插入图片描述
  2. 带头或者不带头
    在这里插入图片描述
  3. 循环或者非循环
    在这里插入图片描述
    虽然有这么多的链表的结构，但是我们重点掌握两种:
    无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
    在这里插入图片描述
    无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

2.2 链表的实现

1.链表的功能

package mysingleList;


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.初始化链表

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 node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;

    }

开辟了内存空间
在这里插入图片描述
使每个node的next域指向下一个节点的地址，连接成链表
head指向第一个节点的地址
在这里插入图片描述

3.实现功能接口

3.1头插添加元素
 public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
        }
        else {
            node.next = this.head;
            this.head = node;
        }
    }

对 node.next = this.head;
this.head = node;
进行解释，node的next域指向下一个节点的地址
head继续为头节点在这里插入图片描述

3.2尾插法添加新元素
public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (this.head == null){
            this.head = node;
        }
        else {
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

找到最后一个元素cur，cur的next指向要插入元素的地址
在这里插入图片描述

3.3找到下标的前驱节点
 private ListNode searchPrev(int index){
            ListNode cur = this.head;
            int count = 0;
            while(count != index-1){
                cur = cur.next;
                count++;
            }
            return cur;
        }
3.4指定位置插入元素
public void addIndex(int index, int data) {
		//判断index的位置是否合法
        if(index < 0 || index >size()){
            return;
        }
        //插入到第一个节点位置
        if(index == 0){
            addFirst(data);
        }
        //插入到最后一个节点的位置
        if (index == size()){
            addLast(data);
        }
        //中间位置
        else {
            ListNode node = new ListNode(data);
            ListNode cur = searchPrev(index);
            node.next = cur.next;
            cur.next = node;
        }
    }

在这里插入图片描述

3.5指定元素是否存在
public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
        }

        return false;
    }

遍历一遍链表寻找是否有key元素

3.6找到指定元素的前驱节点
private ListNode findPrev(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
3.7删除指定节点
public void remove(int key) {
        if (this.head == null){
            System.out.println("没有节点，无法删除");
            return;
        }
        //指定元素在头节点
        if (this.head.val == key){
            this.head = this.head.next;
        }
        
        else {
            ListNode cur = findPrev(key);
            //没有找到指定元素
            if (cur == null){
                System.out.println("没有找到要删除的节点");
                return;
            }
            //找到了指定元素
           ListNode del = cur.next;
            cur.next = del.next;

        }
    }

在这里插入图片描述

3.8删除所有元素为key的节点
public void removeAllKey(int key) {
        if(this.head == null){
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur != null){
            if(cur.val == key){

                prev.next = cur.next;
                cur = cur.next;
            }
            else {
                prev = cur;
                cur = cur.next;
            }
        }
        //删除的节点为头节点
        if(this.head.val == key){
            this.head = this.head.next;
        }
    }
3.9链表的长度
public int size() {
        ListNode cur = this.head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
3.9清空链表
public void clear() {
        ListNode cur = this.head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = null;

            cur = curNext;
        }
        head = null;
    }

完整代码

package mysingleList;


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 node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;

    }
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
        }
        else {
            node.next = this.head;
            this.head = node;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (this.head == null){
            this.head = node;
        }
        else {
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        if(index < 0 || index >size()){
            return;
        }
        if(index == 0){
            addFirst(data);
        }
        if (index == size()){
            addLast(data);
        }
        else {
            ListNode node = new ListNode(data);
            ListNode cur = searchPrev(index);
            node.next = cur.next;
            cur.next = node;
        }
    }
        private ListNode searchPrev(int index){
            ListNode cur = this.head;
            int count = 0;
            while(count != index-1){
                cur = cur.next;
                count++;
            }
            return cur;
        }
    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
        }

        return false;
    }

    @Override
    public void remove(int key) {
        if (this.head == null){
            System.out.println("没有节点，无法删除");
            return;
        }
        if (this.head.val == key){
            this.head = this.head.next;
        }
        else {
            ListNode cur = findPrev(key);
            if (cur == null){
                System.out.println("没有找到要删除的节点");
                return;
            }
           ListNode del = cur.next;
            cur.next = del.next;

        }
    }
    private ListNode findPrev(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    @Override
    public void removeAllKey(int key) {
        if(this.head == null){
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur != null){
            if(cur.val == key){

                prev.next = cur.next;
                cur = cur.next;
            }
            else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
    }

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

    @Override
    public void clear() {
        ListNode cur = this.head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = null;

            cur = curNext;
        }
        head = null;
    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}
更多推荐

如何使用ArcGIS Pro提取河网水系

DEM数据除了可以看三维地图和生成等高线之外，还可以用于水文分析，这里给大家介绍一下如何使用ArcGISPro通过水文分析提取河网水系，希望能对你有所帮助。数据来源本教程所使用的数据是从水经微图中下载的DEM数据，除了DEM数据，常见的GIS数据都可以从水经微图中下载，你可以通过关注公号“水经注GIS”，然后在后台回复

1.8python基础语法——数据类型转换

1）转换数据类型的作用用户输入的数据是字符串类型，可以用类型转换将字符串类型转换为相应的数据类型。2）转换数据类型的函数函数说明int(x[,base])将x转换为一个整数float(x)将x转换为一个浮点数complex(real[,imag])创建一个复数，real为实部，imag为虚部str(x)将对象x转换为字

软件设计原则扩展

一、引言经典的软件设计7大原则开闭原则（OpenClosePrinciple,OCP）依赖倒置原则（DependenceInversionPrinciple,DIP）单一职责原则（SimpleResponsibilityPrinciple,SRP）接口隔离原则（InterfaceSegregationPrinciple

从零开始学习 Java：简单易懂的入门指南之不可变集合、方法引用（二十六）

不可变集合、方法引用1.不可变集合1.1什么是不可变集合1.2使用场景1.3不可变集合分类1.4不可变的list集合1.5不可变的Set集合1.6不可变的Map集合1.6.1：键值对个数小于等于101.6.2：键值对个数大于102.方法引用2.1体验方法引用2.2方法引用符2.3引用类方法2.4引用对象的实例方法2.5

【数据结构】TOP-K问题/使用堆解决

💐🌸🌷🍀🌹🌻🌺🍁🍃🍂🌿🍄🍝🍛🍤📃个人主页：阿然成长日记👈点击可跳转📆个人专栏：🔹数据结构与算法🔹C语言进阶🚩不能则学，不知则问，耻于问人，决无长进🍭🍯🍎🍏🍊🍋🍒🍇🍉🍓🍑🍈🍌🍐🍍文章目录TOP-K问题一、题目描述二、思路：三、代码实现1.随机产生一万

【每日一题】852. 山脉数组的峰顶索引

852.山脉数组的峰顶索引-力扣（LeetCode）符合下列属性的数组arr称为山脉数组：arr.length>=3存在i（0<i<arr.length-1）使得：arr[0]<arr[1]<...arr[i-1]<arr[i]arr[i]>arr[i+1]>...>arr[arr.length-1]给你由整数组成的山

数据结构——二叉树提升

二叉树题型练习前言一、节点个数以及高度等二、二叉树OJ题二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历单值二叉树二叉树最大深度检查两颗树是否相同.翻转二叉树对称二叉树另一颗树的子树总结前言现在我们开始一轮新的自我提升吧！二叉树的题目当然也更有难度！没有什么是生来就会的，尤其是代码这一方面更是讲究熟能生巧，现在的我们学

全能电子地图下载器3.0-下载离线地图瓦片

前言vue项目要部署到局域网内，不使用在线地图，而是离线地图，寻求了很多的解决方案，最终决定使用离线地图瓦片+leaflet.js实现效果！正文首先需要下载正版的软件，目前我实用的是V3.0版本的，可能和之前的有部分差异化，这个也属于正常。一、下载1.有CSDN会员下载渠道：https://download.csdn.

Vue入门--vue的生命周期

一.什么是Vue二.Vue的简介官方网址特点三.前后端的分离重大问题优势4.Vue入门定义一个管理边界​编辑测试结果vue的优势​编辑测试结果5.Vue的生命周期vue的生命周期图​编辑建立一个html测试结果一.什么是VueVue是一种流行的JavaScript前端框架，用于构建用户界面。它被设计为一种渐进式框架，可

CTF —— 网络安全大赛（这不比王者好玩吗？）

前言随着大数据、人工智能的发展，人们步入了新的时代，逐渐走上科技的巅峰。\⚔科技是一把双刃剑，网络安全不容忽视，人们的隐私在大数据面前暴露无遗，账户被盗、资金损失、网络诈骗、隐私泄露，种种迹象表明，随着互联网的发展，网络安全需要引起人们的重视。\互联网安全从其本质上来讲就是互联网上的信息安全。从广义来说，凡是涉及到互联

3.2 Android eBPF程序类型

写在前面为什么要先了解eBPF程序类型？从帮助函数中，我们可能基于内核的eBPF开放API，对eBPF的能力有一个比较细致的认识，但是这并不能让我们从全局，或者更概括的认识eBPF。eBPF程序类型能够更宏观的告诉我们，eBPF能做哪些事情（除网络相关）。一，eBPF程序类型内核中不同事件会触发不同类型的eBPF程序，

热文推荐
  1. 智慧养殖：浅谈视频监控与AI智能识别技术助力奶牛高效、智慧养殖

    一、方案背景随着科技的飞速发展，智能化养殖逐渐成为现代畜牧业的发展趋势。人工智能技术、物联网、视频技术、云计算、大数据等新兴技术，正在为奶牛养殖业带来全新的变革。越来越多的牧场、养殖场开始运用新技术来进行智能监管、提高生产效率、降低生产成本，助力饲养成本高的养殖业，向数字化、智能化、无人化发展方向转型。二、方案概述TS

  2. 计算机硬件设备和网络硬件设备

    计算机硬件设备计算机硬件设备是指构成计算机系统的各种实体部件，包括以下几类常见设备：1、中央处理器（CentralProcessingUnit，CPU）2、内存（RandomAccessMemory，RAM）3、硬盘驱动器（HardDiskDrive，HDD）4、显卡（GraphicsProcessingUnit，GP

  3. uni-app 之 vue位置怎样设置

    vue位置怎样设置VUE是一款流行的JavaScript框架，可以构建动态用户界面。在VUE中，位置的设置是非常重要的，因为它会影响到页面元素的布局。下面将详细介绍VUE中位置设置的基本概念以及如何使用VUE进行位置设置。在VUE中，位置设置一般使用CSS的position属性来实现。position属性有四个属性值：

  4. Spring Boot魔法：简化Java应用的开发与部署

    文章目录什么是SpringBoot？1.自动配置（Auto-Configuration）2.独立运行（Standalone）3.生产就绪（ProductionReady）4.大量的起步依赖（StarterDependencies）SpringBoot的魔法1.起步依赖（StarterDependencies）2.自动配

  5. CMake:测试的其他补充(重要)

    CMake:测试的其他补充（重要）导言预期测试失败项目结构CMakeLists.txt相关源码输出结果使用超时测试运行时间过长的测试项目结构CMakeLists.txt相关源码输出结果并行测试项目结构CMakeLists.txt相关源码输出结果运行测试子集项目结构CMakeLists.txt相关源码输出结果使用测试固件

  6. uniapp实现大气质量指标图（app端小程序端均支持，app-nvue不支持画布）

    效果图如下：思路：1.首先我想到的就是使用图标库echarts或ucharts，可是找了找没有找到类似的。2.其次我就想用画布来实现这个效果，直接上手。（app-vue和小程序均可以实现，但是在app-nvue页面不支持画布，尝试了一下再nvue页面直接导致程序闪退）3.后来，使用手动创建一个竖向的类似效果。注意：1.

  7. 【力扣每日一题】2023.9.21 收集树中金币

    目录题目：示例：分析：代码：题目：示例：分析：题目给我们一棵树，不过这棵树不是普通的树，而是无向无根树。给我们一个二维数组表示节点之间的连接关系，以及一个一维数组表示每个节点是否有金币。我们可以从任何一个节点出发，并且可以收集距离两格的节点的金币，每次可以移动到相邻的节点。问我们要收集完所有的金币并且最终要回到起点，最

  8. Python爬虫：aiohttp的介绍和基本使用

    aiohttp是一个用于编写异步网络应用程序的Python库，它建立在Python3.5+的asyncio框架之上。它允许你创建高性能的异步HTTP客户端和服务器，以处理并发请求和响应。下面是关于aiohttp的介绍和基本使用方法：安装aiohttp你可以使用pip来安装aiohttp：pipinstallaiohtt

  9. python魔术方法_对象_继承_复写_变量注解_函数注解_多态(04)

    文章目录python魔术方法_对象_继承_复写_变量注解_函数注解_多态(04)1对象的魔术方法1.1魔术方法实例：2对象的封装2.1私有变量：开头__（2个下划线）定义2.2案例私有变量访问：3继承3.1类继承语法：3.2类继承案例3.3多继承3.3.1多继承语法3.3.2多继承属性(pass使用)4复写4.1对父类