# Traversing a Linked List Data Structure

Linked lists are made up of a sequence of nodes where each node links to the next node, forming a chain-like structure. Traversing a linked list involves visiting each node in the list in sequence, access the contents of each node, and navigating to the subsequent nodes until reaching the end of the list. This article focuses on visiting all nodes in a linked list sequentially while printing the values present in each node of the linked list.

## Prerequisites

Before we look at the actual algorithm and code for traversing a linked list in forward or reverse direction, let’s briefly go through how a linked list is represented and how a sample linked list is created.

In all the code snippets included in this article, each linked list node is represented with the below structure:

``````
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
``````

In the `Node` class defined above, “`item`” field is used to store the data of linked list node. It’s type is set to string for this article. “`next`” field is used to store a reference to the next node in the linked list.

And this is how the linked list is created before the traversal operation:

``````
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store references to Head node and Tail node
tail = node4

# We can now traverse the linked list using the head pointer
``````

In order to keep the linked list creation logic simple, all the nodes of the linked list are created together and then they are linked in a sequence. Reference to the first node (also called as the `head` node) is stored which can be used during iteration of all the nodes in the linked list.

## Traversing a Linked List in forward direction

Below is the code to iterate through all nodes in a linked list in forward direction, while printing the values present in each node.

``````
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store reference to Head node

# Function which takes in first node (head) of a linked list
# and prints all elements in it in forward direction
# Check if the list is empty
print("The given linked list is empty")
return

# Traverse the linked list until we reach the end
while current is not None:
# print item present in current node
print(current.item, end=" ")

# Move forward to the next node
current = current.next

# We can now traverse the linked list using the head pointer
``````

When you run this code, the output will be:

``````Elements in the linked list in forward order:
A B C D
``````

Here is how the above code works:

• `Node` class is defined to create nodes for the linked list, where each node has
• an `item` attribute which stores data and
• a `next` pointer which stores reference to the next node in the list.
• `print_linked_list` function takes the `head` node pointer as an argument and traverses the entire linked list while printing the values of each node.
• It first checks if the list is empty by verifying if the `head` pointer is `None`.
• If the linked list is empty, it prints a message stating that the list is empty and returns.
• If the linked list is not empty, it initializes a pointer/reference variable “`current`” to point to the `head` node of the list.
• It then traverses the linked list starting from the `head` node:
• Prints the value present in `current` node.
• Moves the `current` pointer to the next node using `current = current.next`.
• Stops when the `current` node reaches the end of linked list.

## Traversing a Linked List in reverse direction

Below is the code to iterate through all nodes in a linked list in reverse direction, while printing the values present in each node.

``````
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store reference to Head node

# Function which takes in first node (head) of a linked list
# and prints all elements in it in reverse direction
# Return if we reached the end of linked list
return

# Recursively traverse the list to the end

# Print the current node's data

# We can now traverse the linked list using the head pointer
print("Elements in the linked list in reverse order:")
``````

When you run this code, the output will be:

``````Elements in the linked list in reverse order:
D C B A
``````

In this code, we have a `Node` class that represents a single node in the linked list. The `reverse_print_linked_list` function takes the head node of the linked list as input and recursively traverses the list in reverse direction while printing the values.

Here’s how the code works:

• The `reverse_print_linked_list` function first checks if the `head` node is `None`. If it is, the function simply returns, as there’s no other node to traverse.
• If the `head` node is not `None`, the function recursively calls itself with the `next` node of the current `head` node. This allows the function to reach the end of the linked list.
• Once the function reaches the end of the list, it starts printing the data of each node in reverse order. This is achieved by the print statement at the end of the function.