The Complete Guide to Implement a Singly Linked List

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. It is used to do a slideshow or some basic operations on a notepad like undo and redo.

In this “singly linked list” tutorial, you will look into the following topics:

  • How to implement a singly linked list?
  • What operations can you perform on a singly linked list?
  • How to insert a node in a singly linked list?
  • How to remove a node from a singly linked list?
  • What are the benefits of a singly linked list?
  • What are the limitations of a singly linked list?

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

How to Implement a Singly Linked List?

singly_linked_list-implementation-img1

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;

}

singly_linked_list-implementation-img2

What Operations Can You Perform on a Singly Linked List?

singly_linked_list-operation-img1

You can perform two operations on a singly linked list:

  • Insertion
  • Deletion 

How to Insert a Node in a Singly Linked List?

singly_linked_list-insertion-img1

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; 

}

singly_linked_list-insertion-img2

How to Remove a Node From a Singly Linked List?

singly_linked_list-deletion-img1

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;

}

singly_linked_list-deletion-img2.

Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE CoursesEnroll Now
Stand Out From Your Peers this Appraisal Season

What Are the Benefits of a Singly Linked List?

singly_linked_list-benefits-img1

  • 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?

singly_linked_list-limitation-img1.

  • 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
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

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.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.