Traverse and Print all values present in 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 or iterating 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 in forward or reverse direction, 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
// Node struct to store an item/value and link to the next node
typedef struct Node {
char* item;
struct Node* next;
} Node;
// Function to create a new node with the given item
Node* create_node(char* item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->item = item;
new_node->next = NULL;
return new_node;
}
// Node class to store a item/value and link to the next node
class Node {
public:
std::string item;
Node* next;
Node(std::string item) {
this->item = item;
this->next = nullptr;
}
};
// Node class to store a item/value and link to the next node
class Node {
constructor(item) {
this.item = item;
this.next = null;
}
}
// Node class to store a item/value and link to the next node
public class Node {
public String item;
// Link to the next node
public Node next;
// Constructor to initialize the node with the given item
public Node(String item) {
this.item = item;
this.next = null;
}
}
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
head = node1
tail = node4
# We can now traverse the linked list using the head pointer
#include <stdio.h>
#include <stdlib.h>
// Node structure to store data and next pointer
typedef struct Node {
char* item;
struct Node* next;
} Node;
// Function to create a new node with the given item
Node* create_node(char* item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->item = item;
new_node->next = NULL;
return new_node;
}
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = create_node("A");
Node* node2 = create_node("B");
Node* node3 = create_node("C");
Node* node4 = create_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
Node* head = node1;
Node* tail = node4;
// We can now traverse the linked list using the head pointer
return 0;
}
// Node class to store a item/value and link to the next node
class Node {
public:
std::string item;
Node* next;
// Constructor to initialize the node
Node(std::string item) {
this->item = item;
this->next = nullptr;
}
};
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = new Node("A");
Node* node2 = new Node("B");
Node* node3 = new Node("C");
Node* node4 = new 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
Node* head = node1;
Node* tail = node4;
// We can now traverse the linked list using the head pointer
return 0;
}
// Node class to store a item/value and link to the next node
class Node {
constructor(item) {
this.item = item;
this.next = null;
}
}
// Create all the nodes we need for creating linked list
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");
const node4 = new 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
const head = node1;
const tail = node4;
// We can now traverse the linked list using the head pointer
// Node class to store a item/value and link to the next node
class Node {
String item;
Node next;
// Constructor to initialize the node with given item
Node(String item) {
this.item = item;
this.next = null;
}
}
public class Main {
public static void main(String[] args) {
// Create all the nodes we need for creating linked list
Node node1 = new Node("A");
Node node2 = new Node("B");
Node node3 = new Node("C");
Node node4 = new 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
Node head = node1;
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
head = node1
# Function which takes in first node (head) of a linked list
# and prints all elements in it in forward direction
def print_linked_list(head):
# Check if the list is empty
if head is None:
print("The given linked list is empty")
return
current = head
print("Elements in the linked list:")
# 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
print_linked_list(head)
#include <stdio.h>
#include <stdlib.h>
// Node struct to store a item/value and link to the next node
typedef struct Node {
char* item;
struct Node* next;
} Node;
// Function to create a new node with the given item
Node* create_node(char* item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->item = item;
new_node->next = NULL;
return new_node;
}
// Function which takes in first node of linked list
// And prints all elements in it in forward direction
void print_linked_list(Node* head) {
// Check if the list is empty
if (head == NULL) {
printf("The given linked list is empty\n");
return;
}
Node* current = head;
printf("Elements in the linked list: ");
// Traverse the linked list until we reach the end
while (current != NULL) {
// print item present in current node
printf("%s ", current->item);
// Move forward to the next node
current = current->next;
}
printf("\n");
}
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = create_node("A");
Node* node2 = create_node("B");
Node* node3 = create_node("C");
Node* node4 = create_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
Node* head = node1;
// We can now traverse the linked list using the head pointer
print_linked_list(head);
// Ideally, all the nodes should be deleted to avoid memory leaks
return 0;
}
#include <iostream>
// Node class to store a item/value and link to the next node
class Node {
public:
std::string item;
Node* next;
// Constructor to initialize the node
Node(std::string item) {
this->item = item;
this->next = nullptr;
}
};
// Function which takes in first node (head) of a linked list
// and prints all elements in it in forward direction
void print_linked_list(Node* head) {
// Check if the list is empty
if (head == nullptr) {
std::cout << "The given linked list is empty" << std::endl;
return;
}
Node* current = head;
std::cout << "Elements in the linked list: ";
// Traverse the linked list until we reach the end
while (current != nullptr) {
// Print item present in current node
std::cout << current->item << " ";
// Move forward to the next node
current = current->next;
}
std::cout << std::endl;
}
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = new Node("A");
Node* node2 = new Node("B");
Node* node3 = new Node("C");
Node* node4 = new 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
Node* head = node1;
// We can now traverse the linked list using the head pointer
print_linked_list(head);
return 0;
}
// Node class to store a item/value and link to the next node
class Node {
constructor(item) {
this.item = item;
this.next = null;
}
}
// Create all the nodes we need for creating linked list
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");
const node4 = new 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
const head = node1;
// Function which takes in first node (head) of a linked list
// and prints all elements in it in forward direction
function printLinkedList(head) {
// Check if the list is empty
if (head === null) {
console.log("The given linked list is empty");
return;
}
let current = head;
console.log("Elements in the linked list:");
// Traverse the linked list until we reach the end
while (current !== null) {
// print item present in current node
console.log(current.item);
// Move forward to the next node
current = current.next;
}
}
// We can now traverse the linked list using the head pointer
printLinkedList(head);
// Node class to store a item/value and link to the next node
class Node {
String item;
Node next;
// Constructor to create a new node with the given item
public Node(String item) {
this.item = item;
this.next = null;
}
}
public class Main {
public static void main(String[] args) {
// Create all the nodes we need for creating linked list
Node node1 = new Node("A");
Node node2 = new Node("B");
Node node3 = new Node("C");
Node node4 = new 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
Node head = node1;
// We can now traverse the linked list using the head pointer
printLinkedList(head);
}
// Function which takes in first node (head) of a linked list
// and prints all elements in it in forward direction
public static void printLinkedList(Node head) {
// Check if the list is empty
if (head == null) {
System.out.println("The given linked list is empty");
return;
}
Node current = head;
System.out.println("Elements in the linked list:");
// Traverse the linked list until we reach the end
while (current != null) {
// Print item present in current node
System.out.print(current.item + " ");
// Move forward to the next node
current = current.next;
}
}
}
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
head = node1
# Function which takes in first node (head) of a linked list
# and prints all elements in it in reverse direction
def reverse_print_linked_list(head):
# Return if we reached the end of linked list
if head is None:
return
# Recursively traverse the list to the end
reverse_print_linked_list(head.next)
# Print the current node's data
print(head.item, end=" ")
# We can now traverse the linked list using the head pointer
print("Elements in the linked list in reverse order:")
reverse_print_linked_list(head)
#include <stdio.h>
#include <stdlib.h>
// Node struct to store a item/value and link to the next node
typedef struct Node {
char item;
struct Node* next;
} Node;
// Function to create a new node with the given item
Node* create_node(char item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->item = item;
new_node->next = NULL;
return new_node;
}
// Function which takes in first node (head) of a linked list
// and prints all elements in it in reverse direction
void reverse_print_linked_list(Node* head) {
// Return if we reached the end of linked list
if (head == NULL) {
return;
}
// Recursively traverse the list to the end
reverse_print_linked_list(head->next);
// Print the current node's data
printf("%c ", head->item);
}
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = create_node('A');
Node* node2 = create_node('B');
Node* node3 = create_node('C');
Node* node4 = create_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
Node* head = node1;
// Print the elements in the linked list in reverse order
printf("Elements in the linked list in reverse order:\n");
reverse_print_linked_list(head);
// Ideally, all the created nodes should be deleted to avoid memory leaks
return 0;
}
#include <iostream>
// Node class to store a item/value and link to the next node
class Node {
public:
std::string item;
Node* next;
Node(std::string item) {
this->item = item;
this->next = nullptr;
}
};
// Function which takes in first node (head) of a linked list
// and prints all elements in it in reverse direction
void reverse_print_linked_list(Node* head) {
// Return if we reached the end of linked list
if (head == nullptr) {
return;
}
// Recursively traverse the list to the end
reverse_print_linked_list(head->next);
// Print the current node's data
std::cout << head->item << " ";
}
int main() {
// Create all the nodes we need for creating linked list
Node* node1 = new Node("A");
Node* node2 = new Node("B");
Node* node3 = new Node("C");
Node* node4 = new 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
Node* head = node1;
// We can now traverse the linked list using the head pointer
std::cout << "Elements in the linked list in reverse order:" << std::endl;
reverse_print_linked_list(head);
}
// Node class to store a item/value and link to the next node
class Node {
constructor(item) {
this.item = item;
this.next = null;
}
}
// Create all the nodes we need for creating linked list
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");
const node4 = new 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
const head = node1;
// Function which takes in first node (head) of a linked list
// and prints all elements in it in reverse direction
function reverse_print_linked_list(head) {
// Return if we reached the end of linked list
if (head === null) {
return;
}
// Recursively traverse the list to the end
reverse_print_linked_list(head.next);
// Print the current node's data
console.log(head.item);
}
// We can now traverse the linked list using the head pointer
console.log("Elements in the linked list in reverse order:");
reverse_print_linked_list(head);
// Node class to store a item/value and link to the next node
class Node {
String item;
Node next;
// Constructor to create a new node with the given item
Node(String item) {
this.item = item;
this.next = null;
}
}
public class Main {
public static void main(String[] args) {
// Create all the nodes we need for creating linked list
Node node1 = new Node("A");
Node node2 = new Node("B");
Node node3 = new Node("C");
Node node4 = new 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
Node head = node1;
// We can now traverse the linked list using the head pointer
reversePrintLinkedList(head);
}
// Function which takes in first node (head) of a linked list
// and prints all elements in it in reverse direction
static void reverseTraverse(Node node) {
// Return if we reached the end of linked list
if (node == null) {
return;
}
// Recursively traverse the list to the end
reverseTraverse(node.next);
// Print the current node's data
System.out.print(node.item + " ");
}
// Function to call the recursive reverseTraverse function
static void reversePrintLinkedList(Node head) {
System.out.println("Elements in the linked list in reverse order:");
reverseTraverse(head);
}
}
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.