-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathremove_dups_hash.py
146 lines (106 loc) · 3.04 KB
/
remove_dups_hash.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
138
139
140
141
142
143
# Python3 implementation of algorithm to remove duplicates
# from an unsorted doubly linked list. This approach is
# obviously more efficent. The doubly linked list is
# traversed from head to tail. For every newly encountered
# element, check whether it is in the hash table. If yes,
# it is removed. Otherwise we put it in the hash table.
# Time complexity is O(n) and space O(n).
# a node of the doubly linked list
class Node:
def __init__(self):
self.data = 0
self.next = None
self.prev = None
# 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 None
# 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 doubly linked list is empty
if ((head_ref) == None):
return None
# unordered_set 'us' implemented as hash table
us = set()
current = head_ref
next = None
# traverse up to the end of the list
while (current != None):
# if current data is seen before
if ((current.data) in us):
# store pointer to the node next to
# 'current' node
next = current.next
# delete the node pointed to by 'current'
head_ref = deleteNode(head_ref, current)
# update 'current'
current = next
else:
# insert the current data in 'us'
us.add(current.data)
# move to the next node
current = current.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)