概述
todo 扩展：实现链表节点的删除（根据索引删除节点、删除第一个元素）、添加的元素为数组最后一个元素（addLast）等
实现上一篇博客中提到的
- 根据索引删除节点。
- 删除第一个元素。
- 添加的元素为数组最后一个元素。
根据索引删除节点
实现
/**
* 根据遍历过程中的索引删除节点 思路：
* 核心思路是 维护待删除节点的上一个节点和下一个节点的next和pre的指向
* <p>
* 查找目标索引上一个节点preNode，preNode的next即目标节点targetNode，targetNode的next即nextNode
* preNode的next直接指向nextNode，nextNode的pre直接指向preNode
* targetNode的next设置为null，pre也设置为null 即可
*
* @param index
*/
public void removeByIndex(int index) {
Node preNode = getNodeByIndex(index - 1);
if (preNode == null) {
throw new RuntimeException(String.format("索引%s不正确", index));
}
Node targetNode = preNode.next;
Node nextNode = targetNode.next;
preNode.next = nextNode;
// 由于是不带尾哨兵的双向链表 所以nextNode可能为空
// 如 链表为 3->2->1 但要删除索引为2的元素 此时 nextNode为null
if (nextNode != null) {
nextNode.pre = preNode;
}
targetNode.next = null;
targetNode.pre = null;
}
测试用例
public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.print();
/**
* 输出为 list:3->1
*/
// list.removeByIndex(1);
// list.print();
/**
* 输出为 list:2->1
*/
// list.removeByIndex(0);
// list.print();
/**
* 输出为 list:3->2
*/
list.removeByIndex(2);
list.print();
}
测试用例输出
删除第一个元素
实现
/**
* 删除第一个元素
*/
public void removeFirst(){
// 调用removeByIndex 传index为0即可
removeByIndex(0);
}
测试用例
public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.print();
// 测试 删除第一个元素
list.removeFirst();
list.print();
}
测试用例输出
添加的元素为数组最后一个元素
实现
/**
* 添加的元素为最后一个元素 思路：
* 找到链表当前的最后一个元素 让这个元素的next指向欲添加的元素
* 欲添加的元素的pre指向原来的lastNode
* 由于本链表实现不是一个带尾哨兵的双向链表 所以需要将欲添加的元素的next设置为null（欲添加的元素是最后一个元素）
* @param value 欲添加元素的值
*/
public void addLast(int value){
Node lastNode = getLastNode();
lastNode.next=new Node(value,lastNode,null);
}
测试用例
public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.print();
// 测试 添加的元素为最后一个元素
list.addLast(100);
list.print(); // 输出为 list:3->2->1->100
}
测试用例输出
完整代码
package com.lovehena.datastructure;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;
/*
* 不带哨兵节点的双向链表：
* 链表中每个元素都是一个节点。每个节点的属性有当前节点的值、上一个节点的地址（变量引用）pre、下一个节点的地址next
* 含有一个头节点。初始时，头节点指向的元素为null。
* 当往链表中某个索引处添加节点时，思路：
* 先找到目标索引的上一个节点preNode，记录当前preNode的next的值nextNode。
* 构建新节点，并将新节点的pre设置为preNode，next设置为nextNode
* 再将preNode的next值设置为新节点
* nextNode的pre值设置为新节点
* 比较抽象 可以看图
* */
@Slf4j
public class DoubleLinkedList {
// 初始化头节点 头节点的value值无所谓
private Node head = new Node(999, null, null);
// 定义节点类
@Data
@AllArgsConstructor
@NoArgsConstructor
private static class Node { // 该类的对象中无需访问外部类DoubleLinkedList对象的任何成员 所以将Node类设置为static的
int value;
Node pre; // 上一个节点
Node next; // 下一个节点
}
/**
* 往索引为0处添加一个元素
*
* @param value
*/
public void addFirst(int value) {
// 调用insert方法即可
insert(0, value);
}
/**
* 添加的元素为最后一个元素 思路：
* 找到链表当前的最后一个元素 让这个元素的next指向欲添加的元素
* 欲添加的元素的pre指向原来的lastNode
* 由于本链表实现不是一个带尾哨兵的双向链表 所以需要将欲添加的元素的next设置为null（欲添加的元素是最后一个元素）
* @param value 欲添加元素的值
*/
public void addLast(int value){
Node lastNode = getLastNode();
lastNode.next=new Node(value,lastNode,null);
}
/**
* 实现往链表中插入一个元素 核心：维护各个节点的指向
*
* @param index 目标索引 索引是便利过程中得到的索引 链表的实现中不在链表的节点发生增删时维护索引（因为实现较为繁琐）
* @param value 待插入元素的值
*/
public void insert(int index, int value) {
// 目标索引处上一节点
Node preNode = getNodeByIndex(index - 1);
// 目标索引原节点
Node next = preNode.next;
// 构建新节点 新节点的next指向目标索引原节点 pre指向目标索引处上一节点
Node inserted = new Node(value, preNode, next);
// 目标索引处上一节点的next指向新节点
preNode.next = inserted;
if (next != null) {
// 目标索引原节点的pre指向新节点
next.pre = inserted;
}
}
/**
* 根据索引获取节点
*
* @param index
* @return
*/
private Node getNodeByIndex(int index) {
Node temp = head;
int i = -1; // 头节点的索引为-1 第一个节点的索引为0
while (temp != null) {
if (index == i) {
break;
}
temp = temp.next;
i++;
}
return temp;
}
/**
* 获取最后一个节点 由于这是一个不包含尾节点（哨兵节点）的链表 所以需单独实现
*
* @return
*/
private Node getLastNode() {
Node temp = head.next;
Node lastNode = temp;
while (temp != null) {
lastNode = temp;
temp = temp.next;
}
return lastNode;
}
/**
* 删除第一个元素
*/
public void removeFirst(){
// 调用removeByIndex 传index为0即可
removeByIndex(0);
}
/**
* 根据遍历过程中的索引删除节点 思路：
* 核心思路是 维护待删除节点的上一个节点和下一个节点的next和pre的指向
* <p>
* 查找目标索引上一个节点preNode，preNode的next即目标节点targetNode，targetNode的next即nextNode
* preNode的next直接指向nextNode，nextNode的pre直接指向preNode
* targetNode的next设置为null，pre也设置为null 即可
*
* @param index
*/
public void removeByIndex(int index) {
Node preNode = getNodeByIndex(index - 1);
if (preNode == null) {
throw new RuntimeException(String.format("索引%s不正确", index));
}
Node targetNode = preNode.next;
Node nextNode = targetNode.next;
preNode.next = nextNode;
// 由于是不带尾哨兵的双向链表 所以nextNode可能为空
// 如 链表为 3->2->1 但要删除索引为2的元素 此时 nextNode为null
if (nextNode != null) {
nextNode.pre = preNode;
}
targetNode.next = null;
targetNode.pre = null;
}
/**
* 遍历打印链表 如3->2->1
*/
public void print() {
if (head.next == null) { // 只有头节点
log.info("双向链表为空");
return;
}
StringBuilder sb = new StringBuilder();
// 从第一个节点开始遍历 不打印头节点的值 直到最后一个元素（包含最后一个元素）
Node temp = head.next;
while (temp != null) {
int value = temp.value;
if (temp.next == null) { // 最后一个节点
sb.append(value);
} else {
sb.append(value).append("->");
}
temp = temp.next;
}
log.info("list:{}", sb.toString());
}
public void reversePrint() {
if (head.next == null) { // 只有头节点
log.info("双向链表为空");
return;
}
StringBuilder sb = new StringBuilder();
Node temp = head.next;
while (temp != null) {
int value = temp.value;
if (temp.next == null) { // 最后一个节点
sb.append(value);
} else {
sb.append(value).append("<-");
}
temp = temp.next;
}
log.info("list:{}", sb.toString());
}
//todo 扩展：如何实现带头哨兵、尾哨兵的双向链表？
//todo 扩展：如何打印双向链表的形式？
}
扩展
如何实现带头哨兵、尾哨兵的双向链表？
如何打印双向链表的形式？
最后
好了，如果对你有帮助的话，欢迎点个免费的赞哦。
