线性表的链式存储结构————双链表（java）
线性表的链式存储结构————双链表（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);
}
}
由于直接调用的输出格式是列表的格式，所以想直接输出数字，就将其转换为字符串，并遍历循环输出。其他更多的功能大家也可以自己去尝试一下。
结语
本次分享就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区留言，如果给小伙伴们带来了一些收获，请留下你的小赞，你的点赞和关注将会成为博主分享每日学习的动力。
原文地址：https://blog.csdn.net/h091616/article/details/140505199
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！