Trusted answers to developer questions
Traversal operations in LinkedList
Adithya Challa
Overview
A LinkedList is a collection of nodes that together represent a sequence.
-
It is a
dynamicandlineardata 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
nodein thelist. -
LinkedListcan be further classified into:
- Singly
LinkedList - Doubly
LinkedList
What is 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.
Singly LinkedList
A singly LinkedList is Uni-directional, meaning traversal is possible in forwarding direction only.
Example
#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()Traversal in a singly linked list
Explanation
- Line 1–3: We initially create a
nodebecause a collection of nodes is aLinkedList. - Line 3–6: A
nodeconsists of two attributes,self.data = dataandself.next = None. - Line 7–10: Next, we create a class named
SinglyLinkedList. - Line 10–15: We use the
Traversal()function to traverse along with thelist. - Line 17–20: We are calling the
listby assigning some values. - Line 20–26: For traversing further, it is important to link each
node, which is done bylist.head.next = l2andl2.next = l3.
Doubly LinkedList
A doubly LinkedList is Bi-directional, meaning traversal is possible in both forward and backward directions.
Example
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()
Traversal in doubly linkedlist
Explanation
- Line 1–5: We create a
nodein doublyLinkedList. It consist of three attributesself.data = data,self.nref = None, andself.pref=None. - Line 6–10: We create a class
doublyLinkedList()in which we can traverse in both directions. - Line 9–12: We use
insert_empty()to insert elements in an emptyLinkedList. - Line 13–20: We use
add_begin()to add elements in the beginning, and change theself.headto the currentnode. - Line 20–25: We use
add_end()to add elements in the end. - Line 20–30: We use
Traversal_forward()andTraversal_backward()to traverse theLinkedListin both the directions.
In this way, traversal operation takes place in the LinkedList.
RELATED TAGS
python
communitycreator
data structures
linkedlist
CONTRIBUTOR
Adithya Challa
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
