Single Linked List is a fundamental data structure in the C programming language. It allows us to store and organize a collection of data elements in a sequential manner. In a Single Linked List, each element is represented by a node, which contains both the data and a pointer to the next node in the list.
What is Single Linked List?
A Single Linked List is a linear data structure where each node contains two fields – data and next. The data field stores the actual value of the node, while the next field stores the address of the next node in the sequence. The first node of the list is called the “head” or “front” of the list. The last node’s next field points to NULL, indicating the end of the list.
struct Node {
int data;
struct Node *next;
};
Operations on Single Linked List
There are several operations that can be performed on a Single Linked List. These operations include insertion, deletion, and display. Before implementing these operations, we need to set up an empty list by declaring the necessary variables and defining the Node structure.
Setting Up an Empty List
To set up an empty list, we need to declare a pointer to the head of the list and initialize it to NULL.
struct Node *head = NULL;
Insertion
Insertion is the process of adding a new node to the linked list. It can be done at the beginning, end, or at a specific location in the list.
Insertion at the Beginning of the List
To insert a new node at the beginning of the list, we create a new node with the given value and set its next field to the current head of the list. Then, we update the head to point to the new node.
Insertion at the End of the List
To insert a new node at the end of the list, we create a new node with the given value and set its next field to NULL. If the list is empty, we update the head to point to the new node. Otherwise, we traverse the list until we reach the last node and update its next field to point to the new node.
Insertion at a Specific Location in the List
To insert a new node after a specific node in the list, we first check if the list is empty. If it is, we set the next field of the new node to NULL and update the head to point to the new node. If the list is not empty, we traverse the list until we find the node after which we want to insert the new node. We then update the next field of the new node to point to the next node of the current node, and update the next field of the current node to point to the new node.
Deletion
Deletion is the process of removing a node from the linked list. It can be done from the beginning, end, or a specific location in the list.
Deletion from the Beginning of the List
To delete a node from the beginning of the list, we check if the list is empty. If it is, we display a message indicating that the list is empty. If the list is not empty, we create a temporary pointer and set it to the head of the list. We then update the head to point to the next node, and free the memory occupied by the deleted node.
Deletion from the End of the List
To delete a node from the end of the list, we check if the list is empty. If it is, we display a message indicating that the list is empty. If the list is not empty, we create two temporary pointers – one pointing to the current node and another pointing to the previous node. We traverse the list until we reach the last node, while keeping track of the previous node. We then update the next field of the previous node to NULL and free the memory occupied by the last node.
Deletion of a Specific Node from the List
To delete a specific node from the list, we first check if the list is empty. If it is, we display a message indicating that the list is empty. If the list is not empty, we create two temporary pointers – one pointing to the current node and another pointing to the previous node. We traverse the list until we find the node to be deleted or reach the end of the list. If we find the node, we update the next field of the previous node to point to the next node of the current node, and free the memory occupied by the current node. If we reach the end of the list without finding the node, we display a message indicating that the node was not found.
Display
Displaying a Single Linked List involves traversing the list and printing the values of each node. We start from the head of the list and keep moving to the next node until we reach the end of the list. We print the value of each node along with an arrow pointing to the next node, and finally, we print NULL to indicate the end of the list.
void display() {
if (head == NULL) {
printf("List is Empty!!!\n");
return;
}
struct Node *temp = head;
while (temp != NULL) {
printf("%d ---> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
Advantages over Arrays:
- Dynamic Size: SLLs can change their size during execution.
- Ease of Insertion/Deletion: Unlike arrays, there’s no need to shift elements after insertion or deletion.
Disadvantages:
- Memory Overhead: Each node requires extra memory for the
nextpointer. - No Direct Access: Elements can’t be accessed directly as in arrays; a sequential search is mandatory.
- Reverse Traversing: SLLs can’t be traversed in reverse without additional data structures or algorithms.
Illustrations:
- Node Representation:
Imagine a chain where each link is a node. The link contains a data compartment and another smaller compartment pointing to the next link. In a computer’s memory, these “links” or nodes aren’t necessarily one after the other, but they’re connected by their pointers, forming a logical sequence.
- Insertion:
Visualize adding a new link to the start of our chain. You don’t reposition the entire chain. Instead, you merely adjust where the new starting point (or head) of the chain is.
- Deletion:
Consider removing a defective link from our chain. Once identified, you disconnect it by reattaching its previous link to its subsequent one. Then, you dispose of the faulty link.
Full Code of a single link list :
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n
5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
}
void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
Recursive insertion and traversal linked list
Insertion
// Function to insert a new node at the
// end of linked list using recursion.
Node* insertEnd(Node* head, int data)
{
// If linked list is empty, create a
// new node (Assuming newNode() allocates
// a new node with given data)
if (head == NULL)
return newNode(data);
// If we have not reached end, keep traversing
// recursively.
else
head->next = insertEnd(head->next, data);
return head;
}
Traversal
void traverse(Node* head)
{
if (head == NULL)
return;
// If head is not NULL, print current node
// and recur for remaining list
printf("%d ", head->data);
traverse(head->next);
}
Time and Space Complexity of Single Linked List Operations in C with Loops
Understanding the efficiency of algorithms and data structures is paramount for computer scientists. When analyzing Single Linked Lists (SLL), it’s vital to consider both time (how long operations take) and space (how much memory is used) complexities.
Let’s dissect the time and space complexity of common operations in a SLL with loop iterations:
1. Insertion:
a. At the Beginning:
Time Complexity: O(1)
Inserting at the beginning doesn’t require traversal. You’re merely updating the head of the list.
b. At the End:
Time Complexity: O(n)
You must traverse the entire list of n elements to find the last node.
2. Deletion:
a. From the Beginning:
Time Complexity: O(1)
Just like insertion at the beginning, deletion here is constant time.
b. From the End:
Time Complexity: O(n)
To delete the last node, you must traverse to the end of the list.
3. Traversal:
Time Complexity: O(n)
Iterating over each element in the list requires linear time.
4. Searching:
Time Complexity: O(n)
In the worst case, you might have to traverse the entire list to find an element or ascertain that it’s not there.
5. Space Complexity:
For the list itself:
Space Complexity: O(n)
Each of the n nodes in the list requires space for its data and a pointer to the next node.
For the operations:
Space Complexity: O(1)
Most SLL operations (insertion, deletion, traversal, searching) only require a constant amount of additional space (like temporary pointers). The operations themselves don’t scale with the size of the list.
Loops and Linked List:
Loops introduce a degree of complexity in evaluating the performance of operations on linked lists. Loops in this context refer to cycles — where a node in a linked list points back to an earlier node, creating a cycle.
Detecting a loop:
Time Complexity: O(n)
The Floyd’s Cycle-Finding Algorithm, also known as the “tortoise and the hare” algorithm, can be used. Here, two pointers move through the list at different speeds. If there’s a cycle, they will meet at some point.
Removing a loop:
Time Complexity: O(n)
Once a loop is detected using the above algorithm, one can find the start of the loop and then break it.
In conclusion, single-linked lists provide dynamic memory allocation, which is a boon. However, their linear structure can be a limitation for certain operations. Knowing the complexities aids in making informed decisions when implementing algorithms and systems. Always remember that the presence of a loop (cycle) can complicate operations and should be handled with care.
Time and Space Complexity of Single Linked List Operations in C with Recursion
Understanding the intricacies of Single Linked Lists (SLL) when combined with recursive methods is pivotal in many algorithmic applications. Recursive operations can be elegant and concise, but they often come with certain performance implications. Here we analyze the time and space complexity of recursive operations on a Single Linked List in C.
1. Traversal:
Recursively visiting every node until a NULL is reached essentially constitutes a traversal.
Time Complexity: O(n)
Each node is visited once, making it linear time complexity.
Space Complexity: O(n)
Every recursive call is added to the call stack, leading to space for n calls in the worst-case scenario. This makes the recursive approach use more space compared to an iterative approach (which would be O(1)).
2. Insertion:
a. At the Beginning:
Time Complexity: O(1)
Insertion at the beginning is constant time, even with recursion, as no traversal is needed.
b. At the End:
Time Complexity: O(n)
You’d recursively traverse to the end of the list and then insert, making it a linear time operation.
3. Deletion:
a. From the Beginning:
Time Complexity: O(1)
Deletion at the start is a constant time operation irrespective of recursion.
b. From the End:
Time Complexity: O(n)
Similar to insertion at the end, deleting the last node requires traversal to the penultimate node, which takes linear time.
4. Searching:
Searching can also be done recursively. The base case is either finding the node or reaching the end of the list (NULL).
Time Complexity: O(n)
In the worst-case scenario, the search operation may have to traverse the entire list.
5. Reversing:
A common algorithmic challenge is to reverse a linked list recursively.
Time Complexity: O(n)
The list is traversed once during the reversal.
Space Complexity: O(n)
Each recursive call is added to the call stack, taking up space.
6. Space Complexity for Recursive Operations:
In general, the space complexity for recursive operations on a Single Linked List is O(n). This is because of the function call stack. Every recursive function call is added to the call stack and consumes memory. Therefore, if you’ve n recursive calls, you’ll consume space for n calls on the stack.
Conclusion:
While recursive methods can simplify operations and make the code more readable, they do not always translate to the most efficient solutions, especially in terms of space complexity. Iterative methods for linked list operations, on the other hand, often have a space complexity of O(1). However, for some operations, like reversing a linked list, the recursive approach can be more intuitive.
0 Comments