Lined list is a useful data structure that allows dynamic storage of data node using links. Each node stores address of next node of the Linked List. Data Structure Linked List traversal is the process to visit each node of the linked list at least once.
Traversal in Linked List is required for different tasks like:
- Counting the number of nodes in the linked list.
- Processing data of every node.
- Displaying the data stored in the linked list nodes.
- Searching a node with specific data in the liked list.
Steps to Linear Linked List Traversal
- Traversal process starts with assignment of address of first node to a pointer variable. This is considered as the current node.
- The data of the current node is processed.
- The current node is then updated with the address of next node by assigning link part of current node to the current pointer.
- After moving from first to last node by updating current node and when the current pointer becomes null, the traversal process is terminated.
Traversing Linked List
The Data Structure Linked List-Traversal is created with nodes with DATA and LINK part. START pointer stores the address of the first node of the linked list. At the beginning, CURR pointer is assigned the address of the first node stored in the START pointer.
To access the next node of the linked list CURR is assigned the CURR->LINK. Now CURR pointer stores the address of next node.
This process is continued and in every step the CURR pointer moves to the next Node.
When the CURR pointer has accessed the last element, CURR=CURR->LINK assignment stores NULL in the CURR pointer. This is the moment when the traversal process terminates.
Algorithm Traverse (DATA, NODE, START) Desc: This algorithm performs Data Structure Linked List-Traversal. Each Linked List Node is created of two parts DATA and LINK. LINK part stores the address of next node in the linked list. START pointer stores the address of first node. Begin Step 1: [Initialize CURR with address of first node which is stored in START pointer] CURR=START Step 2: [Iterate through the Linked list ] Repeat steps 3 and 4 while CURR is not NULL Step 3: Process CURR->DATA Step 4: [Update the CURR pointer with LINK part of current node] CURR=CURR->LINK Exit
The step 3 of the algorithm is modified to add a counter value or print statement of the concerned programming language. This way it can count total nodes or print the value of the current node.