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

news/2025/1/20 2:25:13/

专栏：数据结构(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;//链表的尾@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void display() {}@Overridepublic 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也要存储新的头节点的地址。

@Overridepublic 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;}}@Overridepublic 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();}
}

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

@Overridepublic 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());}
}
@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

1.2. 尾插法

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

@Overridepublic 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;
@Overridepublic 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节点也可以。

@Overridepublic 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也手动置为空。

完整代码：

@Overridepublic 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语句之后直接去指向下一个节点。

@Overridepublic 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);elselinkBefore(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的位置插入100System.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.ppmy.cn/news/1564554.html

相关文章

网络编程：基于TCP/UDP实现客户端和服务端通信（C语言实现简单易懂）

网络编程：基于TCP/UDP实现客户端和服务端通信（C语言实现简单易懂）

wx&#xff1a;嵌入式工程师成长日记 https://mp.weixin.qq.com/s/_eqFaiID2kzFuk3zejFptg?token382885458&langzh_CNhttps://mp.weixin.qq.com/s/_eqFaiID2kzFuk3zejFptg?token382885458&langzh_CN TCP是一个面向连接的&#xff0c;安全的&#xff0c;流式传输协议…
阅读更多...
minio https配置

minio https配置

minio启动时候指定数据目录,配置文件&#xff0c;密钥文件目录&#xff0c;环境文件 1.创建minio用户,专门用于服务启动的 groupadd -r minio-user useradd -M -r -g minio-user minio-user 2.在当前用户目录下创建minio目录&#xff0c;存储minio相关文件 mkdir minio 在mini…
阅读更多...
el-dialog弹窗的@open方法中，第一次引用ref发现undefined问题，第二次后面又正常了

el-dialog弹窗的@open方法中，第一次引用ref发现undefined问题，第二次后面又正常了

解决方法 直接不用这个open方法&#xff0c;转而用opened&#xff0c;代码例子&#xff1a; <el-dialog title"单个新增" :visible.sync"PlacardShowSingle" opened"openpbSingle()" width"1100px" top"1%" :close-on-c…
阅读更多...
【Leetcode 热题 100】45. 跳跃游戏 II

【Leetcode 热题 100】45. 跳跃游戏 II

问题背景 给定一个长度为 n n n 的 0 0 0 索引 整数数组 n u m s nums nums。初始位置为 n u m s [ 0 ] nums[0] nums[0]。 每个元素 n u m s [ i ] nums[i] nums[i] 表示从索引 i i i 向前跳转的最大长度。换句话说&#xff0c;如果你在 n u m s [ i ] nums[i] nums[i…
阅读更多...
EAMM: 通过基于音频的情感感知运动模型实现的一次性情感对话人脸合成

EAMM: 通过基于音频的情感感知运动模型实现的一次性情感对话人脸合成

EAMM: 通过基于音频的情感感知运动模型实现的一次性情感对话人脸合成 1所有的材料都可以在EAMM: One-Shot Emotional Talking Face via Audio-Based Emotion-Aware Motion Model网站上找到。 摘要 尽管音频驱动的对话人脸生成技术已取得显著进展&#xff0c;但现有方法要么忽…
阅读更多...
JAVA实现五子棋小游戏(附源码)

JAVA实现五子棋小游戏(附源码)

文章目录 一、设计来源捡金币闯关小游戏讲解1.1 主界面1.2 黑棋胜利界面1.3 白棋胜利界面 二、效果和源码2.1 动态效果2.2 源代码 源码下载更多优质源码分享 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/145161039 JA…
阅读更多...
IT程序设计文档，软件需求设计文档，详细设计模板（Word原件）

IT程序设计文档，软件需求设计文档，详细设计模板（Word原件）

1引言 1.1编写目的 1.2项目背景 1.3参考材料 2系统总体设计 2.1整体架构 2.2整体功能架构 2.3整体技术架构 2.4设计目标 2.5.1总体原则 2.5.2实用性和先进性 2.5.3标准化、开放性、兼容性 2.5.4高可靠性、稳定性 2.5.5易用性 2.5.6灵活性和可扩展性 2.5.7经济性…
阅读更多...
vue v-if和key值的注意的地方

vue v-if和key值的注意的地方

v-if的使用 v-if 用来判断元素的显示与隐藏&#xff0c; 与v-show的相同和区别&#xff1a; v-if和v-show 为true 都占据位置&#xff0c;为false都不占有位置 控制手段&#xff1a;v-if 通过删除和添加dom结构进行显示和隐藏&#xff0c;v-show通过css的display&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023