数据结构之链表

写在前面

链表是一种常用的线性数据结构,在jdk中也提供具体的实现类java.util.LinkedList。本文来看下其相关内容。

1:链表的特点

链表是一种由很多个节点组成的线性数据结构,每个节点都有一个指向下一个节点的引用,从而构成,像下图:
在这里插入图片描述
这种链表叫做单向链表,如果是节点在此基础上增加一个指向上一个节点的引用,则就变成了双向链表,如下图:
在这里插入图片描述
如果是在单链表的基础上尾节点增加一个指向头节点的引用,则就构成了循环链表,如下图:
在这里插入图片描述

因此最基础的链表是单向链表,双向链表和循环链表都可以在其基础上通过增加相关的节点引用而成。

2:实现双向链表

因为jdk提供的链表实现就是双向链表,为了在学习链表的同时能够更加熟悉jdk提供的类,所以我们照葫芦画瓢也来自己实现一个双向链表的例子,首先来定义接口:

package com.dahuyou.datastructure.linkedlist;public interface List<E> {/*** Appends the specified element to the end of this list (optional* operation).* <p>* 追加元素到尾部!*/boolean add(E e);/*** Removes the first occurrence of the specified element from this list,* if it is present (optional operation).  If this list does not contain* the element, it is unchanged.  More formally, removes the element with* the lowest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns <tt>true</tt> if this list* contained the specified element (or equivalently, if this list changed* as a result of the call).** 删除指定的元素,会删除第一个匹配的元素,如果是成功找到并删除则返回true,否则返回false*/boolean remove(Object o);/*** Returns the element at the specified position in this list.** 返回指定位置的元素*/E get(int index);// --- 其他非java.util.List接口中提供的方法,自己个想的 --- //boolean addFirst(E e);boolean addLast(E e);void printLinkedList();}

支持双向链表的节点类(直接复制的java.util.LinkedList的Node类)

/*** 链表节点的内部静态类* @param <E>*/
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}

实现类:

package com.dahuyou.datastructure.linkedlist;/*** 链表类* @param <E>*/
public class LinkedList<E> implements List<E> {// transient:我没用,别序列化我!!!transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*            (first.prev == null && first.item != null)*/transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*            (last.next == null && last.item != null)*/transient Node<E> last;@Overridepublic boolean add(E s) {return false;}@Overridepublic boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}private E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;return element;}@Overridepublic E get(int index) {return null;}@Overridepublic boolean addFirst(E s) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, s, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;return true;}@Overridepublic boolean addLast(E s) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, s, null);last = newNode;if (l == null) {first = newNode;} else {l.next = newNode;}size++;return true;}@Overridepublic void printLinkedList() {if (this.size == 0) {System.out.println("链表为空");} else {Node<E> temp = first;System.out.print("目前的列表,头节点:" + first.item + " 尾节点:" + last.item + " 整体:");while (temp != null) {System.out.print(temp.item + ",");temp = temp.next;}System.out.println();}}/*** 链表节点的内部静态类* @param <E>*/private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
}

测试:

package com.dahuyou.datastructure.linkedlist;public class TT {public static void main(String[] args) {List<String> list = new LinkedList<>();// 添加元素list.add("a");list.addFirst("b");list.addLast("c");// 打印列表list.printLinkedList();// 头插元素list.addFirst("d");// 删除元素list.remove("b");// 打印列表list.printLinkedList();}}

运行:

目前的列表,头节点:b 尾节点:c 整体:b,c,
目前的列表,头节点:d 尾节点:c 整体:d,c,Process finished with exit code 0

3:使用场景

  • 频繁插入和删除(时间问题)
相比数组更优的时间复杂度,只需要断开和🔗相关节点即可。
  • 元素大小不一样(空间浪费问题)
相比数组要求所有元素占用空间相同,链表并无此限制,因此可更好的避免空间浪费。
  • 元素个数不确定(扩容问题)
个数不确定,数组无法实现申请特定的空间,后续如果涉及到扩容,则需要重新申请内存空间。
  • 实现高阶数据结构
因为链表更加灵活,所以更适合用来实现高阶的数据结构,如栈,队列,跳表(https://dongyunqi.blog.csdn.net/article/details/127107229)等。

写在后面

参考文章列表

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397780.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity(2022.3.38LTS) - 下载,安装

目录 A. 简介 B. 下载和安装UnityHub C. 下载安装unity编辑器 安装页面 选择版本 添加模块 D.总结 A. 简介 Unity 是一款广泛使用的跨平台游戏开发引擎。 一、主要特点 跨平台性&#xff1a; 支持多种主流平台&#xff0c;包括 Windows、Mac、Linux、iOS、Android、Xb…

LeetCode_sql_day15(262.行程与用户)

描述&#xff1a;262. 行程和用户 - 力扣&#xff08;LeetCode&#xff09; 取消率 的计算方式如下&#xff1a;(被司机或乘客取消的非禁止用户生成的订单数量) / (非禁止用户生成的订单总数)。 编写解决方案找出 "2013-10-01" 至 "2013-10-03" 期间非禁止…

Vue 应用实例的关键方法与配置案例一

目录 createApp createSSRApp app.mount app.unmount app.component app.directive Vue3.X自定义全局指令 Vue2.X自定义全局指令 app.use app.mixin 非 VIP 用户能够免费下载博文资源 createApp createApp 是 Vue 3.0 中用于创建应用实例的方法。它接收一个…

127. Go反射基本原理

文章目录 反射基础 - go 的 interface 是怎么存储的&#xff1f;iface 和 eface 的结构体定义&#xff08;runtime/iface.go&#xff09;&#xff1a;_type 是什么&#xff1f;itab 是什么&#xff1f; 反射对象 - reflect.Type 和 reflect.Value反射三大定律Elem 方法reflect.…

mysql中select的执行流程

目录 引言 SELECT查询语句的重要性 ​编辑引言部分重写示例&#xff1a; MySQL架构概览 MySQL架构概述 Server层的核心功能模块 知识点图文结合示例&#xff1a; 连接器的作用 连接器的职责 连接器职责 查询缓存的工作原理 查询缓存的概念 查询缓存的工作机制 查询…

虚幻引擎 C++ 实现平面阴影

1、平面阴影介绍 平面阴影是一种相对简单的渲染阴影的方式&#xff0c;可以理解为对一个模型渲染两次&#xff0c;一次是渲染模型本身&#xff0c;另一次是渲染模型的投影。渲染投影可以看作是将模型的顶点变换到地面的投影空间再渲染&#xff0c;可以理解为渲染了一个“压扁”…

Linux内核编程(十二)热插拔

本文目录 一、知识点1. 热插拔概念2. 热插拔机制3. Netlink机制 二、内核发送uevent事件到用户空间1. kobject发送uevent事件2. udevadm命令查看★示例代码&#xff1a;★优化&#xff1a;完善kset_uevent_ops&#xff08;热插拔事件结构体&#xff09; 三、用户空间使用Netlin…

Dubbo源码深度解析(四)

接上篇博客《Dubbo源码深度解析(三)》&#xff0c;上篇博文&#xff0c;主要讲的是DubboBootstrap#start()方法中调用到的其他方法&#xff0c;以及讲到ServiceConfig#export()方法的调用链路。其中讲到最核心的方法为ServiceConfig#doExportUrlsFor1Protocol()&#xff0c;还没…

CentOS7 配置 nginx 和 php 方案

配置方案 一、安装软件二、编写配置文件&#xff0c;连接PHP三、引用文件四、测试 鉴于网上教程错综复杂&#xff0c;写下一这篇文章 本教程只需要三步即可 一、安装软件 yum install -y nginx php php-fpm二、编写配置文件&#xff0c;连接PHP 一般情况下在安装完 nginx 后…

python-质因数分解(赛氪OJ)

[题目描述] 已知正整数 n 是两个不同的质数的乘积&#xff0c;试求出两者中较大的那个质数。输入格式&#xff1a; 输入一个正整数 n。输出格式&#xff1a; 输出一个正整数 p&#xff0c;即较大的那个质数。样例 #1样例输入 #1 21样例输出 #1 7提示&#xff1a; 1≤n≤2109 来…

无字母数字的绕过方法

php代码 <?phpif(isset($_GET[code])){$code $_GET[code];if(strlen($code)>35){die("Long.");}if(preg_match("/[A-Za-z0-9_$]/",$code)){die("NO.");}eval($code);}else{highlight_file(__FILE__);} 题目的限制&#xff1a; webshell…

书籍分享:【矩阵力量】豆瓣评分高达9.6,看完感叹《矩阵论》又白学了

书籍分享&#xff1a;【矩阵力量】豆瓣评分高达9.6&#xff0c;看完感叹《矩阵论》又白学了 《矩阵力量》简要介绍书籍下载链接 《矩阵力量》简要介绍 《矩阵力量》是姜伟生精心编写的线性代数的深度理解之作&#xff0c;作者将抽象的线性代数概念用通俗易懂的语言和大量生动形…

Windows下,C# 通过FastDDS高效通信

目录 1、安装FastDDS 库2、使用IDL定义自己的数据格式3、生成DLL3.1 托管 &#xff08;Managed&#xff09;模式3.2 非托管 &#xff08;Unmanaged&#xff09;模式 -- 可用于Unity 代码示例 eprosima Fast DDS is a C implementation of the DDS (Data Distribution Service) …

vscode用快捷键一键生成vue模板

项目中有些代码模块是固定的&#xff0c;如下面的代码所示&#xff0c;为了不重复写这些相同的代码&#xff0c;我们可以使用快键键一键生成模板。 流程&#xff1a; 中文&#xff1a;首选项-> 用户代码片段 -> 输入框中输入vue,找到vue.json文件&#xff08;没有vue.j…

Vue-07.生命周期

生命周期&#xff1a; 生命周期&#xff1a;指一个对象从创建到销毁的全过程 生命周期的八个阶段&#xff1a;每触发一个阶段&#xff0c;就会自动执行一个生命周期方法&#xff08;钩子方法&#xff09; 状态 阶段周期 beforeCreated 创…

内部排序(插入、交换、选择)

一、排序的部分基本概念 1. 算法的稳定性 若待排序表中有两个元素 Ri 和 Rj &#xff0c;其对应的关键字相同即 keyi keyj&#xff0c;且在排序前 Ri 在 Rj 的前面&#xff0c;若使用某一排序算法排序后&#xff0c;Ri 仍然在 Rj 的前面&#xff0c;则称这个排序算法是稳定的…

【MySQL】详解数据库约束、聚合查询和联合查询

数据库约束 约束类型 数据库的约束类型主要包括以下几种&#xff1a; 主键约束&#xff08;Primary Key Constraint&#xff09;&#xff1a;确保表中的每一行都有唯一的标识&#xff0c;且不能为NULL。 外键约束&#xff08;Foreign Key Constraint&#xff09;&#xff1a…

5.ADC(模拟信号转数字信号)

理论 3个ADC控制器 转换&#xff1a;单次转换模式、 连续转换模式 转换时间 采样时间 12.5周期 当ADCCLK(时钟) 14MHz&#xff0c;采样时间为1.5周期&#xff0c;TcoNv(转换时间) 1.5 12.5 14 周期 1us 采样精度&#xff1a;12位/16位(212 4096) 实际电压值 (通道采…

Java面试题--JVM大厂篇之破解 JVM 性能瓶颈:实战优化策略大全

目录 引言: 正文: 1. 常见的JVM性能问题 频繁的GC导致应用暂停 内存泄漏导致的内存不足 线程争用导致的CPU利用率过高 类加载问题导致的启动时间过长 2. 优化策略大全 2.1 代码层面的优化 2.1.1 避免不必要的对象创建 2.1.2 优化数据结构的选择 2.1.3 使用并发工具…

Python爬虫:下载4K壁纸

&#x1f381;&#x1f381;创作不易&#xff0c;关注作者不迷路&#x1f380;&#x1f380; 目录 &#x1f338;完整代码 &#x1f338;分析 &#x1f381;基本思路 &#x1f381;需要的库 &#x1f381;提取图片的链接和标题 &#x1f453;寻找Cookie和User-Agent &…