Trusted answers to developer questions

Dhruv Sharma

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.

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`

.

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.

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

- 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

CONTRIBUTOR

Dhruv Sharma

RELATED COURSES

View all Courses

Keep Exploring

Related Courses