Java双向链表的操作
作者：萝诗粉 发布时间：2021-07-31 02:54:33
标签：Java,双向,链表,操作
前言
我们之前学的单链表，默认只能从链表的头部遍历到链表的尾部，在实际中应用太少见，太局限；而双向链表，对于该链表中的任意节点，既可以通过该节点向前遍历，也可以通过该节点向后遍历，双向链表在实际工程中应用非常广泛，是使用链表这个结构的首选。
一、认识双向链表
单向链表不仅保存了当前的结点值，还保存了下一个结点的地址
双向链表不仅保存了当前节点的值，还保存了上一个结点的地址和下一个结点的地址
定义一个双向链表的结点类：
结点中既要保存当前节点的值，还要保存此节点的前驱节点的地址和此节点的后继节点的地址
class DoubleNode{
public DoubleNode next;
DoubleNode prev;
int val;
DoubleNode tail;
public DoubleNode() {}
public DoubleNode(int val) {
this.val = val;
}
public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
this.prev = prev;
this.val = val;
this.tail = tail;
}
}
定义一个双向链表类：
既可以从前向后，也可以从后向前，所以在这个类中，即保存一下头结点，也保存一下尾结点的值
public class DoubleLinkedList {
private int size;
private DoubleNode head;
private DoubleNode tail;
}
二、双向链表的增删改查
1.插入
头插
在当前链表的头部插入一个节点，让当前链表的头结点head前驱指向要插入的节点node，然后让node的后继指向head，然后让head = node，让node成为链表的头结点
代码如下：
/**
* 头插
*/
public void addFirst(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
size++;
}
尾插
和头插一样，只不过在链表的尾部插入
代码如下：
public void addLast(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail =node;
}else{
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}
在index位置插入
在索引为index的位置插入值为val的节点：
插入还是要找前驱节点，但双向链表找前驱节点比单向链表找前驱节点要灵活很多，单向链表只能从头走到尾，假如此时有100个节点，要在索引为98的位置插入节点，那么双向链表就可以从尾结点开始找，会方便很多
如何判断从前向后找，还是从后向前找？
1.index < size / 2 – >从前向后找，插入位置在前半部分
2.index > size / 2 – >从后向前找，插入位置在后半部分
代码如下：
/**
* 在index位置插入
* @param index
* @param val
*/
public void add(int index,int val){
DoubleNode cur = new DoubleNode(val);
if (index < 0 || index > size){
System.err.println("add index illegal");
return;
}else{
if (index == 0){addFirst(val);}
else if (index == size){addLast(val);}
else{
DoubleNode prev = node(index-1);
DoubleNode next = prev.next;
cur.next = next;
next.prev = cur;
prev.next = cur;
cur.prev = prev;
}
}
size++;
}
/**
* 根据索引值找到对应的结点
* @param index
* @return
*/
private DoubleNode node(int index){
DoubleNode x = null;
if (index < size/2){
x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
}else{
x = tail;
for (int i = size - 1; i > index ; i--) {
x = x.prev;
}
}
return x;
}
2.修改
代码如下：
/**
* 修改双向链表index位置的结点值为newVal
*/
public int set(int index,int newVal){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("set index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
int oldVal = cur.val;
cur.val = newVal;
return oldVal;
}
3.查询
代码如下：
/**
* 查询index位置的结点值
*/
public int get(int index){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("get index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
return cur.val;
}
4.删除
删除index位置的节点
代码如下：
//删除链表index位置的结点
public void removeIndex(int index){
if (index < 0 || index > size - 1){
System.err.println("remove index illegal");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
/**
* 删除当前双向链表的node结点
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先处理node的前半部分
if (prev == null){
head = successor;
}else{
//前驱不为空的情况
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
头删
调用删除任意位置的节点即可
代码如下：
//头删
public void removeFirst(){
removeIndex(0);
}
尾删
调用删除任意位置的节点即可
代码如下：
//尾删
public void removeLast(){
removeIndex(size - 1);
}
删除第一个值为val的节点
代码如下：
//删除第一个值为val的结点
public void removeValOnce(int val){
if (head == null){
return;
}
for (DoubleNode x = head;x != null;x = x.next){
if (x.val == val){
unlink(x);
break;
}
}
}
/**
* 删除当前双向链表的node结点
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先处理node的前半部分
if (prev == null){
head = successor;
}else{
//前驱不为空的情况
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
删除所有值为val的值
代码如下：
//删除链表中所有值为val的结点
public void removeAllVal(int val){
for (DoubleNode x = head;x != null;){
if (x.val == val){
//暂存一下x的下一个结点
DoubleNode next = x.next;
unlink(x);
x = next;
}else{
//val不是待删除的元素
x = x.next;
}
}
}
/**
* 删除当前双向链表的node结点
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先处理node的前半部分
if (prev == null){
head = successor;
}else{
//前驱不为空的情况
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
来源：https://blog.csdn.net/weixin_57011679/article/details/124820698
0
投稿猜你喜欢
- 我们都知道在一些特殊的场景，我们需采用特殊的编码格式，如：UTF-8,但是系统默认的编码为ISO-8859-1那么我们就需要将编码转换为我们
- private string CheckCidInfo(string cid) &
目录如何快速获取 相册分类一些异常情况的处理Recycleview-CursorAdapter还有必要用LoaderManager吗总结如何- C#函数式程序设计之作用域在C#中，变量的作用域是严格确定的。其本质是所有代码生存在类的方法中、所有变量只生存于声明它们的模块中或者之后的代
- 导语本章根据百度地图API，实现仿钉钉打卡功能。用到了基础地图、覆盖物、定位图层、陀螺仪方法、悬浮信息弹框。百度地图API地址
- 二叉搜索树的定义它是一颗二叉树任一节点的左子树上的所有节点的值一定小于该节点的值任一节点的右子树上的所有节点的值一定大于该节点的值特点： 二
- 主要介绍使用MediaPlayer播放音频的方式。关于MediaPlayer的基础知识，比如状态，可以参考Android MediaPlay
- Maven本地jar引用的实现方法有的时候需要在maven工程项目中引用本地的jar，pom.xml配置如下：<dependency&
- 从何说起前些天和朋友讨论一个问题，他们的应用有几十万会员然后对应有积分，现在想做积分排名的需求，问有没有什么好方案。这个问题也算常见，很多地
- BroadcastReceiver不仅可以接收系统广播，也可接收自定义的广播 1.定义一个广播 * public class My
- 前言想象一下生活中哪些是和线程沾边的？饭店炒菜就是一个很好的例子首先客人要吃菜，前提是厨师要炒好，也就是说，厨师不炒好的话客人是没有饭菜的。
- 本文实例讲述了Android编程应用风格和主题。分享给大家供大家参考，具体如下：当你设计你的程序的时候，你可以用风格和主题来统一格式化各种屏
- 由Lombok的@AllArgsConstructor注解引发的错误需求：在Service实现中写了一个方法调用第三方接口同步数据。 功能代
- 下拉刷新对于一个app来说是必不可少的一个功能，在早期大多数使用的是chrisbanes的PullToRefresh，或是修改自该框架的其他
- Spring @Configuration 和 @Component 区别一句话概括就是 @Configuration 中所有带 @Bean
- 实例如下：package com.bwsk.modules.weixin.util;import java.util.Random;/**
- 1.其中包括下载JDBC FRO Microsft SQL_Server2000的驱动程序（在微软官方网站下的，是sp3版的，这里就不写具体
- 源码地址：https://gitee.com/fighter3/eshop-project.git持续更新中……大家好，我是三分恶。这一节我
- 前言：在我们使用C# WinForm中，我们有时候是需要或者自己本机的IP地址进行处理，今天我们学习一下如何使用C# Winform获取主机
- 写在自定义之前我们也许会遇到，自定义控件的触屏事件处理，先来了解一下View类中的，onTouch事件和onTouchEvent事件。1、b
