线性表的链式存储结构————双链表（java）

嗨！收到一张超级美丽的风景图，愿你每天都能顺心！

双链表

在双链表中，由于每个结点既包含一个指向后续结点又包含一个指向前驱结点，所以当访问过一个结点后既可以向后访问每一个结点，也可以一次向前访问每一个结点。因此与单链表相比，在双链表中访问一个结点的前后结点更方便。

双链表的创建

    private Node head;private Node tail;private static class Node {int data;Node next;Node prev;public Node(int data) {this.data = data;this.next = null;this.prev = null;}}

• private Node head;：这是一个私有成员变量，表示链表的头节点。头节点是链表中的第一个节点。
• private Node tail;：这是一个私有成员变量，表示链表的尾节点。尾节点是链表中的最后一个节点。
• private int size;：这是一个私有成员变量，表示链表中节点的数量。
• int data;：存储节点中的数据。
• Node next;：指向链表中下一个节点的引用。如果当前节点是链表的最后一个节点，则此引用为null。
• Node prev;：指向链表中前一个节点的引用。如果当前节点是链表的第一个节点，则此引用为null。

Node类的构造函数接受一个整数参数data，并将其赋值给节点的成员变量data。同时，它将next和prev初始化为null，表示这个节点目前没有连接到任何其他节点。

插入数据元素

头插法

• 插入数据首先要判断链表是否为空。
• 如果是空链表头结点=插入的结点=尾结点。
• 不为空将则将插入节点next指向头结点
• 调整首结点的前驱为新结点
• 将新结点设置为首结点
• 链表长度+1

    public void insertHead(int data){Node newNode = new Node(data);if (head != null) {head.prev = newNode;newNode.next = head;}head = newNode;}

尾插法

47a11.png#pic_center)

• 插入数据首先要判断链表是否为空。
• 如果是空链表头结点=插入的结点=尾结点。
• 不为空将则将插入节点prev指向尾结点
• 调整尾结点的后继为新结点
• 将新结点设置为尾结点
• 链表长度+1

public void insertTail(int data){Node newNode = new Node(data);if(head == null){head = newNode;}else {tail.next = newNode;newNode.prev = tail;}tail = newNode;}

求链表的长度

要计算双链表的长度，可以遍历整个链表并计数节点的数量。

    public int length(){int size = 0;Node current = head;while (current != null){size++;current = current.next;}return size;}public void len(){int size = length();System.out.println(size);}

输出双链表

    public void print(){Node current = head;while (current != null){System.out.print(current.data + " ");current = current.next;}System.out.println();}

删除双链表中的指定元素

e.png#pic_center)

• 定义一个名为delete的公共方法，接收一个整数类型的参数data，表示要删除的节点的数据值。
  初始化一个名为current的变量，将其设置为链表的头节点（head）。
• 使用一个while循环遍历链表，直到current变为null（即到达链表尾部）。
• 在循环内部，检查当前节点的数据值是否等于要删除的数据值（current.data == data）。
• 如果找到了匹配的节点，执行以下操作： a. 如果当前节点不是头节点（即current.prev != null），则将当前节点的前一个节点的next指针指向当前节点的下一个节点（current.prev.next = current.next）。 b. 如果当前节点是头节点（即current.prev == null），则将链表的头节点更新为当前节点的下一个节点（head = current.next）。 c. 如果当前节点不是尾节点（即current.next != null），则将当前节点的下一个节点的prev指针指向当前节点的前一个节点（current.next.prev = current.prev）。
• 完成删除操作后，直接返回，不再继续遍历链表。
  如果遍历完整个链表都没有找到匹配的节点，那么函数什么也不做，自然结束。

    public void delete(int data){Node current = head;while (current != null){if(current.data == data){if(current.prev != null){current.prev.next = current.next;}else {head = current.next;}if(current.next != null){current.next.prev = current.prev;}return;}current = current.next;}}

总代码

public class Dnode {private Node head;private Node tail;private static class Node{int data;Node next;Node prev;public Node(int data){this.data = data;this.next = null;this.prev = null;}}//尾插法public void insertTail(int data){Node newNode = new Node(data);if(head == null){head = newNode;}else {tail.next = newNode;newNode.prev = tail;}tail = newNode;}//长度public int length(){int size = 0;Node current = head;while (current != null){size++;current = current.next;}return size;}public void len(){int size = length();System.out.println(size);}public void print(){Node current = head;while (current != null){System.out.print(current.data + " ");current = current.next;}System.out.println();}//删除指定元素public void delete(int data){Node current = head;while (current != null){if(current.data == data){if(current.prev != null){current.prev.next = current.next;}else {head = current.next;}if(current.next != null){current.next.prev = current.prev;}return;}current = current.next;}}public static void main(String[] args) {Dnode list = new Dnode();list.insertTail(1);list.insertTail(2);list.insertTail(3);list.insertTail(4);list.print();list.len();list.delete(2);list.print();}
}

运行效果

用Java内部类实现双链表

我们除了自己手写双链表外，Java还提供了一个类来帮助我们快速实现双链表(LinkedList)

API网址
https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedList.html

我们直接调用我们需要的方法即可。

import java.util.LinkedList;public class Dnode {public static void main(String[] args) {// 创建一个空的双链表LinkedList<Integer> Dnode = new LinkedList<>();Dnode.addLast(1);Dnode.addLast(2);Dnode.addLast(3);Dnode.addLast(4);Dnode.addLast(5);StringBuilder output = new StringBuilder();for(int value:Dnode){output.append(value).append(" ");}System.out.print(output);}
}

由于直接调用的输出格式是列表的格式，所以想直接输出数字，就将其转换为字符串，并遍历循环输出。其他更多的功能大家也可以自己去尝试一下。

结语

本次分享就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区留言，如果给小伙伴们带来了一些收获，请留下你的小赞，你的点赞和关注将会成为博主分享每日学习的动力。