This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Loop through each node
Complexity:
Complexity:
Note:
%run ../linked_list/linked_list.py
class MyLinkedList(LinkedList):
def remove_dupes(self):
if self.head is None:
return
node = self.head
seen_data = set()
while node is not None:
if node.data not in seen_data:
seen_data.add(node.data)
prev = node
node = node.next
else:
prev.next = node.next
node = node.next
def remove_dupes_single_pointer(self):
if self.head is None:
return
node = self.head
seen_data = set({node.data})
while node.next is not None:
if node.next.data in seen_data:
node.next = node.next.next
else:
seen_data.add(node.next.data)
node = node.next
def remove_dupes_in_place(self):
curr = self.head
while curr is not None:
runner = curr
while runner.next is not None:
if runner.next.data == curr.data:
runner.next = runner.next.next
else:
runner = runner.next
curr = curr.next
%%writefile test_remove_duplicates.py
import unittest
class TestRemoveDupes(unittest.TestCase):
def test_remove_dupes(self, linked_list):
print('Test: Empty list')
linked_list.remove_dupes()
self.assertEqual(linked_list.get_all_data(), [])
print('Test: One element list')
linked_list.insert_to_front(2)
linked_list.remove_dupes()
self.assertEqual(linked_list.get_all_data(), [2])
print('Test: General case, duplicates')
linked_list.insert_to_front(1)
linked_list.insert_to_front(1)
linked_list.insert_to_front(3)
linked_list.insert_to_front(2)
linked_list.insert_to_front(3)
linked_list.insert_to_front(1)
linked_list.insert_to_front(1)
linked_list.remove_dupes()
self.assertEqual(linked_list.get_all_data(), [1, 3, 2])
print('Test: General case, no duplicates')
linked_list.remove_dupes()
self.assertEqual(linked_list.get_all_data(), [1, 3, 2])
print('Success: test_remove_dupes\n')
def main():
test = TestRemoveDupes()
linked_list = MyLinkedList(None)
test.test_remove_dupes(linked_list)
if __name__ == '__main__':
main()
Overwriting test_remove_duplicates.py
run -i test_remove_duplicates.py
Test: Empty list Test: One element list Test: General case, duplicates Test: General case, no duplicates Success: test_remove_dupes