SINGLY LINKED LIST

 SINGLY LINKED LIST

The singly linked list is a data structure that contains two parts, i.e., one is the data part, and the other one is the address part, which contains the address of the next or the successor node. The address part in a node is also known as a pointer. The pointer that holds the address of the initial node is known as a head pointer.

Operations on Singly Linked List:

 There are various operations which can be performed on singly linked list. A list of all such operations is given below. 

Node Creation:

struct node 

{

                    int data;

struct node *next; 

}

struct node *head, *ptr; 

ptr = (struct node *)malloc(sizeof(struct node *)); 

Traversing a Linked List:

Traversing a linked list means accessing the nodes of the list in order to perform some operation.Traversing means visiting each node of the list once in order to perform some operation on that.

linked list always contains a pointer variable START which stores the address of the first node of the list.

End of the list is marked by storing NULL or –1

ptr = head;

while (ptr!=NULL)

{

ptr = ptr -> next; 

}

Algorithm for traversing a linked list:

Step 1: [INITIALIZE] SET PTR = START

Step 2: Repeat Steps 3 and 4 while PTR != NULL

Step 3: Apply Process to PTR DATA

Step 4: SET PTR = PTR NEXT

[END OF LOOP]

Step 5: EXIT

Algorithm to print the number of nodes in a linked list:

Insertion:

The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories. 

1. Inserting at Beginning 

2. Inserting at the End of the List 

3. Inserting after specified node

4. Inserting before specified node

1.Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to insert a new node in the list at beginning.

• Allocate the space for the new node and store data into the data part of the node. This will be done by the following statements. 

ptr = (struct node *) malloc(sizeof(struct node *));

ptr → data = item

• Make the link part of the new node pointing to the existing first node of the list. This will be done by using the following statement.

ptr->next = head

• At the last, we need to make the new node as the first node of the list this will be done by using the following statement.

head = ptr;

Algorithm 

Function for inserting element at beginning of the list

struct node *insert_beg(struct node *start)

{

struct node *new_node;

int num;

printf(“\n Enter the data : “);

scanf(“%d”, &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

new_node -> next = start;

start = new_node;

return start;

}

2.Inserting at the End of the List

Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes will be done in the linked list.

    In Step 6, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list.

     In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node.

     Remember that the NEXT field of the new node contains NULL, which signifies the end of the linked list.

struct node *insert_end(struct node *start)

{

struct node *ptr, *new_node;

int num;

printf(“\n Enter the data : “);

scanf(“%d”, &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

new_node -> next = NULL;

ptr = start;

while(ptr -> next != NULL)

ptr = ptr -> next;

ptr -> next = new_node;

return start;

}

3.Inserting a Node After a Given Node in a Linked List

• In Step 5, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list.
• Then we take another pointer variable PREPTR which will be used to store the address of the node preceding PTR. Initially, PREPTR is initialized to PTR. 
• So now, PTR, PREPTR, and START are all pointing to the first node of the linked list.
• In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. We need to reach this node because the new node will be inserted after this node.
• Once we reach this node, in Steps 10 and 11, we change the NEXT pointers in such a way that new node is inserted after the desired node.

ex: Suppose we want to add a new node with value 9 after the node containing data 3.

struct node *insert_after(struct node *start)

{

struct node *new_node, *ptr, *preptr;

 int num, val;

printf(“\n Enter the data : “);

scanf(“%d”, &num);

printf(“\n Enter the value after which the data has to be inserted : “);

scanf(“%d”, &val);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr = start;

preptr = ptr;

while(preptr -> data != val)

{

preptr = ptr;

ptr = ptr -> next;

}

preptr -> next=new_node;

new_node -> next = ptr;

return start;

}

 

4.Inserting a Node Before a Given Node in a Linked List

1. In Step 5, we take a pointer variable PTR and initialize it with START. 
2. That is, PTR now points to the first node of the linked list. 
3. Then, we take another pointer variable PREPTR and initialize it with PTR. 
4. So now, PTR, PREPTR, and START are all pointing to the first node of the linked list.
5. In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. We need to reach this node because the new node will be inserted before this node.
6. Once we reach this node, in Steps 10 and 11, we change the NEXT pointers in such a way that the new node is inserted before the desired node.

Ex: Consider the linked list shown in Fig. Suppose we want to add a new node with value 9 before the node containing 3.

struct node *insert_before(struct node *start)

{

struct node *new_node, *ptr, *preptr;

int num, val;

printf(“\n Enter the data : “);

scanf(“%d”, &num);

printf(“\n Enter the value before which the data has to be inserted : “);

scanf(“%d”, &val);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr = start;

while(ptr -> data != val)

{

ptr = ptr -> next;

}

preptr -> next = new_node;

new_node -> next = ptr;

return start;

}

Deletion 

The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories. 

1. Deleting at Beginning 

2. Deleting at the End of the List 

3. Deleting after specified node.

UNDERFLOW: Underflow is a condition that occurs when we try to delete a node from a linked list that is empty. This happens when START = NULL or when there are no more nodes to delete.

1. Deleting at Beginning

In Step 1, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm.

if there are nodes in the linked list, then we use a pointer variable PTR that is set to point to the first node of the list.

For this, we initialize PTR with START that stores the address of the first node of the list. In Step 3, START is made to point to the next node in sequence and finally the memory occupied by the node pointed by PTR (initially the first node of the list) is freed and returned to the free pool.

2. Deleting at the End of the List

In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 

In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR. 

Once we reach the last node and the second last node, we set the NEXT pointer of the second last node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned back to the free pool.

3. Deleting after specified node.

Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 

In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR. 

Once we reach the node containing VAL and the node succeeding it, we set the next pointer of the node containing VAL to the address contained in next field of the node succeeding it. 

The memory of the node succeeding the given node is freed and returned back to the free pool.

Searching in singly linked list:

Searching is performed in order to find the location of a particular element in the list. Searching any element in the list needs traversing through the list and make the comparison of every element of the list with the specified element. If the element is matched with any of the list element then the location of the element is returned from the function.

ex:If we have VAL = 4, then the flow of the algorithm can be explained as shown in the figure.

In Step 1, we initialize the pointer variable PTR with START that contains the address of the first node. 

In Step 2, a while loop is executed which will compare every node’s DATA with VAL for which the search is being made. 

If the search is successful, that is, VAL has been found, then the address of that node is stored in POS and the control jumps to the last statement of the algorithm. 

However, if the search is unsuccessful, POS is set to NULL which indicates that VAL is not present in the linked list.

SINGLY LINKED LIST ADVANTAGE 

1) Insertions and Deletions can be done easily. 

2) It does not need movement of elements for insertion and deletion. 3) It space is not wasted as we can get space according to our requirements. 

4) Its size is not fixed. 

5) It can be extended or reduced according to requirements. 

6) Elements may or may not be stored in consecutive memory available 

7) It is less expensive.

DISADVANTAGE 

1) It requires more space as pointers are also stored with information. 

2) Different amount of time is required to access each element. 

3) If we have to go to a particular element then we have to go through all those elements that come before that element. 

4) we can not traverse it from last & only from the beginning. 

5) It is not easy to sort the elements stored in the linear linked list. 

Applications of Linked 

Lists Graphs, queues, and stacks can be implemented by using Linked List.