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 = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# print list
def print_ll(self):
temp = self.head
while temp:
print(str(temp.data))
temp = temp.next
# insert a new node
def insert(self, data):
node = Node(data)
if not self.head:
self.head = node
else:
self.tail.next = node
self.tail = node
# create a linked list
l1 = SinglyLinkedList()
# create an array
l1val = [1,2,3,4,5]
# insert elements into the list
for i in l1val:
l1.insert(i)
# print list
l1.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.

widget

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 = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# insert a new node
def insert(self, data):
node = Node(data)
if not self.head:
self.head = node
else:
self.tail.next = node
self.tail = node
# function to compare two lists
def compare_lists(llist1, llist2):
now1 = llist1
now2 = llist2
while now1 != None and now2 != None:
if now1.data != now2.data:
return 0
now1 = now1.next
now2 = now2.next
if now1 != None or now2 != None:
return 0
return 1
# create the first list
l1 = SinglyLinkedList()
l1val = [1,2,3,4,5]
for i in l1val:
l1.insert(i)
# create the second list
l2 = SinglyLinkedList()
l2val = [1,2,3,4]
for i in l2val:
l2.insert(i)
# create the third list
l3 = SinglyLinkedList()
l3val = [1,2,3,4,5]
for i in l3val:
l3.insert(i)
# compare the first and the second lists
print(compare_lists(l1.head,l2.head))
# compare the first and the third lists
print(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".

Free Resources