在 Java 中插入双向链表节点

10 Sept 2024 | 4 分钟阅读

双向链表是一种数据结构，其中每个节点包含两个引用，一个指向前一个节点，另一个指向后一个节点。这使得可以在两个方向上进行高效的遍历。在双向链表中插入节点涉及更新相邻节点的引用以保持正确的顺序。在本文中，我们将探讨如何在 Java 中在双向链表中插入节点。

让我们从定义双向链表中节点的结构开始

Class Node {
    Int data;
    Node prev;
    Node next;
    public Node(int data) {
        This.data = data;
        This.prev = null;
        This.next = null;
    }
}

在这里，每个节点包含一个整数值数据，以及指向前一个节点和后一个节点的引用（prev 和 next）。

要在双向链表中插入新节点，我们需要考虑三种情况：

在列表开头插入。
在列表末尾插入。
在列表中的特定位置插入。

在列表开头插入

要将节点插入开头，我们需要更新新节点的 next 引用，使其指向当前的第一个节点，并更新当前第一个节点的 prev 引用，使其指向新节点。此外，我们需要将新节点的 prev 引用更新为 null，因为这将是新的第一个节点。

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    If (head == null) {
        Head = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
}

在列表末尾插入

要将节点插入末尾，我们需要遍历列表直到到达最后一个节点。然后，我们更新当前最后一个节点的 next 引用，使其指向新节点，并更新新节点的 prev 引用，使其指向当前最后一个节点。最后，我们将新节点的 next 引用更新为 null，因为它将是新的最后一个节点。

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    If (head == null) {
        Head = newNode;
    } else {
        Node current = head;
        While (current.next != null) {
            Current = current.next;
        }
        Current.next = newNode;
        newNode.prev = current;
    }
}

在列表中的特定位置插入

要在特定位置插入节点，我们需要遍历列表直到到达所需位置。然后，我们更新相邻节点的引用以包含新节点。具体来说，我们将前一个节点的 next 引用更新为指向新节点，将新节点的 prev 引用更新为指向前一个节点，将新节点的 next 引用更新为指向后一个节点，并将后一个节点的 prev 引用更新为指向新节点。

public void insertAtPosition(int data, int position) {
    Node newNode = new Node(data);
    If (position == 1) {
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        Head = newNode;
    } else {
        Node current = head;
        Int currentPosition = 1;
        While (currentPosition < position - 1 && current != null) {
            Current = current.next;
            currentPosition++;
        }
        If (current != null) {
            newNode.next = current.next;
            newNode.prev = current;
            if (current.next != null) {
                current.next.prev = newNode;
            }
            Current.next = newNode;
        } else {
            System.out.println("Invalid position");
        }
    }
}

InsertNodeExample.java

class Node {
    int data;
    Node prev;
    Node next;
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}
class DoublyLinkedList {
    Node head;
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            }
            head = newNode;
        } else {
            Node current = head;
            int currentPosition = 1;
            while (currentPosition < position - 1 && current != null) {
                current = current.next;
                currentPosition++;
            }
            if (current != null) {
                newNode.next = current.next;
                newNode.prev = current;
                if (current.next != null) {
                    current.next.prev = newNode;
                }
                current.next = newNode;
            } else {
                System.out.println("Invalid position");
            }
        }
    }
    public void display() {
        Node current = head;
        System.out.print("Doubly Linked List: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}
public class InsertNodeExample {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        // Inserting nodes
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.display(); // Output: Doubly Linked List: 10 20 30
        list.insertAtBeginning(5);
        list.display(); // Output: Doubly Linked List: 5 10 20 30
        list.insertAtPosition(15, 2);
        list.display(); // Output: Doubly Linked List: 5 15 10 20 30
    }
}

输出

Doubly Linked List: 10 20 30
Doubly Linked List: 5 10 20 30
Doubly Linked List: 5 15 10 20 30

通过这三种插入方法，您可以轻松地在 Java 的双向链表中添加新节点。请记住处理特殊情况，例如空列表或无效位置。

总之，双向链表是一种多功能的数据结构，允许在两个方向上进行高效的插入和遍历。通过了解如何在列表中的不同位置插入节点，您可以在 Java 程序中有效地利用双向链表。

下一主题Java 9 不可变集合

← 上一个下一个 →

在 Java 中插入双向链表节点

在列表开头插入

在列表末尾插入

在列表中的特定位置插入

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

在 Java 中插入双向链表节点

在列表开头插入

在列表末尾插入

在列表中的特定位置插入

相关帖子

How to Set CLASSPATH in Java

Java 中的 Eratosthenes 筛法算法

Java 中的下界

Java 中的 Atomic Boolean

Java 中 System.out.println() 和 System.err.println() 的区别

Java 中查找标记索引的最大数量

Java 中的图像处理 - 亮度增强

为什么 Java 不是纯粹的面向对象语言

Java 中的歧义

What is an anagram in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器