java实现不带哨兵节点的双向链表（二）

概述

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 扩展：如何打印双向链表的形式？ } 扩展

如何实现带头哨兵、尾哨兵的双向链表？ 如何打印双向链表的形式？

最后

好了，如果对你有帮助的话，欢迎点个免费的赞哦。