Java集合类——LinkedList（单链表及双链表）

article/2025/9/11 1:13:10

一，ArrayList的缺陷

1.空间浪费

在之前的博客中，我利用源码详细的讲解了ArrayList这个集合类（尤其是扩容机制），可以知道ArrayList的底层主要是一个动态的可变数组，容量满的时候需要进行1.5倍扩容。但是我们现在考虑这样一个问题，假设ArrayList底层数组的容量是100，我们需要存放101个元素时，当存放第101个元素时需要1.5倍扩容（扩容之后的容量是150），此时势必会造成49个存储空间的浪费！

2.时间开销大

ArrayList底层是一个数组，当我们对顺序表进行插入和删除时，需要移动大量的元素，大大提高了时间复杂度，所以可以看出ArrayList并不适用于进行大量插入和删除的操作。

针对上述ArrayList的两大缺陷，Java是否提供了其他的集合类或者数据结构来解决呢？

1.进行元素扩容时能否根据需求来进行扩容，需要多少空间就去申请多少空间；

2.在进行插入和删除的时候，可不可以不需要移动大量元素。

今天所要介绍的LinkedList集合类和链表的数据结构将很好的解决这两个问题！！！

二，链表

2.1 链表的概念

相对于顺序表，链表是一种在逻辑上连续，在存储上不一定连续的数据结构。其中链表每个元素之间的逻辑关系是通过引用来实现的。

链表中的每一个元素称为一个节点，每一个节点至少包含两类数据：

1.数据域（存放该节点的数据信息）

2.节点域（实现链表节点与节点之间的逻辑关系，对于单链表来说只需要存储一个next即可（存储下一个节点的地址），对于双链表来说则需要存储next和prev（分别存储下一个节点和前一个节点的地址））

2.2 链表的分类

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

我们只需要重点掌握两种即可：

1.无头单向非循环链表（因为笔试的OJ题中经常会考）；

2.无头双向链表（因为LinkedList的底层就是不带头的双链表）。 

三，顺序表和链表的区别

不同点
ArrayList
LinkedList
存储空间上
物理上一定连续
逻辑上连续，但物理上不一定连续
随机访问
支持： O(1)
不支持： O(N)
头插
需要搬移元素，效率低 O(N)
只需修改引用的指向，时间复杂度为 O(1)
插入
空间不够时需要扩容
没有容量的概念
应用场景
元素高效存储 + 频繁访问
任意位置插入和删除频繁

四，无头单向非循环链表的实现

定义一个MySingleList类来实现单链表的方法，用TestMySingleList类来测试MySingleList类的方法

import java.util.List;public class MySingleList {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;//第一节点的引用，默认为null//打印链表public void display() {ListNode cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//获取链表长度public int size() {ListNode cur = this.head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = this.head;this.head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = this.head;if (this.head == null) {this.head = node;} else {while (cur.next != null) {cur = cur.next;}//此时已经处于尾节点cur.next = node;}}//任意index位置插入（假设第一个节点的下表为0）public void add(int index, int data) {//判断index位置的合法性if (index < 0 || index > size()) {System.out.println("index位置不合法！");//也可以抛异常} else if (index == 0) {addFirst(data);} else if (index == size()) {addLast(data);} else {//1.找到所需插入index位置的前驱ListNode cur = findIndexPrev(index);//2.修改引用的指向ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}}private ListNode findIndexPrev(int index) {ListNode cur = this.head;while (index - 1 != 0) {cur = cur.next;index--;}return cur;}//删除第一次出现的关键字keypublic void remove(int key) {if (this.head == null) {System.out.println("链表为空！");return;}if (this.head.val == key) {this.head = this.head.next;return;}ListNode cur = findPrev(key);//找到所需删除关键字key的前驱if (cur == null) {System.out.println("没有关键字key！");} else {cur.next = cur.next.next;}}private ListNode findPrev(int key) {ListNode cur = this.head;while (cur.next != null) {if (cur.val == key) {return cur;}cur = cur.next;}return null;}//删除所有出现的关键字keypublic void removeAllKey(int key) {if (this.head == null) {System.out.println("链表为空！");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;}}//清空链表public void clear() {this.head = null;//单链表只需要将指向第一个节点的引用指向null即可}
}

public class TestMySingleList {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.addLast(1);mySingleList.addLast(2);mySingleList.addLast(3);mySingleList.addLast(4);mySingleList.addLast(5);mySingleList.display();mySingleList.addFirst(0);mySingleList.display();mySingleList.remove(0);mySingleList.addLast(1);mySingleList.addLast(1);mySingleList.addLast(1);mySingleList.removeAllKey(1);mySingleList.display();}
}

 

五，无头双向非循环链表的实现

定义一个MyLinkedList类来实现单链表的方法，用TestMyLinkedList类来测试MyLinkedList类的方法

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;//定义一个头引用，默认为nullListNode tail;//定义一个尾引用，默认为null//打印链表public void display() {ListNode cur = this.head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//获取链表长度public int size() {ListNode cur = this.head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}//判断链表是否包含某个元素keypublic 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 (this.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;} else {this.tail.next = node;node.prev = this.tail;this.tail = node;}}//任意index位置插入（假设第一个节点的下标为0）public void add(int index, int data) {//判断index位置的合法性if (index < 0 || index > size()) {System.out.println("index位置不合法！");//也可以抛异常} else if (index == 0) {addFirst(data);} else if (index == size()) {addLast(data);} else {//1.找到index位置的节点ListNode cur = findIndexPrev(index);//2.修改指向的引用ListNode node = new ListNode(data);node.next = cur;node.prev = cur.prev;cur.prev.next = node;cur.prev = node;}}private ListNode findIndexPrev(int index) {ListNode cur = this.head;while (index != 0) {cur = cur.next;index--;}return cur;}//删除第一次出现的关键字keypublic void remove(int key) {if (this.head == null) {System.out.println("链表为空！");return;}ListNode cur = this.head;while (cur != null) {if (cur.val == key) {if (cur == this.head) {this.head = this.head.next;if (this.head != null) {this.head.prev = null;} else {this.tail = null;}} else {cur.prev.next = cur.next;if (cur.next != null) {cur.next.prev = cur.prev;} else {this.tail = cur.prev;this.tail.next = null;}}return;}cur = cur.next;}}//删除所有出现的关键字keypublic void removeAllKey(int key) {if (this.head == null) {System.out.println("链表为空！");return;}ListNode cur = this.head;while (cur != null) {if (cur.val == key) {if (cur == this.head) {this.head = this.head.next;if (this.head != null) {this.head.prev = null;} else {this.tail = null;}} else {cur.prev.next = cur.next;if (cur.next != null) {cur.next.prev = cur.prev;} else {this.tail = cur.prev;this.tail.next = null;}}}cur = cur.next;}}//清空链表public void clear() {ListNode cur = this.head;while (cur != null) {ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}this.head = null;this.tail = null;}
}

public class TestMyLinkedList {public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.addLast(1);myLinkedList.addLast(2);myLinkedList.addLast(3);myLinkedList.addLast(4);myLinkedList.addLast(5);myLinkedList.addFirst(0);myLinkedList.display();myLinkedList.remove(0);myLinkedList.display();myLinkedList.add(2,10);myLinkedList.display();myLinkedList.addLast(1);myLinkedList.addLast(1);myLinkedList.removeAllKey(1);myLinkedList.display();}
}

 


http://chatgpt.dhexx.cn/article/YwRWIYam.shtml

相关文章

java学习之LinkedList（链表）

java学习之LinkedList（链表）

LinkedList&#xff1a;一种线性表&#xff0c;但不按照线性顺序存储数据&#xff08;实际上为链表&#xff09;。 链表分为单向链表和双向链表&#xff0c;实际应当还有循环链表。 单向链表&#xff1a;将一个区域分成两部分&#xff0c;分别为节点区域和数据域。 如下图所…
阅读更多...
LinkedList和ArrayList对比各有什么优势？

LinkedList和ArrayList对比各有什么优势？

一、LinkedList的概述 1. LinkedList是双向链表实现的List 2. LinkedList是非线程安全的 3. LinkedList元素允许为null&#xff0c;允许重复元素 4. LinkedList是基于链表实现的&#xff0c;因此插入删除效率高&#xff0c;查找效率低(虽然有一个加速动作) 5. LinkedList是…
阅读更多...
LinkedList详解

LinkedList详解

文章目录 介绍继承体系 LinkedLists实现底层数组结构构造函数getFirst(),getLast()removeFirest(),removeLast(),remove(e),remove(index)删除head元素删除last元素add()addAll()clear()查找操作遍历 介绍 LinkedList同时实现了List接口和Deque对口&#xff0c;也就是收它既可…
阅读更多...
Chrome被百度网页劫持

Chrome被百度网页劫持

Chrome被百度劫持的解决办法 浏览器的运行太慢了&#xff0c;就想试试谷歌的浏览器&#xff0c;但是每次打开的都是百度的界面&#xff0c;明显就是被劫持了&#xff0c; 看了网上的好多方法都没有什么明显的效果 问题 在使用Chrome浏览器打开后直接弹出一个百度的界面这看着就…
阅读更多...
网页被劫持怎么修复？主页被劫持修复方法

网页被劫持怎么修复？主页被劫持修复方法

电脑的浏览器被劫持了应该怎么解决&#xff1f;小编今天就来教大家解决电脑浏览器自动跳转到一个网页中的问题。 方法步骤 1.随着网络的兴起&#xff0c;更多的小伙伴享受到网络带来的便利生活&#xff0c;其中上网浏览就是非常受欢迎的一个功能&#xff0c;但是很多不法分子看…
阅读更多...
Google Chrome主页被iduba劫持解决方法

Google Chrome主页被iduba劫持解决方法

今天用电脑的时候发现google的主页被改成了iduba的主页&#xff0c;烦的一比&#xff0c;看了好久才解决1.查看chrome://version 在命令行处会发现带有iduba的网站&#xff0c;我这里解决了&#xff0c;就没有了 2.点开google快捷方式的属性进行修改 将命令行中的代码全部复制…
阅读更多...
浏览器被劫持怎么解决？关于浏览器被劫持主页的处理方法

浏览器被劫持怎么解决？关于浏览器被劫持主页的处理方法

背景： 上个月重做了win10系统，系统激活过程中没有出现任何问题。重装office套装，使用暴风激活下载地址： （http://win.shibojiaa.cn/baofeng/）激活office套装后，发现所有浏览器主页被劫持。打开任何一个浏览器地址栏中显示：（http://uj7.gndh555.top/）随后跳转hao123。…
阅读更多...
Microsoft edge 主页被劫持的处理办法

Microsoft edge 主页被劫持的处理办法

最根本的办法&#xff0c;如果是任务栏固定打开后发现主页被劫持&#xff0c;应该是弄明白任务栏的链接是来自电脑的开始页面还是桌面的快捷方式。 如果是开始界面应用固定于任务栏&#xff0c;那么找到开始界面的Microsoft edge&#xff0c;右键然后找到所在文件夹。 找到开始…
阅读更多...
浏览器主页被劫持，跳转hao123解决办法！

浏览器主页被劫持，跳转hao123解决办法！

劫 持 指 南 前戏-疑难杂症小妙招 当打开电脑准备划水时&#xff0c;结果一打开浏览器&#xff0c;就发现它自动打开一个新的链接&#xff0c;紧接着又跳转到一个特定网页上去了&#xff0c;大家肯定心里那个气啊&#xff0c;打开百度一顿搜索&#xff0c;试了各种方法都不行…
阅读更多...
百度主页被“/?tn=88093251_85_hao_pg“劫持的一种解决办法

百度主页被“/?tn=88093251_85_hao_pg“劫持的一种解决办法

前言 在闲暇之余换了个系统&#xff0c;为了方便使用了在线的小白一键装机安装的win10专业版&#xff0c;先抛开携带的各种垃圾软件不说&#xff0c;最不爽的还是主页无论如何修改都被百度劫持。 内容 尝试了网上各种解决办法&#xff0c;其中包括但不限于&#xff1a; 下…
阅读更多...
Chrome主页被劫持怎么破

Chrome主页被劫持怎么破

之前遇到Chrome被2345劫持了&#xff0c;导致的结果是每天初次打开Chrome都会进入2345的流氓主页&#xff0c;尝试了若干解决办法&#xff0c;最终得以解决。现简要记录一下所尝试过的方法以及解决过程&#xff0c;以下所涉及到的任何一种能够方法都有可能导致Chrome浏览器的劫…
阅读更多...
教你解决浏览器被360劫持篡改主页的麻烦

教你解决浏览器被360劫持篡改主页的麻烦

前言 相信很多的小伙伴都遇到一个问题&#xff0c;就是好端端的&#xff0c;打开自己的edge或者Chrome&#xff0c;突然发现自己的主页变成了这样&#xff08;下图&#xff09; 不得不说&#xff0c;这个看得人真的不适。&#xff08;晕&#x1f635;&#xff09;相信大部分人还…
阅读更多...
Motan RPC

Motan RPC

中文文档&#xff1a;https://github.com/weibocom/motan/wiki/zh_userguide#%E9%85%8D%E7%BD%AE%E8%AF%B4%E6%98%8E 微信公众号
阅读更多...
Motan整体结构详述

Motan整体结构详述

简述 Motan是一套高性能、易于使用的分布式远程服务调用(RPC)框架。 文章结构 1.调用详解 2.注册中心 3.支持的协议 4.配置概述 5.注解配置 6.架构概述 7.模块概述 8.运维监控 高清原图见脑图地址http://naotu.baidu.com/file/2832af5a32a02ea63bb0e826a966d502?token4e7921e3…
阅读更多...
motan源码分析三：与spring框架的结合

motan源码分析三：与spring框架的结合

在本文第一章&#xff0c;分析的demo中使用了代码加载的方式加载了相关的类&#xff0c;但在我们的实际工作中&#xff0c;使用spring来加载相关的类的情况会更多&#xff0c;本文将分析一下motan是如何与spring一起协同工作的&#xff0c;主要的原理就是利用了spring支持的自定…
阅读更多...
motan源码分析一：服务发布及注册

motan源码分析一：服务发布及注册

motan是新浪微博开源的服务治理框架&#xff0c;具体介绍请看&#xff1a;http://tech.sina.com.cn/i/2016-05-10/doc-ifxryhhh1869879.shtml. 本系列的文章将分析它的底层源码&#xff0c;分析的源码版本为&#xff1a;0.1.2。第一篇文章将以服务的发布和注册开始&#xff0c;…
阅读更多...
轻量级Rpc框架设计--motan源码解析六:client端服务发现

轻量级Rpc框架设计--motan源码解析六:client端服务发现

一, Client端初始化工作 client端通过RefererConfigBean类实现InitializingBean接口的afterPropertiesSet方法, 进行下面三项检查配置工作: ①checkAndConfigBasicConfig(); // 检查并配置basicConfig ②checkAndConfigProtocols(); //检查并配置protocols ③checkAndConfi…
阅读更多...
java rpc motan_【RPC 专栏】Motan 中使用异步 RPC 接口

java rpc motan_【RPC 专栏】Motan 中使用异步 RPC 接口

为什么慢&#xff1f; 多线程加速 异步调用 RPC 异步调用 总结 这周六参加了一个美团点评的技术沙龙&#xff0c;其中一位老师在介绍他们自研的 RPC 框架时提到一点&#xff1a;RPC 请求分为 sync&#xff0c;future&#xff0c;callback&#xff0c;oneway&#xff0c;并且需要…
阅读更多...
Motan-远程调用的rpc框架的负载均衡策略

Motan-远程调用的rpc框架的负载均衡策略

虽然我不会&#xff0c;但是偶然之间看到了Motan远程调用框架的一些内容&#xff0c;然后直接copy过来了&#xff0c;想着以后自己可能看看 集群中的loadbalance负载均衡策略 ActiveWeightLoadBalance"低并发优化" 负载均衡 /** Copyright 2009-2016 Weibo, Inc.** …
阅读更多...
motan源码分析五：cluster相关

motan源码分析五：cluster相关

上一章我们分析了客户端调用服务端相关的源码&#xff0c;但是到了cluster里面的部分我们就没有分析了&#xff0c;本章将深入分析cluster和它的相关支持类。 1.clustersupport的创建过程&#xff0c;上一章的ReferConfig的initRef()方法中调用了相关的创建代码&#xff1a; fo…
阅读更多...
推荐文章

Copyright @ 2022~2023