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 = Nonedef print_ll(self):temp = self.headwhile temp:print(str(temp.data))temp = temp.nextdef insert(self, data):node = Node(data)if not self.head:self.head = nodeelse:self.tail.next = nodeself.tail = nodel1 = SinglyLinkedList()l1val = [1,2,3,4,5]for i in l1val:l1.insert(i)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 in the SinglyLinkedList
class.
Node
class is used to create a new node, each node has a data
attribute and a pointer
attribute to the next node which initially points to a null.
Consider two linked lists that will meet at some point. The head nodes of both lists are given pointers to find the node where the two lists merge.
In the above example, the two lists merge at Node 4, which is the result of the function.
In the program below, we use the merge_point()
function to find the data of the node where both the lists merge.
class SinglyLinkedListNode:def __init__(self, data):self.data = dataself.next = Noneclass SinglyLinkedList:def __init__(self):self.head = Noneself.tail = Nonedef insert(self, data):node = SinglyLinkedListNode(data)if not self.head:self.head = nodeelse:self.tail.next = nodeself.tail = nodedef merge_point(head1, head2):data = []while head1 != None:data.append(head1)head1 = head1.nextwhile head2 != None:if head2 in data:return (head2.data)head2 = head2.nextl1 = SinglyLinkedList()l1val = [1,2,3,4,5]l1_count = 5for i in l1val:l1.insert(i)l2 = SinglyLinkedList()l2val = [9,2]l2_count = 2for i in l2val:l2.insert(i)ptr1 = l1.head;ptr2 = l2.head;for i in range(l1_count):if i < 3:ptr1 = ptr1.nextfor i in range(l2_count):if i != l2_count-1:ptr2 = ptr2.nextptr2.next = ptr1print(merge_point(l1.head, l2.head))
We follow the steps below to run the merge_point()
function:
Lines 21–23: Traverse the first linked list and add all the nodes in a list called data
Lines 24–25: Check if any node exists in the data
list to traverse the second linked list.
Lines 25–26: Use an exit condition to return the data of the node which exist in the data
list.