-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathremove_dups.py
139 lines (105 loc) · 2.97 KB
/
remove_dups.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# Python implementation of algorithm to remove duplicates
# from an unsorted doubly linked list. Here the outer loop
# is used to pick the elements one by one and the inner
# loop compares the picked element with the rest of the
# elements. Time complexity: O(n^2) and auxiliary space
# 0(1)
# Node of a linked list
class Node:
def __init__(self, data = None, next = None):
self.next = next
self.data = data
# Function to delete a node in a Doubly Linked List.
# head_ref -. pointer to head node pointer.
# del -. pointer to node to be deleted.
def deleteNode(head_ref,del_):
# base case
if (head_ref == None or del_ == None):
return head_ref
# If node to be deleted is head node
if (head_ref == del_):
head_ref = del_.next
# Change next only if node to be deleted
# is NOT the last node
if (del_.next != None):
del_.next.prev = del_.prev
# Change prev only if node to be deleted
# is NOT the first node
if (del_.prev != None):
del_.prev.next = del_.next
return head_ref
# function to remove duplicates from
# an unsorted doubly linked list
def removeDuplicates( head_ref):
# if DLL is empty or if it contains only
# a single node
if ((head_ref) == None or (head_ref).next == None):
return head_ref
ptr1 = head_ref
ptr2 = None
# pick elements one by one
while(ptr1 != None) :
ptr2 = ptr1.next
# Compare the picked element with the
# rest of the elements
while (ptr2 != None):
# if duplicate, then delete it
if (ptr1.data == ptr2.data):
# store pointer to the node next to 'ptr2'
next = ptr2.next
# delete node pointed to by 'ptr2'
head_ref = deleteNode(head_ref, ptr2)
# update 'ptr2'
ptr2 = next
# else simply move to the next node
else:
ptr2 = ptr2.next
ptr1 = ptr1.next
return head_ref
# Function to insert a node at the beginning
# of the Doubly Linked List
def push( head_ref, new_data):
# allocate node
new_node = Node()
# put in the data
new_node.data = new_data
# since we are adding at the beginning,
# prev is always None
new_node.prev = None
# link the old list of the new node
new_node.next = (head_ref)
# change prev of head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node
# move the head to point to the new node
(head_ref) = new_node
return head_ref
# Function to print nodes in a
# given doubly linked list
def printList( head):
# if list is empty
if (head == None):
print("Doubly Linked list empty")
while (head != None):
print( head.data ,end= " ")
head = head.next
# Driver Code
head = None
# Create the doubly linked list:
# 8<.4<.4<.6<.4<.8<.4<.10<.12<.12
head = push(head, 12)
head = push(head, 12)
head = push(head, 10)
head = push(head, 4)
head = push(head, 8)
head = push(head, 4)
head = push(head, 6)
head = push(head, 4)
head = push(head, 4)
head = push(head, 8)
print("Original Doubly linked list:")
printList(head)
# remove duplicate nodes */
head=removeDuplicates(head)
print("\nDoubly linked list after removing duplicates:")
printList(head)