13. Python 程序从双向链表中删除重复元素。

17 Mar 2025 | 4 分钟阅读

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

Python program to remove duplicate elements from a Doubly Linked List

删除重复元素后的列表

在上面的列表中，节点 2 重复了三次，节点 3 重复了两次。 Current 指向 head，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 以存储重复节点。
由于 temp 指向 index（这是一个重复节点），因此将 temp 设置为 null。

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

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

程序

#Represent a node of doubly linked list  
class Node:  
    def __init__(self,data):  
        self.data = data;  
        self.previous = None;  
        self.next = None;  
          
class RemoveDuplicate:  
    #Represent the head and tail of the doubly linked list  
    def __init__(self):  
        self.head = None;  
        self.tail = None;  
          
    #addNode() will add a node to the list  
    def addNode(self, data):  
        #Create a new node  
        newNode = Node(data);  
          
        #If list is empty  
        if(self.head == None):  
            #Both head and tail will point to newNode  
            self.head = self.tail = newNode;  
            #head's previous will point to None  
            self.head.previous = None;  
            #tail's next will point to None, as it is the last node of the list  
            self.tail.next = None;  
        else:  
            #newNode will be added after tail such that tail's next will point to newNode  
            self.tail.next = newNode;  
            #newNode's previous will point to tail  
            newNode.previous = self.tail;  
            #newNode will become new tail  
            self.tail = newNode;  
            #As it is last node, tail's next will point to None  
            self.tail.next = None;  
              
    #removeDuplicateNode() will remove duplicate nodes from the list  
    def removeDuplicateNode(self):  
          
        #Checks whether list is empty  
        if(self.head == None):  
            return;  
        else:  
            #Initially, current will point to head node  
            current = self.head;  
            while(current != None):  
                #index will point to node next to current  
                index = current.next  
                while(index != None):  
                    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 != None):  
                            index.next.previous = index.previous;  
                        #Delete duplicate node by making temp to None  
                        temp = None;  
                    index = index.next;  
                current = current.next;  
                          
    #display() will print out the nodes of the list  
    def display(self):  
        #Node current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
            return;  
        while(current != None):  
            #Prints each node by incrementing pointer.  
            print(current.data),  
            current = current.next;  
        print();  
          
dList = 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);  
   
print("Originals list: ");  
dList.display();  
   
#Removes duplicate nodes  
dList.removeDuplicateNode();  
   
print("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

下一个主题Python 程序

← 上一个下一个 →

13. Python 程序从双向链表中删除重复元素。

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

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

Python 程序

13. Python 程序从双向链表中删除重复元素。

算法

程序

相关帖子

Python 程序打印数组中的元素数量

Python 程序

Python 程序确定给定的数字是否为 Harshad Number

Python 程序对循环链表进行排序

Python 程序在循环链表中间插入一个新节点

Python 程序显示日历

Python 程序在循环链表末尾插入一个新节点

Python 程序从双向链表中删除一个新节点

Python 程序生成随机数

Python 函数程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器