How to Implement A Singly Linked List in Data Structures

A singly linked list is like a train system, where it connects each bogie to the next bogie. A singly linked list is a unidirectional linked list; i.e., you can only traverse it from head node to tail node. Here are some quick facts about linked lists. It is used to do a slideshow or some basic operations on a notepad like undo and redo.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

How to Implement a Singly Linked List?

You can create nodes of singly linked lists using classes or structures. And you link them using the next pointer. 

Code:

// implementation of singly linked list

#include <bits/stdc++.h>

using namespace std;

//A class to create node

class Node {

public:

int data;

Node* next;

};

// A function to print the given linked list

// starting from the given node

void printList(Node* n)

{

while (n != NULL)

 {

cout << n->data << " ";

n = n->next;

 }

}

int main()

{

//creating nodes

Node* head = NULL;

Node* second = NULL;

Node* third = NULL;

Node* tail = NULL;

// allocate four nodes

head = new Node();

second = new Node();

third = new Node();

  tail = new Node(); 

head->data = 2; // assign data in head node

head->next = second; // Link first node with second

  second->data = 3; // assign data to second node

  second->next = third;//Link second node with third

  third->data = 5; // assign data to third node

  third->next = tail;//Link third node with tail

tail->data = 7;// assign data to tail node

tail->next=NULL;//link tail node with NULL

//printing singly linked list

cout<<"Created singly linked list: "<<endl;

printList(head);

return 0;

}

What Operations Can You Perform on a Singly Linked List?

You can perform two operations on a singly linked list:

• Insertion
• Deletion 

How to Insert a Node in a Singly Linked List?

You can insert a node at three different positions, they are:

• At the beginning
• At the end
• At a specific position after a node

Code:

//A c++ code to insert a node 

//in singly linked list 

#include <bits/stdc++.h>

using namespace std; 

//A class to create nodes

class Node 

{ 

public:

int data; 

Node *next; 

}; 

// A function to insert a node at the 

//beginning of singly linked list

void push(Node** head, int newdata) 

{ 

Node* newnode = new Node();//creating newnode

newnode->data = newdata; //put in data

newnode->next = (*head); //link newnode to head

(*head) = newnode; //changing head

} 

// A function to insert a node after  

//a specific node in a singly linked list

void insertAfter(Node* prevnode, int newdata) 

{ 

//check if previous node is null

if (prevnode == NULL) 

{ 

cout<< “the given previous node cannot be NULL”; 

return; 

} 

Node* newnode = new Node();//creating newnode

newnode->data = newdata; //put in data

//link newnode to prevnode’s next node

newnode->next = prevnode->next; 

prevnode->next = newnode; //link prevnode to newnode

} 

// A function to insert a node at the 

//end of singly linked list

void append(Node** head, int newdata) 

{ 

Node* newnode = new Node();//creating newnode

Node *last = *head; // creating a ‘last’ node

newnode->data = newdata; //put in data

newnode->next = NULL; //link newnode with null

//Check if head is null

if (*head == NULL) 

{ 

*head = newnode; 

return; 

} 

//traversing ‘last’ node to end of the linked list 

while (last->next != NULL) 

last = last->next; 

//link ‘last’ node with newnode

last->next = newnode; 

return; 

} 

// A function to print the given linked list

// starting from the given node

void printList(Node *node) 

{ 

while (node != NULL) 

{ 

cout<<" "<<node->data; 

node = node->next; 

} 

}   

/* Driver code*/

int main() 

{ 

/* Start with the empty list */

Node* head = NULL;       

// Insert 6 at the end,

append(&head, 6); 

//6->NULL     

// Insert 7 as head 

push(&head, 7); 

//7->6->NULL       

// Insert 1 as head. 

push(&head, 1); 

//1->7->6->NULL      

// Insert 4 at the end  

append(&head, 4); 

//1->7->6->4->NULL       

// Insert 8, after 7

insertAfter(head->next, 8); 

//1->7->8->6->4->NULL      

cout<<"Created Linked list is: "; 

printList(head);       

return 0; 

}

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

How to Remove a Node From a Singly Linked List?

You can delete a node from 3 different locations, they are:

• From the beginning
• From the last  
• From a specific position after a given node

Code:

//A c++ code to insert a node 

//in singly linked list

#include <bits/stdc++.h>

using namespace std;

//A class to create node

class Node{

public:

int data;

Node* next;

};

//insert a node at the beginning

void push(Node** head, int newdata)

{

//create newnode

Node* newnode = new Node();

newnode->data = newdata;//put in data

newnode->next = (*head);//link newnode with head

(*head) = newnode;//changing head

}

//A function to delete a node

void deleteNode(Node** head, int key)

{

Node* temp = *head;//creating temp node

Node* prev = NULL;//creating prev node

//checking if node to be deleted is head the node

if (temp != NULL && temp->data == key)

{

*head = temp->next;//changing head

delete temp; //delete node

return;

}

else

{

//traversing to find key to delete

while (temp != NULL && temp->data != key)

{

prev = temp;

temp = temp->next;

}

if (temp == NULL)

return;

prev->next = temp->next;

delete temp;//delete node

}

}

// This function prints contents of

// linked list starting from the

// given node

void printList(Node* node)

{

while (node != NULL)

{

cout << node->data << " ";

  node = node->next;

}

}

// Driver code

int main()

{    

// Start with the empty list

Node* head = NULL; 

// Add elements in linked list

push(&head, 7);

push(&head, 1);

push(&head, 3);

push(&head, 2);

puts("Created Linked List: ");

printList(head);

deleteNode(&head, 1);

puts("\nLinked List after Deletion of 1: "); 

printList(head);  

return 0;

}

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

What Are the Benefits of a Singly Linked List?

• You can perform operations like insertion and deletion with ease
• It is a dynamic data structure, i.e., it does not have a fixed size
• It doesn’t require the movement of nodes for insertion and deletion
• It doesn’t need elements to be stored in consecutive memory spaces
• It does not waste space as it uses space according to the requirement

What Are the Limitations of a Singly Linked List?

• It requires more storage space because it also stores the next pointer with data
• If you have to reach any node, then you have to go through every node before it
• You can not traverse it from anywhere but the head node
• It requires a different amount of time to access any elements
• Sorting is complex in this linked list

Next Steps

“Doubly Linked list” can be your next stop. Doubly Linked lists are made up of nodes that point to the next and previous nodes. Doubly Linked lists are dynamic and have faster insertion/deletion time complexities. A doubly linked list is faster at reverse traversal.

If you are perhaps looking to build a career in software development, explore Simplilearn in partnership with Purdue University & in collaboration with IBM. Featuring ask-me-anything sessions from IBM, a masterclass from Purdue, and many great benefits, this program will give you the work-ready software development training you need to succeed today. 

If you have any questions about this tutorial, please feel free to leave them in the comment section below. Our 24/7 expert team will make sure to answer all your queries for you at the earliest.