Summary
Introduction to singly linked list
Singly linked list is a basic linked list type. Singly linked list is a collection of nodes linked together in a sequential way where each node of singly linked list contains a data field and an address field which contains the reference of the next node. Singly linked list can contain multiple data fields but should contain at least single address field pointing to its connected next node.
To perform any operation on a linked list we must keep track/reference of the first node which may be referred by head pointer variable. In singly linked list address field of last node must contain a NULL value specifying end of the list.
Basic structure of a singly linked list
Each node of a singly linked list follows a common basic structure. In a node we can store more than one data fields but we need at least single address field to store the address of next connected node.
struct node {
int data; //Data part
struct node * next; //Address part
};
Advantages of Singly linked list
There are several points about singly linked list that makes it an important data structure.- Singly linked list is probably the most easiest data structure to implement.
- Insertion and deletion of element can be done easily.
- Insertion and deletion of elements doesn't requires movement of all elements when compared to an array.
- Requires less memory when compared to doubly, circular or doubly circular linked list.
- Can allocate or deallocate memory easily when required during its execution.
- It is one of most efficient data structure to implement when traversing in one direction is required.
Disadvantages of Singly linked list
After seeing the advantages of singly linked list. Singly linked list also has some disadvantages over other data structures.- Id uses more memory when compared to an array.
- Since elements are not stored sequentially hence requires more time to access each elements of list.
- Traversing in reverse is not possible in case of Singly linked list when compared to Doubly linked list.
- Requires O(n) time on appending a new node to end. Which is relatively very high when compared to array or other linked list.
Creation of a singly linked list
To create a new node or to allocate memory dynamically we use malloc() function. malloc() function returns NULL value if memory is not allocated else returns a newly allocated memory address.
void createSinglyLinkedList()
{
struct node * head; //head pointer keeps the address of first node
head = (struct node *)malloc(sizeof(struct node));
/*
* If memory is not allocated
*/
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else //If memory is allocated
{
printf("List created successfully");
}
}
See detailed explanation with program how to create a singly linked list.
Traversal of a singly linked list
To traverse entire list, start from the head or starting node and in each step advance the position of head pointer to next pointing node till a NULL or empty node is reached.
void traverseList(struct node *head)
{
struct node *temp = head; //head contains the address of first node
while(temp != NULL)
{
printf("Data = %d\n", temp->data);
/* Advances the position of temp pointer */
temp = temp->next;
}
}
See detailed explanation with program how to traverse a singly linked list.
Insertion of a new node at beginning of list
To insert a new node at the beginning of list first create a new node. Then connect the new node to the head node i.e. new node should point to the first node. After connecting new node to head node make sure that the head node now points to the newly created node.
void insertNodeAtBeginning(struct node *head)
{
struct node * newNode;
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->data = 10; //Assign some data to the data part of the node
newNode->next = head; //Links new node to the first node of list
head = newNode; //new node is the head node now.
printf("New node added successfully at the beginning of list.");
}
}
See detailed explanation with program how to insert a new node at the beginning of singly linked list.
Insertion of new node at end of list
To insert a new node at the end of list first traverse to the last node. Then create a new node and connect with the last node. Make sure that the last node points to the newly created node and newly created node points to NULL.
void insertNodeAtEnd(struct node *head)
{
struct node *newNode, *temp;
/*
* Check if the list is empty
*/
if(head == NULL)
{
printf("Can't add a node at the end of an empty list.");
}
else
{
temp = head;
/* Traverses to last node of the list */
while(temp->next != NULL)
{
temp = temp->next;
}
newNode = (struct node *)malloc(sizeof(struct node));
/*
* If memory is not allocated
*/
if(newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->data = 10; //Assign some data to newly create node.
newNode->next = NULL; //Since new node is last node hence points to NULL
temp->next = newNode; //The previous last node now points to newly created node
printf("Node added successfully at the end of list.");
}
}
}
See detailed explanation with program how to insert a new node at the end of singly linked list.
Insertion at n position of the list
To insert a new node at nth position in the list. First traverse to n-1 position. Create a new node and make sure that the new node points to n+1th node and n-1th node points to the newly created node.
void insertNodeAtN(struct node *head)
{
struct node *newNode, *temp;
int count;
if(head == NULL)
{
printf("Can't insert a new node in an empty list.");
}
else
{
temp = head;
/*
* Traverse to n-1 position
*/
for(count=1; count<n-1 && temp!=NULL; count++)
{
temp = temp->next;
}
newNode = (struct node*)malloc(sizeof(struct node));
/*
* If memory is not allocated
*/
if(newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->data = 10; //Assign some data to new node
newNode->next = temp->next; //New node points to n+1 node
temp->next = newNode; //n-1 node points to new node
printf("Node added successfully at %d position", n);
}
}
}
See detailed explanation with program how to insert a new node at the n position in singly linked list.
Deletion from beginning of list
To delete node from the beginning of list, first copy the reference of first node to some temp variable. Then make sure that the head node now points to 2nd node of the list. Now clear the memory allocated by the 1st node i.e. temp node. To clear resources allocated in memory use free() function.
void deleteNodeFromBeginning(struct node *head)
{
struct node * toDelete;
/*
* Check if the list is empty
*/
if(head == NULL)
{
printf("Unable to delete from an empty list.");
}
else
{
toDelete = head; //contains reference of 1st node
head = head->next; //head now points to 2nd node
free(toDelete); //clears all resources used by 1st node
printf("Successfully deleted first node of list.");
}
}
See detailed explanation with program how to delete node from beginning of a singly linked list.
Deletion from end of list
To delete a node from the end of list, first traverse to n-1th position then copy the reference of nth node. Make sure that the n-1th node points to NULL. Now delete the nth node from the list.
void deleteNodeFromEnd(struct node *head)
{
struct node *lastNode, *secondLastNode;
/*
* Check if the list is empty
*/
if(head == NULL)
{
printf("Can't delete from an empty list.");
}
else
{
/*
* Traverses to the last node
*/
lastNode = head;
while(lastNode->next != NULL)
{
secondLastNode = lastNode; //contains address of n-1 node
lastNode = lastNode->next; //contains address of last node i.e n node
}
/*
* If there is only single node in the list
*/
if(lastNode == head)
{
head = NULL;
}
else
{
secondLastNode->next = NULL; //Makes second last node as last node
}
free(lastNode); //deletes the last node from memory
printf("Successfully deleted last node from the list.");
}
}
See detailed explanation with program how to delete node from end of a singly linked list.
Deletion from n position in list
To delete nth node from the list, first traverse to n-1th node and copy the reference of nth node to a temp variable. Make sure that the n-1th node now points to n+1th node. After that free all resources allocated by nth node.
void deleteNodeFromN(struct node *head)
{
struct node *nNode, *temp;
int count;
/*
* Check if the list is empty
*/
if(head == NULL)
{
printf("Unable to delete from an empty list.");
}
else
{
temp = head;
/* Traverse to n-1 node */
for(count=1; count<n-1 && temp!=NULL; count++)
{
temp = temp->next;
}
/* Check if the given position n is valid */
if(temp != NULL)
{
printf("Unable to delete at specified position.");
}
else
{
nNode = temp->next;
temp->next = nNode->next; //n-1 node points to n+1 node
free(nNode); //Clears all memory used by nth node
printf("Successfully deleted node at %d position.", n);
}
}
}
See detailed explanation with program how to delete node from middle of a singly linked list.Deletion of entire list
void deleteList(struct node *head)
{
struct node *nextNode, *curNode;
/*
* Check if the list is empty
*/
if(head == NULL)
{
printf("Can't delete list is already empty.");
}
else
{
curNode = head;
while(curNode != NULL)
{
nextNode = curNode->next;
free(curNode);
curNode = nextNode;
}
head = NULL;
printf("Successfully deleted all nodes of list.");
}
}
See detailed explanation with program how to delete all nodes of a singly linked list.
Count total number of elements
To count total number of elements we just need to traverse entire list and increment value of count variable in each repetition.
void countList(struct node *head)
{
struct node *temp;
int count = 0;
temp = head;
/*
* Traverses entire list and counts total number of nodes
*/
while(temp != NULL)
{
count++; //Increments count
temp = temp->next; //Moves to next node
}
printf("Total number of nodes = %d", count);
}
See detailed explanation with program how to count total number of nodes in a singly linked list.
Reverse entire list
void reverseList(struct node *head)
{
struct node *previousNode, *curNode;
/*
* Checks if the list is empty
*/
if(head == NULL)
{
printf("Unable to reverse an empty list.");
}
else
{
previousNode = head;
curNode = head->next;
head = head->next;
previousNode->next = NULL; //First node becomes last node
while(head != NULL)
{
head = head->next;
curNode->next = previousNode;
previousNode = curNode;
curNode = head;
}
head = previousNode; //Last node becomes the head node
printf("Entire list reversed successfully.");
}
}
See detailed explanation with program how to reverse a singly linked list.