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.
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;
}
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;
}
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.
