Data Structure - Logic of Singly linked list

 What is a Singly linked list ?

Single linked lists are linear data structures where elements are not stored in contiguous locations but they are linked using pointers. The linked list comes into picture when the data is dynamic in nature and size of data is not known initially. Here I've explained the Singly linked list from the basics so that the learner gets a better idea of it.

Structure of Singly linked list

        The linked lists are made up of nodes. Each node is made up of two parts : data part and address part (holds the address of the next node).

Representation of a node in C/C++ language:

struct Node {
    int data;          // data part
    Node* link;        // Address of the next node
}*head;
  

Constructing a linked list:

        Let us consider 4 integers and its corresponding addresses as given in the below table. We shall construct a linked list with this data. The first node in the single linked list is called head node which contains the “10” in its data part and the address of the next node (here it is 10002) in its address part. The second node holds the data element “20” and the address of the next node( here it holds the value 10003). Similarly other nodes will have the data part and the address of the successive nodes. The last node is called the tail node which contains the data “40” and contains NULL in its address part which denotes the end of the linked list.

Data in node	Address of the node
10	10001
20	10002
30	10003
40	10004

Constructing nodes in C/C++ :

Node *second, *third, *tail;
head = new Node;
second = new Node;
third = new Node;
tail = new Node;
 
head -> data = 10;
head -> link = second;
 
second -> data = 20;
second -> link = third;
 
third -> data = 30;
third -> link = tail;
 
tail -> data = 40;
tail -> link = NULL;

Adding nodes :

        Let us consider that we have to add a node with data “25” between the 2nd and 3rd node. Remember that we have to add the new node without breaking the link with the 3rd node.

STEP 1 : Set the value of data in new node 

STEP 2 : Copy the address part from 2nd node to new node

STEP 3 : Store the address of new node in the address part of 2nd node

Adding new node using C/C++ :

Node * temp;                                // New node
temp = new Node;
temp -> data = 25;		  	    // STEP 1
temp -> link = second -> link;              // STEP 2
second -> link = temp;                      // STEP 3

Deleting nodes :

Let us consider that we need to delete the 3rd node (“25”). Deletion can be done simply in 2 steps : Copy the address part of the 3rd node to the 2nd node and clear the memory of the 3rd node.

STEP 1:

STEP 2:

Deleting nodes using C/C++:

second -> link = temp -> link;
delete temp;

Search nodes:

Nodes can be searched starting from the head node till the tail node.

Node * node;
for (node = head ;  node !=NULL ; node = node -> link)
{
	if (node -> data == number)
		cout << “Number is found” << endl;
}

Advantages of singly linked list:

1. List can be extended or shrunk since memory can be allocated dynamically.

2. Insertion and deletion can be made easily.

Disadvantages of single linked list:

1. A Singly Linked list can be traversed only in forward direction.

2. For searching any elements in the singly linked list, traversal has to be started right from the beginning of the list only.

Applications of advanced linked list (doubly linked lists):

      1.To navigate forward and backward in the browser window.

     2.To maintain playlists in the Music app.

     3.To view previous and next images in the Image viewer.

Complete C++ code for Singly linked list:

The following code gives the overview of functionalities of the Singly linked list. In order to make the learner to get a clear idea of a Singly linked list, the code has not been optimized.

#include <iostream>
using namespace std;
 
struct Node {
    int data;             // data part
    Node* link;           // Address of the next node
} *head;
 
 
int main()
{
    Node *second, *third, *tail;
    head = new Node;
    second = new Node;
    third = new Node;
    tail = new Node;
    
    head -> data = 10;
    head -> link = second;
 
    second -> data = 20;
    second -> link = third;
   
    third -> data = 30;
    third -> link = tail;
 
    tail -> data = 40;
    tail -> link = NULL;
    
    // Adding node to linked list
    
    Node * temp;                                       // New node
    temp = new Node;
    temp -> data = 25;		                       // STEP 1
    temp -> link = second -> link;               // STEP 2
    second -> link = temp;                          // STEP 3
 
    // Printing linked list
 
    cout << "\nShowing list after insertion" << endl;
    Node * node;
    for (node = head ;  node !=NULL ; node = node -> link)
    {
		cout << "Data : " << node -> data << "|Address of current node :" << node <<   "|Address of next node : " << node -> link << endl;
    }
    
    // Deleting node from linked list
    
    second -> link = temp -> link;
    delete temp;
    
    // Printing linked list
   
     cout << "\nShowing list after deletion" << endl;
    for (node = head ;  node !=NULL ; node = node -> link)
    {
		cout << "Data : " << node -> data << "|Address of current node :" << node << "|Address of next node : " << node -> link << endl;
    }
    return 0;
}

Output:

 

.