Java 从双向链表中删除重复元素的程序

17 Mar 2025 | 4 分钟阅读

在此程序中，我们将创建一个双向链表，并通过遍历链表来删除重复元素（如果存在）。

原始列表

Java program to remove duplicate elements from a Doubly Linked List

删除重复元素后的列表

在上面的列表中，节点 2 重复了三次，节点 3 重复了两次。Current 将指向头节点，index 将指向 current 的下一个节点。遍历列表，直到找到重复项，即 current 的数据等于 index 的数据。在上面的示例中，第一个重复项将在位置 4 找到。将 index 分配给另一个节点 temp。将 index 的前一个节点与 index 的下一个节点连接起来。删除指向重复节点的 temp。此过程将继续，直到所有重复项都被删除。

算法

定义一个 Node 类，它表示列表中的一个节点。它将有三个属性：数据、previous 指向前一个节点，以及 next 指向下一个节点。
定义另一个用于创建双向链表的类，它有两个节点：头节点和尾节点。最初，头节点和尾节点将指向 null。
addNode() 将向列表中添加节点。
- 它首先检查头节点是否为 null，然后将节点作为头节点插入。
- 头节点和尾节点都将指向新添加的节点。
- 头节点的前一个指针将指向 null，尾节点的下一个指针将指向 null。
- 如果头节点不为 null，则新节点将插入到列表的末尾，使得新节点的前一个指针将指向尾节点。
- 新节点将成为新的尾节点。尾节点的下一个指针将指向 null。

a. removeDuplicateNode() 将从列表中删除重复节点。

定义一个新节点 current，它最初将指向头节点。
节点 index 将始终指向 current 的下一个节点。
循环遍历列表，直到 current 指向 null。
检查 current 的数据是否等于 index 的数据，这意味着 index 是 current 的重复项。
节点 temp 将指向 index 以存储重复节点。
index 的前一个节点将指向 index 的下一个节点。
由于 temp 指向 index（这是一个重复节点），因此将 temp 设置为 null。

a. display() 将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 指向 null。
在每次迭代中，current 将指向列表中的下一个节点。

程序

public class RemoveDuplicate {
    //Represent a node of the doubly linked list
    class Node{
        int data;
        Node previous;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }
    //Represent the head and tail of the doubly linked list
    Node head, tail = null;

    //addNode() will add a node to the list
    public void addNode(int data) {
        //Create a new node
        Node newNode = new Node(data);

        //If list is empty
        if(head == null) {
            //Both head and tail will point to newNode
            head = tail = newNode;
            //head's previous will point to null
            head.previous = null;
            //tail's next will point to null, as it is the last node of the list
            tail.next = null;
        }
        else {
            //newNode will be added after tail such that tail's next will point to newNode
            tail.next = newNode;
            //newNode's previous will point to tail
            newNode.previous = tail;
            //newNode will become new tail
            tail = newNode;
            //As it is last node, tail's next will point to null
            tail.next = null;
        }
    }
    //removeDuplicateNode() will remove duplicate nodes from the list
    public void removeDuplicateNode() {
        //Node current will point to head
        Node current, index, temp;

        //Checks whether list is empty
        if(head == null) {
            return;
        }
        else {
            //Initially, current will point to head node
            for(current = head; current != null; current = current.next) {
                //index will point to node next to current
                for(index = current.next; index != null; index = index.next) {
                    if(current.data == index.data) {
                        //Store the duplicate node in temp
                        temp = index;
                        //index's previous node will point to node next to index thus, removes the duplicate node
                        index.previous.next = index.next;
                        if(index.next != null)
                            index.next.previous = index.previous;
                        //Delete duplicate node by making temp to null
                        temp = null;
                    }
                }
            }
        }
    }

    //display() will print out the nodes of the list
    public void display() {
        //Node current will point to head
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
            return;
        }
        while(current != null) {
            //Prints each node by incrementing the pointer.

            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        RemoveDuplicate dList = new RemoveDuplicate();
        //Add nodes to the list
        dList.addNode(1);
        dList.addNode(2);
        dList.addNode(3);
        dList.addNode(2);
        dList.addNode(2);
        dList.addNode(4);
        dList.addNode(5);
        dList.addNode(3);

        System.out.println("Originals list: ");
        dList.display();

        //Removes duplicate nodes
        dList.removeDuplicateNode();

        System.out.println("List after removing duplicates: ");
        dList.display();
    }
}

输出

Originals list: 
1 2 3 2 2 4 5 3 
List after removing duplicates: 
1 2 3 4 5

下一个主题Java 程序

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 程序

Java 从双向链表中删除重复元素的程序

算法

程序

相关帖子

Java 中数组中的多数元素

查找数组中第二大数字的 Java 程序

计算二叉树奇数层和偶数层节点和之差的 Java 程序

Java 山峰索引问题

在控制台上打印以下图案的 Java 程序 11

Java 在循环链表开头插入新节点的程序

Java 中的糖果分配问题

Java 在单链表开头插入新节点的程序

Java 从循环链表开头删除节点的程序

如何在 Java 中将字符串转换为日期

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器