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 = 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
.
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 = 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))