Linked List Data Structures

In this data structure tutorial, we will learn all aspects of the linked list. We will start by the introduction of linked list than linked list examples, linked list algorithms and various types of linked lists such as Grounded Header Linked List, Circular Linked List, Double or Doubly Linked List, Singly Linked List etc.

What is a Linked List in Data Structure? 

A linked list is a linear collection of data elements or nodes; the here linear order is given by pointers. Each data element or node in linked list is divided into two parts:

• Contains the actual data of the element. 
• This part contains the address of next node. 

This type of linked list is called one-way linked list. Let’s take a look on below example to understand the basic concept of linked list.

Linked List Example

In above-linked list diagram, there are three nodes and each node is divided into two parts first part contains the data and second part contains the address of next node. The address part of the last node is null because this is the end of the linked list.

Need of Linked List 

You may know, arrays stored in contiguous memory location means one after another. Take a real life example, suppose there is a classroom which contains 50 seats for students. Suppose students are coming randomly than they sit according to their choice so after some time you see there are 10 seats are available but they are not contiguous. So, remaining 10 students have to sit where seats are empty. If they say we all want to sit together then this is not possible like an array. Same in computers we store our data, then after some time we have non-contiguous space. So linked list can utilize it efficiently because they don’t take contiguous storage in memory.

Traversing a Linked List 

Traversing a linked list means read all nodes of linked list at least one time. Suppose there is a linked list stored in the memory. Consider the following algorithm to understand how to traverse a linked list.

Linked List Traversing Algorithm in Data Structures

In this algorithm we use a variable PTR it contains the address of the first node. Then we apply a loop and loop continues until PTR is not equal to Null. In next step, we PRINT the value of node then in next step we assign the PTR:= LINK[PTR] means the address of next node.

1. Step I: Set PTR := START. [Initializes pointer PTR.]
2. Step II: Repeat steps 3 and 4 while PTR != NULL:
3. Step III: PRINT: INFO[PTR]. [Print information of node.]
4. Step IV: Set PTR := LINK[PTR]. [PTR now points to the next node.]
5. [End of step 2 loop.]
6. Step V: Exit.

Consider the following example to understand the above algorithm:

Traversing Linked List

According to our above algorithm:

1. PTR = 220 
2. Now loop will Continue until PTR in not equal to null. 
3. PRINT: INFO[PTR] mean PRINT: 4 
4. PTR = LINK[PTR] means PTR = 220 now. 

Now we will again go to step 2 because PTR is not null this loop continues until the pointer is not equal to null.

Header Linked List 

Header linked list contains a special node in starting, this node is called header node. Header node contains the information about the linked list such as the type of data in linked list, the number of nodes in linked list etc. There are two types of header linked list:

1. Grounded Header Linked List 
2. Circular Header Linked List

Grounded Header Linked List

A linked list which has a header node in beginning and last node contains the null pointer is called grounded header linked list.

Grounded Header Linked List

Circular Header Linked List

In circular header linked list the last node contains the address of the first node. It means we can move the last node to the first node when we reach the end of linked list.

Circular Header Linked List

Grounded header linked list and circular header linked list are same but the only difference is that last node of circular header linked list contains the address of the first node whereas the last node of grounded header linked list contains a null pointer.

Algorithm for Traversing Grounded Header Linked List Data Structure

1. Step I: Set PTR: = LINK [START]. [Initializes the pointer PTR.]
2. Step II: Repeat steps 3 and 4 while PTR != START:
3. Step III: PRINT: INFO [PTR]. [Print information of node.]
4. Step IV: Set PTR: = LINK [PTR]. [PTR now points to the next node.]
5. [End of step 2 loop.]
6. Step V: Exit.

Traversing in circular header linked list is same as of normal linked list but the difference is that here the loop continues until PTR != START. Because last node’s pointer contains the address of the first node.

Doubly Linked List or Two Way Linked List in Data Structures

In the doubly linked list, we can navigate in both ways which means backward and forward. In doubly linked list each node is divided into three parts: first part contains the address of previous node, the second node contains the actual data and third part contains the address of next node.

Doubly Or Two Way Linked List

Traversing Doubly Linked List Algorithm

Doubly Linked List or Two way linked lists can be traversed in two ways:

1. Traversing from Beginning of the linked list

Step I: Set PTR := START. [Initializes the pointer PTR.]
Step II: Repeat steps 3 and 4 while PTR != NULL:
Step III: PRINT: INFO[PTR].
[Print information of node.]
Step IV: Set PTR := FORW[PTR].
[PTR now points to the next forward node.]
[End of step 2 loop.]
Step V: Exit.

2. Traversing Doubly Linked List from Ending

Step I: Set PTR := END. [Initializes the pointer PTR.]
Step II: Repeat steps 3 and 4 while PTR != NULL:
Step III: PRINT: INFO[PTR].
[Print information of node.]
Step IV: Set PTR := BACKW[PTR].
[PTR now points to the next backward node.]
[End of step 2 loop.]
Step V: Exit.