揭开链表的真面目
链表是一种常见的数据结构,链表是由一连串的结点组成,这个节点就是链结点,每个链结点都由数据域和指针域两部分组成。
使用链表结构可以克服数组结构需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
链表比较好的一种理解是:将链表看成一个火车,每个车厢之间都是相互连接的,只要找到火车头,就可以找到具体的车身。链表也是,我们只关心它的头。
一 单向链表
1.1 单向链表原理图
单向链表的一个链结点包含数据域和下一个链结点的指针。头结点也包含数据域和指针域,但是一般为了方便查找,头节点不写数据,最后一个结点的指针指向空。
1.2 实现单向链表的存储等操作
创建一个链结点的实体类
public class Node {
// 数据域
public long data;
// 指针域
public Node next;
public Node(long value){
this.data = value;
}
}
1.2.1 插入一个节点
在头节点后插入一个结点,第一步需要将新插入的结点指向头结点指向的结点,第二步将头结点指向新插入的结点。插入结点只需要改变一个引用,所以复杂度为O(1)。
public class LinkList {
private Node head;
/**
* 在头节点之后插入一个节点
*/
public void insertFirst(long value){
Node node = new Node(value);
node.next = head;
head = node;
}
}
1.2.2 头结点后删除一个结点
在头结点后删除一个结点,就是让头结点指向这个结点的下一个结点。复杂度也是O(1)。
public Node deleteFirst(){
Node tmp = head;
head = tmp.next;
return tmp;
}
1.2.3 根据数据域查找结点
查找需要比对每个结点的数据,理论上查找一个结点平均需要N/2次,所以复杂度为O(N)。
public Node find(long value){
Node current = head;
while (current.data != value){
if(current.next == null){
return null;
}
current = current.next;
}
return current;
}
1.2.4 根据数据与删除结点
查找需要比对每个结点的数据,理论上删除一个结点平均需要N/2次,所以复杂度为O(N)。
public Node delete(int value){
Node current = head;
// 当前结点的前一个结点
Node pre = head;
while (current.data != value){
if(current.next == null){
return null;
}
pre = current;
current = current.next;
}
if(current == head){
head = head.next;
}else{
pre.next = current.next;
}
return current;
}
二 双端链表
2.1 双端链表原理图
双端链表是在单向链表的基础上,头结点增加了一个尾结点的引用。
2.2 实现双端链表的存储等操作
2.2.1 从头部插入结点
如果链表为空,则设置尾结点就是新添加的结点。复杂度为O(1)。
public class FirstLastLinkList {
private Node first;
private Node last;
/**
* 在头结点之后插入一个节点
*/
public void insertFirst(long value){
Node node = new Node(value);
if(first == null){
last = node;
}
node.next = first;
first = node;
}
}
2.2.2 从尾部插入结点
如果链表为空,则设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加的结点。复杂度为O(1)。
public void insertLast(long value){
Node node = new Node(value);
if(first == null){
first = node;
}else{
last.next = node;
}
last = node;
}
2.2.3 从头部进行删除
判断头结点是否有下一个结点,如果没有则设置尾结点为null,复杂度为O(1)。
public Node deleteFirst(){
Node tmp = first;
if(first.next == null){
last = null;
}
first = tmp.next;
return tmp;
}
三 双向链表
3.1 双向链表原理图
每个结点除了保存对后一个结点的引用外,还保存着对前一个结点的引用。
3.2 实现双向链表的存储等操作
链结点实体类
public class Node {
// 数据域
public long data;
// 后一个结点指针域
public Node next;
// 前一个结点指针域
public Node prev;
public Node(long value){
this.data = value;
}
}
3.2.1 从头部插入结点
如果链表为空,则设置尾结点为新添加的结点,如果不为空,还需要设置头结点的前一个结点为新添加的结点。插入结点只需要改变两个结点的引用,所以复杂度为O(1)。
public class DoubleLinkList {
private Node first;
private Node last;
/**
* 在头结点之后插入一个节点
*/
public void insertFirst(long value){
Node node = new Node(value);
if(first == null){
last = node;
} else{
first.prev = node;
}
node.next = first;
first = node;
}
}
3.2.2 从尾部插入结点
如果链表为空,则设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾结点。插入结点只需要改变1个结点的引用,所以复杂度为O(1)。
public void insertLast(long value){
Node node = new Node(value);
if(first == null){
first = node;
}else{
last.next = node;
node.prev = last;
}
last = node;
}
3.2.3 从头部删除结点
判断头结点是否有下一个结点,如果没有则设置尾结点为null,否则设置头结点的下一个结点的prev为null。复杂度也为O(1)。
public Node deleteFirst(){
Node tmp = first;
if(first.next == null){
last = null;
}else{
first.next.prev = null;
}
first = tmp.next;
return tmp;
}
3.2.4 从尾部删除结点
如果头结点后没有其他结点,则设置头结点为null,否则设置尾结点的前一个结点的next为null,设置尾结点为前一个结点。复杂度为O(1)。
public Node deleteLast(){
Node tmp = last;
if(first.next == null){
first = null;
}else{
last.prev.next = null;
}
last = last.prev;
return last;
}
四 总结
链表包含一个头结点和多个结点,头结点包含一个引用,这个引用通常叫做first,它指向链表的第一个链结点。结点的next为null,则意味着这个结点是尾结点。与数组相比,链表更适合做插入、删除操作,而查找操作的复杂度更高。还有一个优势就是链表不需要初始化内存大小,不会造成内存溢出(数组中插入元素个数超过数组长度)或内存浪费(声明的数组长度比实际放的元素长)。
本文分享自微信公众号 - Java旅途(Javatrip)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
typescript实战总结之实现一个互联网黑白墙
前言 笔者上一篇文章TS核心知识点总结及项目实战案例分析主要写了typescript的用法和核心知识点总结, 这篇文章将通过一个实际的前端案例来教大家如何在项目中使用typescript. 你将收获 如何使用umi快速搭建一个基于React+antd+typescript的前端项目 中后台前端项目的目录和ts文件划分 在React组件中使用typescript 在工具库中使用typescript 互联网黑白墙案例分析 正文 在开始文章之前, 我们先看一下企业黑白墙项目的演示: (注: 本文仅针对项目剖析和学习使用, 不做任何商业用途) 该项目是一个响应式网站, 针对PC端和H5均做了一定的适配, 接下来我们将正对该网站做一次typescript剖析. 由上面的gif可以看出网站的信息结构图大致如下: 接下来进入我们的正文. 1. 使用umi快速搭建一个基于React+antd+typescript的前端项目 umi是一个功能强大且开箱即用的企业级项目脚手架, 这里笔者直接采用umi来创建一个ts项目, 具体方式如下: // 1.创建项目空目录$ mkdir ts-react &...
- 下一篇
kkFileView v2.2.1 发布,文件文档在线预览解决方案
kkfileview 文件在线预览 此项目为文件文档在线预览项目解决方案,项目使用流行的 spring boot 搭建,易上手和部署,部署好后可以独立提供预览服务,使用 http 接口访问,不需要和应用集成,具有跨系统跨语言使用的特性。提供 zip/tar.gz 发行包、自定义配置文件、和启动/停止脚本等,极大方便部署使用,同时官方发布 Docker 镜像,方便容器环境中部署使用。基本支持主流办公文档的在线预览,如 doc,docx,dwg, xls,xlsx,ppt,pptx,pdf,txt,zip,rar,7z,mp3,mp4,flv 图片等等。 项目地址:https://gitee.com/kekingcn/file-online-preview 项目官网:https://kkfileview.keking.cn Docker 镜像:https://hub.docker.com/r/keking/kkfileview 本次 v2.2.1 更新内容: 1. 支持纯文本预览原样格式输出 2. 修复PDF预览出现文字缺失异常,升级pdf.js组件 3. docker镜像底层使用ubun...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Red5直播服务器,属于Java语言的直播服务器
- Windows10,CentOS7,CentOS8安装Nodejs环境
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7,8上快速安装Gitea,搭建Git服务器
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Docker使用Oracle官方镜像安装(12C,18C,19C)