How to compare two linked lists
Overview
A linked list is a collection of nodes. Each node contains data and a pointer to the next node.
A Linked List is preferred over other data structures, like arrays, because it has a dynamic size and it's easier to insert and delete elements/nodes.
How to create a linked list
class Node:def __init__(self, data):self.data = dataself.next = Noneclass SinglyLinkedList:def __init__(self):self.head = Noneself.tail = None# print listdef print_ll(self):temp = self.headwhile temp:print(str(temp.data))temp = temp.next# insert a new nodedef insert(self, data):node = Node(data)if not self.head:self.head = nodeelse:self.tail.next = nodeself.tail = node# create a linked listl1 = SinglyLinkedList()# create an arrayl1val = [1,2,3,4,5]# insert elements into the listfor i in l1val:l1.insert(i)# print listl1.print_ll()
In a linked list, the head attribute refers to the first node of a list. All the functions used in the list are added to the SinglyLinkedList class.
A Node class is used to create a new node. Each node has a data attribute and a pointer for the next node which initially points to a null.
How to compare the linked lists
Consider we have two linked lists. If we have the head pointers of the two lists, we can check if the lists are equal or not.
In the above figure, the two lists are similar till the 4th node. The first list has an extra element at the end.
Application
In the program given below, the compare_lists() function is used to check if the lists are equal or not. The function returns "0" if the lists are unequal and "1" if they are equal.
class Node:def __init__(self, data):self.data = dataself.next = Noneclass SinglyLinkedList:def __init__(self):self.head = Noneself.tail = None# insert a new nodedef insert(self, data):node = Node(data)if not self.head:self.head = nodeelse:self.tail.next = nodeself.tail = node# function to compare two listsdef compare_lists(llist1, llist2):now1 = llist1now2 = llist2while now1 != None and now2 != None:if now1.data != now2.data:return 0now1 = now1.nextnow2 = now2.nextif now1 != None or now2 != None:return 0return 1# create the first listl1 = SinglyLinkedList()l1val = [1,2,3,4,5]for i in l1val:l1.insert(i)# create the second listl2 = SinglyLinkedList()l2val = [1,2,3,4]for i in l2val:l2.insert(i)# create the third listl3 = SinglyLinkedList()l3val = [1,2,3,4,5]for i in l3val:l3.insert(i)# compare the first and the second listsprint(compare_lists(l1.head,l2.head))# compare the first and the third listsprint(compare_lists(l1.head,l3.head))
Explanation
- Line 25: We iterate the two lists together till one of them ends.
- Lines 26–27: During the iteration, if the corresponding elements of the two lists do not match, the function returns "0".
- Lines 31–32: If any of the two lists are not completely iterated over, the function returns "0".
- Line 34: During the iteration, if the two lists are equal and corresponding elements match, the function returns "1".