Java双向链表的增删改查怎么实现
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--;
}登录后复制
以上是Java双向链表的增删改查怎么实现的详细内容。更多信息请关注PHP中文网其他相关文章！
本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
2 周前
By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：如何解锁Myrise中的所有内容
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
热门话题
突破或从Java 8流返回？
Feb 07, 2025 pm 12:09 PM
Java 8引入了Stream API，提供了一种强大且表达力丰富的处理数据集合的方式。然而，使用Stream时，一个常见问题是：如何从forEach操作中中断或返回？ 传统循环允许提前中断或返回，但Stream的forEach方法并不直接支持这种方式。本文将解释原因，并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读： Java Stream API改进 理解Stream forEach forEach方法是一个终端操作，它对Stream中的每个元素执行一个操作。它的设计意图是处
