数据结构之双向链表详解
😽博主CSDN主页：小源_😽
🖋️个人专栏：《数据结构》🖋️
😀努力追逐大佬们的步伐~
1. 前言
上一篇文章中我们重点讲解了无头单向非循环链表的模拟实现，现在我们来讲解LinkedList（无头双向链表实现 ）的模拟实现。
本章重点：
本文着重讲解了LinkedList(无头双向单链表)的实现和LinkedList的使用。
2. LinkedList（无头双向链表）的模拟实现
从上图可以看出，无头双向链表和无头单向非循环链表结构类似，只是在每个节点中加入了前一个节点的地址(用prev存储)，使得每个节点可以访问前一个节点。其中第一个节点的前驱prev为空。
2.1 定义IList接口
无头双向链表的模拟实现要定义的接口和上一篇文章中无头单向非循环链表的模拟实现一样，即：
public interface IList {
//头插法
void addFirst(int data);
//尾插法
void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
boolean contains(int key);
//删除第一次出现关键字为key的节点
void remove(int key);
//删除所有值为key的节点
void removeAllKey(int key);
//得到单链表的长度
int size();
//清空
void clear();
//打印
void display();
}
2.2 重写IList中的方法
定义一个MyLinkedList类来实现IList接口，并且重写IList中的方法
（选中IList,快捷键为Ctrl+O）：
首先需要定义一个内部类作为节点的类，用static修饰，代表只能在当前类中使用。
接着定义一个头节点head，尾节点last。
public class MyLinkedList implements IList{
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
@Override
public void addFirst(int data) {
}
@Override
public void addLast(int data) {
}
@Override
public void addIndex(int index, int data) {
}
@Override
public boolean contains(int key) {
return false;
}
@Override
public void remove(int key) {
}
@Override
public void removeAllKey(int key) {
}
@Override
public int size() {
return 0;
}
@Override
public void clear() {
}
@Override
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.println(cur.next + " ");
cur = cur.next;
}
System.out.println();
}
}
2.3 display（打印方法）
遍历双向链表的方法和遍历单链表相同：我们只需关心next域，而不需要关心prev。
@Override
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}
2.4 size方法
求链表个数/长度
@Override
public int size() {
ListNode cur = head;
//定义一个计数器
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
2.5 contains方法
指的是查找是否包含关键字key是否在单链表当中。这里跟size方法相似，只需遍历链表时判断是否cur.val == key
@Override
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
//判断
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
2.6 addFirst头插法
指的是将插入的节点存放在链表的第一个位置。
1.实例化一个节点
2.改变插入节点的next和prev
3.改变head
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data);
//如果head为空，则head和last都指向node
if (head == null) {
head = node;
last = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
2.7 addLast尾插法
指的是将插入的节点存放在链表的第一个位置。
1.实例化一个节点
2.找到最后一个节点last
3.last.next = node;
node.prev = last;
4.改变last
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
//如果head为空，则head和last都指向node
if (head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
2.8 addIndex任意插法
指的是在任意位置插入一个节点。
1.让cur走index步(单链表的addIndex任意插法为走（index – 1）步)
2.node.next = cur.next;（还是先绑定后面的节点）
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
@Override
public void addIndex(int index, int data) {
int len = size();
//检查index是否合法
if(index len) {
//可以抛出自定义异常
System.out.println("index位置不合法：" + index);
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
//用cur接收前驱
ListNode cur = findIndex(index);
//实例化一个新的节点
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//找到要插入的位置
public ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
2.9 remove方法
指的是删除第一次出现关键字为key的节点。
1.直接让cur走到index位置
2.删除
@Override
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
//删除头节点
if (cur == head) {
head = head.next;
head.prev = null;
} else {
cur.prev.next = cur.next;
//删除最后一个节点
if (cur.next == null) {
last = last.prev;
} else {
cur.next.prev = cur.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
效果图如下：看似很正常，实际上还存在问题 （当节点只有一个时的问题）
如图：第108行代码中，当节点只有一个的情况下，head.next为空,null.prev这一操作会报空指针异常
解决方法如下：
效果图如下：此时正常执行
remove方法的最终代码为：
@Override
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 ！= null的前提下才能执行这行代码
head.prev = null;
}
last = null;
} else {
cur.prev.next = cur.next;
//删除最后一个节点
if (cur.next == null) {
last = last.prev;
} else {
cur.next.prev = cur.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
2.10 removeAllKey方法
指的是删除所有值为key的节点。
和remove方法类似，只需把删除操作的一段代码结束以后，不return ,继续cur = cur.next即可
@Override
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 ！= null的前提下才能执行这行代码
head.prev = null;
}
last = null;
} else {
cur.prev.next = cur.next;
//删除最后一个节点
if (cur.next == null) {
last = last.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
2.11 clear方法
指的是删除链表的所有节点。
1.直接把头节点和尾巴节点置空的方法太粗糙，我们下面学习更细节的写法：
2.遍历链表，把每个节点的 val = null, prev = null, next = null 即可（val = null可以不写，因为没有人指向这个节点的时候，会被系统自动回收）
@Override
public void clear() {
ListNode cur = head;
while (cur != null) {
//用curNext记录cur.next，因为接下来cur.next将会改变为null
// 我们要用curNext来继续遍历链表
ListNode curNext = cur.next;
cur.val = 0;
cur.next = null;
cur.prev = null;
cur = curNext;
}
head = null;
//暴力做法
// head = null;
// last = null;
}
3. LinkedList的使用
3.1 什么是LinkedLList
LinkedList
的底层是双向链表结构
，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，
LinkedList
也实现了
List
接口
【说明】
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
3.2 LinkedList的使用
1.LinkedList的构造
| 方法 | 解释 |
|
LinkedList | 无参构造 |
public LinkedList(Collection c) | 使用其他集合容器中元素构造List |
public static void main(String[] args) { // 构造一个空的LinkedList List list1 = new LinkedList(); List list2 = new java.util.ArrayList(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List list3 = new LinkedList(list2);}2.2. LinkedList的其他常用方法介绍
|
方法 | 解释 |
1. boolean | 尾插 |
2. void | 将 |
3. boolean | 尾插 c 中的元素 |
4. E | 删除 index 位置元素 |
5. boolean | 删除遇到的第一个 |
6. E | 获取下标 |
7. E | 将下标 |
8. void | 清空 |
9. boolean | 判断 |
10. int | 返回第一个 |
11. int | 返回最后i一个 o 所在下标 |
12. List | 截取部分 list |
import java.util.LinkedList;import java.util.List;public class TestLink { public static void main(String[] args) { LinkedList list = new LinkedList(); list.add(1); // 1.add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); //打印链表大小 System.out.println(list.size()); //打印链表 System.out.println(list); // 在起始位置插入0 list.add(0, 0); // 2.add(index, elem): 在index位置插入元素elem System.out.println(list); list.remove(); // 4.remove(): 删除第一个元素，内部调用的是removeFirst() list.removeFirst(); // removeFirst(): 删除第一个元素 list.removeLast(); // removeLast(): 删除最后元素 list.remove(1); // 4.remove(index): 删除index位置的元素 System.out.println(list);// 9.contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false if(!list.contains(1)){ // 2. list.add(0, 1); } //1. list.add(1); System.out.println(list); System.out.println(list.indexOf(1)); // 10.indexOf(elem): 从前往后找到第一个elem的位置 System.out.println(list.lastIndexOf(1)); // 11.lastIndexOf(elem): 从后往前找第一个1的位置 int elem = list.get(0); // 6.get(index): 获取指定位置元素 list.set(0, 100); // 7.set(index, elem): 将index位置的元素设置为elem System.out.println(list); // 12.subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回 List copy = list.subList(0, 3); System.out.println(list); System.out.println(copy); list.clear(); // 8.将list中元素清空 System.out.println(list.size()); }}效果图如下：
3.3 LinkedList的遍历
import java.util.LinkedList;
import java.util.ListIterator;
public class TestLink {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println("======");
// 1.直接打印，因为LinkedList底层实现了List的toString方法
System.out.println(list);
System.out.println("======");
// 2.foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
System.out.println("======");
// 3.for循环
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
System.out.println("======");
// 4.使用迭代器遍历---正向遍历
ListIterator it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
System.out.println("===反向===");
// 5.使用反向迭代器---反向遍历
ListIterator rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}
}
效果图如下：
4. 经常遇到的面试问题
1.ArrayList和LinkedList的区别是什么？/2.顺序表和链表的区别是什么？/3.数组（和顺序表类似）和链表的区别？
（这三个问题其实是一个问题）
答：
如果是经常根据下标进行查找的使用顺序表（ArrayList）
如果经常进行插入和删除操作的可以使用链表（LinkedList）
下图是ArrayList和LinkedList的其他区别：
最后，祝大家天天开心，更上一层楼！关注我🌹，我会持续更新学习分享…🖋️
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/14c8b00bf0.html
相关推荐
-
图像处理：Tiler制作你的专属卡通头像和LOGO(圣诞特别篇)
目录 0 前言 1 安装与贴图 2 算法原理 2.1 计算像素频率 2.2 计算像素相对距离 2.3 计算合适贴图 3 配置功能 4 使用：以圣诞老人为例 推荐内容 0 前言 Ti…
-
全网疯传的前端量子纠缠效果，源码来了！
这两天，很多群里都在疯传一个视频，视频演示了纯前端实现的“量子纠缠”效果，不少前端er表示：“前端白学了”。 原视频如下： 全网疯传的前端量子纠缠效果，源码来了！ 体验地址：3d …
-
【AI选股】如何通过python调用通达信-小达实现AI选股（量化又多了一个选股工具，原文Chrome浏览器请改为Edge浏览器）
文章目录 前言 一、通达信-小达是什么？ 二、使用步骤 1. 引入browser_cookie3库 2. 通达信-小达 AI选股源代码 总结 前言 ChatGPT火遍网络，那么有没…
-
纯HTML+CSS实现可响应式登陆界面
先上效果视频： 演示视频 基本思路： 一：日月切换模块 1. 用阴影画出太阳和月亮 2.用transform: translate； transform: rotate；两个属性实…
-
从零开发短视频电商 Java开发者的AI大模型（LLM）应用开发和设计-LangChain4j
文章目录 简介 示例 1.添加依赖 2.设置OpenAI API 密钥 3.创建模型的实例并开始交互 功能 实践 爬取网页并embedding HuggingFace在线API集成…
-
利用级联选择器实现省市区三级联动【vue + elementUI Plus | uViewUI】
文章目录 准备数据 vue + ElementUI Plus 利用级联选择器实现省市区三级联动 学习记录 具体代码 vue + uViewUI 利用选择器多列联动实现省市区三级联动…
-
Spring Cloud gateway 运行报错：Please set spring.main.web-application-type=reactive or remove spring-boot
昨天在使用 Spring Cloud gateway 运行报错：“Please set spring.main.web-application-type=reactive or r…
-
flex 布局：实现一行固定个数，超出强制换行（流式布局）
一、flex 布局基础知识 flex 布局的知识想必不用多说，一些常用的属性如下： 设置在父容器上的属性：display：flex， align-items, justify-co…
-
数据结构——插入排序与希尔排序
🌇个人主页：_麦麦_ 📚今日名言：喜你成疾，药石无医。——《玫瑰与鹿》 一、前言 在本篇文章，我们将为小伙伴们进行排序概念的基本讲解…
-
【学习笔记】LeetCode SQL刷题（高频50基础版+进阶版）
一、高频SQL50题(基础版) 题目考查类型 题号 查询 1-5 连接 6-14 聚合函数 15-22 排序和分组 23-29 高级查询和连接 30-36 子查询 37-43 高级…
