Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
linked list
data structure
communitycreator

How to compare two linked lists

Dhruv Sharma

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()
Create a linked list

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))
Compare lists

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".

RELATED TAGS

python
linked list
data structure
communitycreator
RELATED COURSES

View all Courses

Keep Exploring