A LinkedList
is a collection of nodes that together represent a sequence.
It is a dynamic
and linear
data structure. It doesn’t need a contiguous memory location.
It can be visualized as a chain of nodes where each node contains a data field and a reference to the next node
in the list
.
LinkedList
can be further classified into:
LinkedList
LinkedList
Traversal()
?Traversal()
is used to visit each node
of the list
to perform an operation.
Here, we will traverse and print data present in the list
.
LinkedList
A singly LinkedList
is Uni-directional
, meaning traversal is possible in forwarding direction only.
#Traversing using singly linked list class Node: #Creating a node def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: #Node is attribute of linkedlist def __init__(self): self.head = None def Traversal(self): #Traversal through linked List n = self.head while n is not None: print (n.data) n = n.next list = SinglyLinkedList() list.head = Node("Monday") l2 = Node("Tuesday") l3 = Node("Wedneday") # Link first Node to second node list.head.next = l2 # Link second Node to third node l2.next = l3 list.Traversal()
node
because a collection of nodes is a LinkedList
.node
consists of two attributes, self.data = data
and self.next = None
.SinglyLinkedList
.Traversal()
function to traverse along with the list
.list
by assigning some values.node
, which is done by list.head.next = l2
and
l2.next = l3
.LinkedList
A doubly LinkedList
is Bi-directional
, meaning traversal is possible in both forward and backward directions.
class Node: #Creating a node def __init__(self, data): self.data = data self.nref = None self.pref=None class doublyLinkedList: #Node is attribute of linkedlist def __init__(self): self.head = None def insert_empty(self,data): if self.head is None: new_node=Node(data) self.head=new_node def add_begin(self,data): new_node=Node(data) if self.head is None: self.head=new_node else: new_node.nref=self.head self.head.pref=new_node self.head=new_node def add_end(self,data): new_node=Node(data) if self.head is None: self.head=new_node else: n=self.head while n.nref is not None: n=n.nref n.nref=new_node new_node.pref=n def Traversal_forward(self): #Traversal in forward direction if self.head is None: print("Linked list is empty!") else: n=self.head while n is not None: print(n.data) n=n.nref def Traversal_backward(self):#Traversal in backward direction if self.head is None: print("LL is empty!") else: n=self.head while n.nref is not None: n=n.nref while n is not None: print(n.data) n=n.pref dl1 = doublyLinkedList() dl1.insert_empty('Monday') dl1.add_begin('Tuesday') dl1.Traversal_forward() dl1.Traversal_backward()
node
in doubly LinkedList
. It consist of three attributes self.data = data
, self.nref = None
, and self.pref=None
.doublyLinkedList()
in which we can traverse in both directions.insert_empty()
to insert elements in an empty LinkedList
.add_begin()
to add elements in the beginning, and change the self.head
to the current node
.add_end()
to add elements in the end.Traversal_forward()
and Traversal_backward()
to traverse the LinkedList
in both the directions.In this way, traversal operation takes place in the LinkedList
.
RELATED TAGS
CONTRIBUTOR
View all Courses