当前位置: 首页 > news >正文

【数据结构】双向链表 - 指南

文章目录

  • 什么是LinkedList
  • LinkedList的使用
    • LinkedList的构造
    • LinkedList的其他常用方法
    • LinkedList的遍历
  • ArrayList和LinkedList的区别


小贴士:建议学习这章之前先看一下上一章的单向链表哦

什么是LinkedList

LinkedList的底层是双向链表结构(链表后面介绍),由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

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

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

LinkedList的使用

LinkedList的构造

在这里插入图片描述
我们在顺序表那一章节中(详见顺序表)详细的探讨过构造函数的问题,当时我们知道构造函数时可以传递一个ArrayList类型的表的参数。不过由于只要是Collection的子类都可以传参,所以传递的参数不仅可以是ArrayList,还可以是任意的其他的类型。比如下面这个案例:

public static void main(String[] args) {
// 构造一个空的LinkedList
List<
Integer> list1 = new LinkedList<
>();
List<
String> list2 = new java.util.ArrayList<
>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<
String> list3 = new LinkedList<
>(list2);
}

LinkedList的其他常用方法

在这里插入图片描述
这些常用的方法我们很容易就可以模拟实现,并且这些方法在ArrayList那一章中我们就模拟实现过了,所以我们实现一些特殊的方法,具体如下:
还是先建立一个MyList接口,然后再用链表类实现它:

package demo;
public interface MyList {
//头插法
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 clear() ;
public void display() ;
}

双向链表类:

package demo;
// 2、无头双向链表实现
public class MyLinkedList
implements MyList{
static class ListNode
{
public ListNode next;
public ListNode prev;
int val;
public ListNode(int val) {
this.val = val;
}
}
ListNode head;
ListNode last;
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null){
head = last = node;
return;
}
head.prev = node;
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(last == null){
last = head = node;
return;
}
node.prev = last;
last.next = node;
last = node;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
ListNode cur = head;
ListNode node = new ListNode(data);
if(index == 0){
node.next = head;
head.prev = node;
head = node;
return;
}
if(index == size()){
node.prev = last;
last.next = node;
last = node;
return;
}
while(index != 0){
cur = cur.next;
index--;
}
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//开始删除
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//开始删除
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
public void clear(){
last = null;
head = null;
}
}

还是建议大家可以跟着自己尝试模拟实现一下

LinkedList的遍历

public static void main(String[] args) {
LinkedList<
Integer> list = new LinkedList<
>();
list.addLast(1);
list.addLast(1);
list.addLast(1);
list.addLast(2);
list.add(2,3);
list.add(0,9);
list.addLast(6);
System.out.println("====for循环====");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
System.out.println("====for each循环====");
for(Integer x : list){
System.out.print(x + " ");
}
System.out.println();
System.out.println("====iterator====");
Iterator<
Integer> it = list.iterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
System.out.println("====listIterator反向输出====");
ListIterator<
Integer> it2 = list.listIterator(list.size());
while(it2.hasPrevious()){
System.out.print(it2.previous() + " ");
}
System.out.println();
}

在这里插入图片描述
遍历这一部分跟顺序表大差不差,其中迭代器输出的方法还是着重理解一下。

ArrayList和LinkedList的区别

在这里插入图片描述


http://www.hskmm.com/?act=detail&tid=13289

相关文章:

  • 告别“能源糊涂账”:MyEMS如何帮企业把能耗数据“算明白、用到位”
  • Windows 离线环境下使用 VS Code 连接容器 Python 环境完整指南(亲测可用)
  • Macos 安装kali报错
  • 完整教程:线程、进程、协程
  • CF913G Power Substring
  • YC大佬分享的 10 个 vibe coding技巧,看完收获巨大
  • ES集群部署-EFK架构实战 - 实践
  • 《BOE解忧实验室》第四季圆满收官 以科技重塑文化生活新范式
  • 洛谷P2261 [CQOI2007] 余数求和
  • arc206 总结
  • 科研必读|提升酿酒酵母表达蛋白产量的关键技术
  • 完整教程:uniapp、devceo华为鸿蒙运行模拟器报错:未开启Hyper-V
  • 浏览器访问页面卡顿刷新页面方法
  • 完整教程:散斑深度相机原理
  • 如何用 Dify 无代码工作流实现 AI 自动化抓取与分析 LinkedIn 招聘数据
  • WSL+共享文件夹搭建zephyr工作环境
  • 如果 Spring Cloud Feign 配置了 OkHttp3 非阻塞 IO(NIO),那么还需要reactor 模型来提高性能吗
  • 数据结构-单链表基础2
  • G1垃圾回收过程
  • Trellix自动化大规模修复开源漏洞,已修补超6万个项目
  • 爆款游戏背后:尚娱如何借助阿里云 Kafka Serverless 轻松驾驭“潮汐流量”?
  • Vben Admin5.0 keepAlive缓存和onActivated未生效
  • 版本速递 | 华为云Versatile智能体平台 新增特性介绍(2025年9月发布)
  • JVM体系结构
  • PE程序常见脱壳方案
  • 基于二值化断裂裂缝的裂缝拼接算法
  • spring ai基于内存RAG尝鲜
  • 想自己做大模型备案的企业看过来【评估测试题+备案源文件】
  • 基于 IOCP 的协程调度器——零基础深入浅出 C++20 协程
  • Gitee PPM风险矩阵:数字化转型中的项目管理预警雷达