Singly Linked List actually follows the same principles as a generic Linked List. A generic link list is termed a singly linked list as we can traverse through the link list only from the beginning.
In a singly linked list, each node maintains a pointer to hold the base address of the next node. The last element of the list does not point to any node, hence the pointer of the last node is null. A pointer variable is used to point to the first element of the linked list. If the list is empty, this pointer holds NULL value. We can visualize a singly linked list as shown below.
An example of a Singly Linked List
A node of a singly linked list can be represented as shown in the following code snippet, where the data part of the node is an integer element and the pointer references to a similar type of node.
typedef struct Node {
int data;
struct Node *next;
} node;
Operations on Linked List
The discussion on the linked list till now talks about how the data would be bound together within a node. But equal importance should be given to how we can manage those data after they are stored within the nodes. In this context, we can think of certain operations on linked lists so that data management becomes easy.
Following subsections discuss how we can perform some basic as well as some sophisticated operations on the linked list.
Creating a node of a linked list
Node creation is the basic function or operation that you need to do with a linked list. Following is the function which you can write to create a node. This function takes up the data which has to be stored within the node and it returns the base address of the newly created node.
node* createNode(int data)
{
node* temp;
temp = (node*)malloc(sizeof(node));
temp->next = NULL;
temp->data = data;
return temp;
}
Please note that once we have allocated the memory for the node, the address part i.e. temp->next is set with NULL. It is so because the newly created node has nothing to point out as such.
Hence we can use this function every time we want to create a new node in the linked list.
Creating the first-ever node of a linked list
The following code shows how you can create the very first node of a linked list. The code uses the function node* createNode(int) as discussed above. Moreover, we need to assume that there is a global definition of struct Node type as shown at the top of this tutorial. For the purpose of simplicity, we are just omitting the header file includes.
int main(void)
{
node* head;
int data = 10;
//createNode defined above
head = createNode(data);
return 0;
}
This code will create a linked list with only one node with a data part value of 10. Please note that the pointer head just points to the first node of the linked list. At this point, the linked list will look like the following figure.
Fig: Linked List creation
Please note that at this point, from the outer world, the linked list can only be accessed through the head. Hence if due to any reason, this head is made to free, then the entire linked list would be inaccessible in the primary memory.
Inserting a node at the beginning of a linked list
At the time of inserting a new node at the beginning, there may be two scenarios: (i) the list is empty and (ii) the list contains at least one element.
(i) Empty List: If the list is empty, the new node is added as the only node on the list.
(ii) Non-empty List: If the list is not empty, the new node is added at the beginning of the list. Hence, the next pointer of the newnode points to the first node of the previous list, and the head pointer points to the newly created node as shown below.
The following describes the function void insertAtBegin(node **head, int item).
void insertAtBegin(node **head, int item)
{
node *newnode = (node *)malloc(sizeof(node));
newnode->data = item;
if(*head == NULL)
newnode->next=NULL;
else
newnode->next = *head;
*head = newnode;
}
Traversing a linked list
In-Order Traversal: Let us suppose that, we have an already existing linked list pointed by a pointer head. Hence head points to the very first node of the linked list.
The following describes the function void traverseInOrder(node *head).
void traverseInOrder(node *head)
{
while(head != NULL)
{
printf(" %d ", head->data);
head = head->next;
}
}
Reverse-Order Traversal: In this list, the pointer head points to the first element of the list. Hence, the list can be traversed from the beginning as we have discussed earlier. To print this list in reverse order, a recursive method is used.
The following describes the function void traverseInReverseOrder(node *head).
void traverseInReverseOrder(node *head)
{
if(head->next != NULL)
traverseInReverseOrder(head->next);
printf(" %d ", head->data);
}
Searching a specific data element in a linked list
In this context, we are assuming that the list contains unique elements. This function returns the node where data matches with the search key. If the element does not exist in this list, it returns null. This loop iterates until the pointer reaches the end of the list.
node * searchInList(node *head, int key)
{
while((head != NULL) && (head->data != key))
head = head->next;
return head;
}
Inserting a node at the end of a linked list
Let us consider the same linked list pointed by a pointer head. Hence head points to the very first node of the linked list.
Empty List: If the list is empty, the node is added in a similar way as discussed in insertAtBegin() function.
Non-empty List: If the list is non-empty, first we have to reach the last node. As the pointer head points to the first element of the list, using the iterative approach we have to move to the last node. The next pointer of the last node is NULL. Hence, we have to update this pointer to the head address of the newnode. The steps are shown in the following figures.
The following code describes a function void insertAtEnd(node *head, int item), which takes up the head of the existing linked list and the data for the new node to be created as the arguments and ultimately create a new node with the specified data and inserts the new node at the end of the existing linked list.
void insertAtEnd(node **head, int item)
{
node *temp;
node *newnode = (node *)malloc(sizeof(node));
newnode->data = item;
newnode->next=NULL;
if(*head == NULL)
*head = newnode;
else
{
temp = *head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
}
Inserting a node after a specific node of an already existing linked list
The function searchInList() returns a node where a search key is found in the list. The new node is added after this node. The function is shown below.
void insertAfterElement(node **head, int item, int after)
{
node *newnode;
node *curloc = searchInList(*head, after);
if (curloc == (node *) NULL)
return;
newnode = (node *)malloc(sizeof(node));
newnode->data = item;
newnode->next = curloc->next;
curloc->next= newnode;
}
Deleting a starting node of an already existing linked list
This is a very simple function, first, we have to check if the list is empty or not. If the list is empty, the function has nothing to do. If the list is not empty, the head pointer points to the second node of the list. If the list contains only one node, the head pointer is set NULL automatically.
void deleteFromBegin(node **head)
{
node *temp;
if(*head == NULL)
return;
else
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
Deleting the last node of an already existing linked list
To delete the last node of a linked list, if we reach the end of the list, we have to update the next pointer of the previous node as the current node gets deleted.
As in a singly linked list, we don't have any pointer to move back to the previous node, we have to stop at the previous node of the last node.
The following function shows how the last node is deleted from the linked list.
void deleteFromEnd(node **head)
{
node *temp, *loc;
if(*head == NULL)
return;
else if((*head)->next == (node *)NULL)
{
temp = *head;
*head = NULL;
free(temp);
}else
{
loc = *head;
temp = (*head)->next;
while(temp->next != NULL)
{
loc = temp;
temp = temp->next;
}
loc->next = NULL;
free(temp);
}
}
Deleting a node after a specific node of an already existing linked list
To delete a node after a node, first, we have to reach the node, then we can delete the next node. The function searchInList() returns the node loc where we get a match of the search key after. To delete the next node, we have to update the next pointer of loc. If the function searchInList() returns NULL, it indicates that the key is not available in the linked list. Hence, the function returns without any modification to the list. If loc is the last node of the list, the function has nothing to do with the list and hence returns. If the loc is not NULL and loc is not the last element of the list, next pointer of the loc is updated as shown in the following function.
void deleteAfterElement(node **head, int after)
{
node *temp, *loc;
loc = searchInList(*head, after);
if (loc == (node *)NULL)
return;
if (loc->next == NULL)
return;
temp = loc->next;
loc->next = temp->next;
free(temp);
}
Deleting an entire linked list
To delete an entire list, we are declaring a pointer temp to point to a node of the list. In this function, we are starting from the first node and using an iterative approach one node is deleted in every iteration. The loop stops when we reach the end of the list.
The following function shows the technique.
void deleteList(node **head)
{
node *temp;
while(*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
Complete Code
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.