Linked List
 Linked List over Array?
 Linked List Traversal Algorithm
 Linked List Traversal Illustration
 Linked List Traversal Implementation
 Linked List Traversal Algorithm Complexity
A linked list is a linear data structure. It is a collection of objects defined as nodes. But in the linked list, nodes are stored in random positions in memory and not stored in contiguous locations.
A node of the linked list consists of:

A data item.

An address of the next node.
class Node {
int data;
Node *next;
};
This representation of the node is used to create every node in the list. The data field stores the element, and *next
is a pointer to store the next node’s address.
The address of the first node is called the head, and the last node is called the tail. The last node in the linked list points to NULL
. So, when the list is empty head node points to the NULL
node. Linked lists do not require declaring the size beforehand and can grow dynamically in size. It is very easy to insert and delete elements in a linked list. We do not need to move all the elements; only changing the previous and next elements’ pointers is sufficient.
Linked List over Array?
Linked lists have a natural advantage over array in the sense that we do not have to allocate a huge chunk of memory beforehand, but that also makes them cache unfriendly as memory is not allocated continuously. They allow easy insertion and deletion of elements with the help of pointers but also costs double memory for each node due to the space required by pointers. Linked lists also do not provide random access to elements. So, it is clear that there is no single winner and both linked lists and array have their own set of advantages and disadvantages.
Arrays should be used when we have a small list with knowledge of the maximum number of elements that we might store, whereas Linked lists should be used when there is a large list that is regularly changing.
Linked List Traversal Algorithm
Let the head
be the first node of the linked list.

Initialize
curr
pointing to thehead
node of the linked list. 
While
curr
does not reach the end of the list i.e.curr
!=NULL
, do the following: print the data stored inside the current node.
curr=curr>next
;
Linked List Traversal Illustration

Initialize a pointer
curr
pointing to thehead
node with a data value equal to2
. Print the value2
. 
Move the pointer
curr
to the next node with the value4
. Print the value4
. 
Move the pointer
curr
to the next node with the value6
. Print the value6
. 
Move the pointer
curr
to the next node with the value8
. Print the value8
. 
Move the pointer
curr
to the next node, which equalsNULL
. Thewhile
loop termination condition is reached. Hence, we have visited all the nodes.
Linked List Traversal Implementation
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this>data = x;
this>next = NULL;
}
};
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
cout << curr>data << " ";
curr = curr>next;
}
}
int main() {
Node* head = new Node(1);
head>next = new Node(2);
head>next>next = new Node(3);
head>next>next>next = new Node(4);
head>next>next>next>next = new Node(5);
head>next>next>next>next>next = new Node(6);
printList(head);
return 0;
}
Linked List Traversal Algorithm Complexity
Time Complexity
 Average Case
To traverse the complete linked list, we have to visit each node. So, if a linked list has n
nodes, the averagecase time complexity of traversal is of the order of O(n)
. The time complexity is of the order of O(n)
.
 Best Case
The bestcase time complexity is O(n)
. It is the same as averagecase time complexity.
 Worst Case
The worstcase time complexity is O(n)
. It is the same as bestcase time complexity.
Space Complexity
This traversal algorithm’s space complexity is O(1)
as no extra space other than the curr
pointer is required.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort