Showing posts with label mskuthar. Show all posts
Showing posts with label mskuthar. Show all posts

Circular Linked List

A circular linked list is one in which the nodes are linked in such a way that they form a circle, with the last node pointing to the first node. There are no nodes in a circular linked list that have a null address space. 



There are two types:

1) Singly Linked List: 

  • It establishes a link to the first node by substituting the address of the first node for NULL. 
  • With the help of circular link generation, the Singly Linked List allows you to access the preceding node.

2) DLL (Doubly Linked List): 

  • A DLL (Doubly Linked List) has an extra pointer called the prior pointer.

The Benefits of a Singly and Doubly Linked List
  • Even if traversing ahead from a specific place, aids in obtaining earlier node information.
  • DLL is capable of traversing both forward and backward.
  • Due to the prior pointer, DLL is faster in retrieving previous node information.
  • Because it does not have a preceding pointer, a singly linked list takes up less space than a doubly linked list.

Algorithm

Addition of node at beginning of Circular linked list

  • Step 1. START
  • Step 2. Store the data to create a linked list.
  • Step 3. Enter the element to be at beginning of the list.
  • Step 4. Swap the address (header) of the first node.
  • Step 5. The first node address is swapped with the second node repeat till the last node address is swapped with the new first node address.
  • Step 6. STOP
Program
#include <stdio.h>  
#include <stdlib.h>   
struct node  
{  
    int data;  
    struct node *link;  
};  
   
struct node *head = NULL, *x, *y, *z;  
void ins_at_beg();  
void display();  
  
int main()  
{   int c;  
 x = (struct node*)malloc(sizeof(struct node));  
    printf("\n Enter the data to create linked list:");  
    scanf("%d", &x->data);  
    x->link = x;  
    head = x;  
    printf("\n If you wish to continue press 1 otherwise 0:");  
    scanf("%d", &c);  
    while (c != 0)  
    {  
        y = (struct node*)malloc(sizeof(struct node));  
        printf("\n Enter the data:");  
        scanf("%d", &y->data);  
        x->link = y;  
        y->link = head;  
        x = y;  
        printf("\n If you wish to continue press 1 otherwise 0:");  
        scanf("%d", &c);   
    }  
    ins_at_beg();   
    display();  
}  
  
void ins_at_beg()  
{  
    x = head;  
    y = (struct node*)malloc(sizeof(struct node));  
    printf("\n Enter the data to insert at beggining:");  
    scanf("%d", &y->data);  
    while (x->link != head)  
    {  
        x = x->link;  
    }  
    x->link = y;  
    y->link = head;  
    head = y;  
}  
  
void display()  
{  
       if (head == NULL)  
        printf("\n List is empty");  
    else  
    {  
        x = head;  
        while (x->link !=  head)  
        {   
            printf("%d->", x->data);  
            x = x->link;  
        }  
        printf("%d", x->data);  
    }   
      }  

Output
Enter the data to create a linked list:10                                                                                                                                                                                                                     
 If you wish to continue press 1 otherwise 0:1                                                                                                                                                                                                                     
 Enter the data:15                                                                                                                 
                                                                                                                                   
 If you wish to continue press 1 otherwise 0:1                                                                                                                                                                                                                       
 Enter the data:20                                                                                                                 
                                                                                                                                   
 If you wish to continue press 1 otherwise 0:1                                                                                                                                                                                                                      
 Enter the data:25                                                                                                                 
                                                                                                                                   
 If you wish to continue press 1 otherwise 0:1                                                                                                                                                                                                                        
 Enter the data:30                                                                                                                 
                                                                                                                                   
 If you wish to continue press 1 otherwise 0:1                                                                                                                                                                                                                        
 Enter the data:35                                                                                                                 
                                                                                                                                   
 If you wish to continue press 1 otherwise 0:0                                                                                                                                                                                                                        
 Enter the data to insert at beggining:5                                                                                           
5->10->15->20->25->30->35   

by at No comments:
Tags , , , , , ,

Insertion in singly linked list 2

Insertion in singly linked list after specified Node

  • To insert an element into a linked list after a certain number of nodes, we must skip the desired number of elements in the list and change the pointer to the spot where the node will be put. 
  • The following statements will be used to do this.
emp=head;  
            for(i=0;i<loc;i++)  
            {  
                temp = temp->next;  
                if(temp == NULL)  
                {  
                    return;  
                }  
            }
  • Allocate space for the new node and include the item in the data section. The following statements will be used to do this.
ptr = (struct node *) malloc (sizeof(struct node));  
        ptr->data = item; 
  • Only a few more link adjustments are needed, and our node will be put at the correct location. 
  • Because the loop pointer temp will be pointing to the node when the new node is placed at the end of the loop. 
  • As a result, the address of the next portion of the temp must be included in the next part of the new node ptr (since, ptr will be in between temp and the next of the temp). 
  • The following statements will be used to do this.
ptr→ next = temp → next
  • Now, we just need to make the next part of the temp, point to the new node ptr. This will insert the new node ptr, at the specified position.
temp ->next = ptr;   

Insertion in singly linked list

Algorithm

  • STEP 1: IF PTR = NULL
              WRITE OVERFLOW
              GOTO STEP 12
              END OF IF
  • STEP 2: SET NEW_NODE = PTR
  • STEP 3: NEW_NODE → DATA = VAL
  • STEP 4: SET TEMP = HEAD
  • STEP 5: SET I = 0
  • STEP 6: REPEAT STEP 5 AND 6 UNTIL I
  • STEP 7: TEMP = TEMP → NEXT
  • STEP 8: IF TEMP = NULL
               WRITE "DESIRED NODE NOT PRESENT"
                GOTO STEP 12
                END OF IF
                END OF LOOP
  • STEP 9: PTR → NEXT = TEMP → NEXT
  • STEP 10: TEMP → NEXT = PTR
  • STEP 11:  SET PTR = NEW_NODE
  • STEP 12:  EXIT
C program to insert data(after specific node) in singly linked list.
#include<stdio.h>  
#include<stdlib.h>  
void randominsert(int);  
void create(int);  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item,loc;  
    do   
    {  
        printf("\nEnter the item which you want to insert?\n");  
        scanf("%d",&item);  
        if(head == NULL)  
        {  
            create(item);  
        }  
        else  
        {  
            randominsert(item);  
        }  
        printf("\nPress 0 to insert more ?\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void create(int item)  
{  
      
        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW\n");  
        }  
        else  
        {  
            ptr->data = item;  
            ptr->next = head;  
            head = ptr;  
            printf("\nNode inserted\n");  
        }  
}  
void randominsert(int item)  
    {  
        struct node *ptr = (struct node *) malloc (sizeof(struct node));  
        struct node *temp;  
        int i,loc;  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW");  
        }  
        else  
        {  
              
            printf("Enter the location");  
            scanf("%d",&loc);             
            ptr->data = item;  
            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");  
        }  
          
    }  

Expected Output:

Enter the item which you want to insert?
12
Node inserted
Press 0 to insert more ?
2
by at No comments:
Tags , , , , ,

Insertion in singly linked list 1

Insertion in singly linked list (at the end).

There are two cases that need to be described in order to put a node at the end.
  1. The node is being added to a list that is currently empty.
  2. The node is appended to the connected list's end.
The first case:
  • The condition (head == NULL) is satisfied in the first case. As a result, we only need to use the malloc statement in C to allocate space for the node. The following statements are used to build up the data and link parts of the node.
ptr->data = item;  
                ptr -> next = NULL; 
  • Because ptr is the only node that will be added into the list, it must be pointed to by the list's head pointer. The following statements will be used to do this.
Head = ptr     

The second case:

  • Because Head is not null, the condition Head = NULL would fail. In order to traverse the list, we must first declare a temporary pointer temp. temp is set to point to the list's initial node.
Temp = head  
  • Then, traverse through the entire linked list using the statements: 
while (temp→ next != NULL)  
            temp = temp → next; 
  • The temp will point to the last node of the list at the end of the loop. Now, set aside space for the new node and assign the item to its data section. 
  • Because the new node will be the last node in the list, the next component of this node must point to null. The next section of the temp node (which is presently the list's last node) must point to the new node (ptr).
temp = head;  
        while (temp -> next != NULL)  
        {  
            temp = temp -> next;  
        }  
        temp->next = ptr;  
        ptr->next = NULL;

Insertion in singly linked list


Algorithm

  • Step 1: IF PTR = NULL Write OVERFLOW
         Go to Step 1
         [END OF IF]
  • Step 2: SET NEW_NODE = PTR
  • Step 3: SET PTR = PTR - > NEXT
  • Step 4: SET NEW_NODE - > DATA = VAL
  • Step 5: SET NEW_NODE - > NEXT = NULL
  • Step 6: SET PTR = HEAD
  • Step 7: Repeat Step 8 while PTR - > NEXT != NULL
  • Step 8: SET PTR = PTR - > NEXT
         [END OF LOOP]
  • Step 9: SET PTR - > NEXT = NEW_NODE
  • Step 10: EXIT
C program to insert data(at the end) in singly linked list.

#include<stdio.h>  
#include<stdlib.h>  
void lastinsert(int);  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\nEnter the item which you want to insert?\n");  
        scanf("%d",&item);  
        lastinsert(item);  
        printf("\nPress 0 to insert more ?\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void lastinsert(int item)  
    {  
        struct node *ptr = (struct node*)malloc(sizeof(struct node));     
        struct node *temp;  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW");     
        }  
        else  
        {  
            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");  
              
            }  
        }  
    }  

Expected Output:

Enter the item which you want to insert?
12
Node inserted
Press 0 to insert more ?
0
Enter the item which you want to insert?
23
Node inserted
Press 0 to insert more ?
2
by at No comments:
Tags , , , , , ,

Doubly Linked List

Two-way chain or doubly-linked list

A doubly linked list is a more complicated sort of linked list in which each node has a pointer to both the previous and next node in the sequence. As a result, a node in a doubly linked list has three parts: node data, pointer to the next node in the sequence (next pointer), and pointer to the prior node (previous pointer). The graphic depicts a sample node in a doubly linked list.

mskuthar


Structure of a node in a doubly linked list

struct node   
{  
    struct node *prev;   
    int data;  
    struct node *next;   
}   
  • The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.
  • Because each node contains the address of the next node and has no record of its previous nodes, we can only navigate in one way in a singly linked list. 
  • The limitation of a singly linked list is overcome by a doubly linked list. 
  • We can obtain all the facts about the previous node by using the previous address stored inside the previous section of each node because each node of the list has the address of its previous node.
A doubly linked list's memory representation.
  • The following graphic displays the memory representation of a doubly linked list. 
  • In general, a doubly-linked list takes up more space for each node, making fundamental operations like insertion and deletion take longer. 
  • However, because the list keeps pointers in both directions, we can simply change the list's elements (forward and backward).
  • The first entry of the list, i.e. 13, is stored at address 1 in the figure below. The starting address 1 is indicated by the head pointer. 
  • The prior of the list includes null because this is the first piece added to the list.

Operations on doubly linked list

Node Creation

struct node   
{  
    struct node *prev;  
    int data;  
    struct node *next;  
};  
struct node *head;   

All the operations of a doubly linked list can be implemented using a menu-driven program written in C.

#include<stdio.h>  
#include<stdlib.h>  
struct node  
{  
    struct node *prev;  
    struct node *next;  
    int data;  
};  
struct node *head;  
void insertion_beginning();  
void insertion_last();  
void insertion_specified();  
void deletion_beginning();  
void deletion_last();  
void deletion_specified();  
void display();  
void search();  
void main ()  
{  
int choice =0;  
    while(choice != 9)  
    {  
        printf("\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 the node after the given data\n7.Search\n8.Show\n9.Exit\n");  
        printf("\nEnter your choice?\n");  
        scanf("\n%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            insertion_beginning();  
            break;  
            case 2:  
                    insertion_last();  
            break;  
            case 3:  
            insertion_specified();  
            break;  
            case 4:  
            deletion_beginning();  
            break;  
            case 5:  
            deletion_last();  
            break;  
            case 6:  
            deletion_specified();  
            break;  
            case 7:  
            search();  
            break;  
            case 8:  
            display();  
            break;  
            case 9:  
            exit(0);  
            break;  
            default:  
            printf("Please enter valid choice..");  
        }  
    }  
}  
void insertion_beginning()  
{  
   struct node *ptr;   
   int item;  
   ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW");  
   }  
   else  
   {  
    printf("\nEnter Item value");  
    scanf("%d",&item);  
      
   if(head==NULL)  
   {  
       ptr->next = NULL;  
       ptr->prev=NULL;  
       ptr->data=item;  
       head=ptr;  
   }  
   else   
   {  
       ptr->data=item;  
       ptr->prev=NULL;  
       ptr->next = head;  
       head->prev=ptr;  
       head=ptr;  
   }  
   printf("\nNode inserted\n");  
}  
     
}  
void insertion_last()  
{  
   struct node *ptr,*temp;  
   int item;  
   ptr = (struct node *) malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW");  
   }  
   else  
   {  
       printf("\nEnter value");  
       scanf("%d",&item);  
        ptr->data=item;  
       if(head == NULL)  
       {  
           ptr->next = NULL;  
           ptr->prev = NULL;  
           head = ptr;  
       }  
       else  
       {  
          temp = head;  
          while(temp->next!=NULL)  
          {  
              temp = temp->next;  
          }  
          temp->next = ptr;  
          ptr ->prev=temp;  
          ptr->next = NULL;  
          }  
             
       }  
     printf("\nnode inserted\n");  
    }  
void insertion_specified()  
{  
   struct node *ptr,*temp;  
   int item,loc,i;  
   ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\n OVERFLOW");  
   }  
   else  
   {  
       temp=head;  
       printf("Enter the location");  
       scanf("%d",&loc);  
       for(i=0;i<loc;i++)  
       {  
           temp = temp->next;  
           if(temp == NULL)  
           {  
               printf("\n There are less than %d elements", loc);  
               return;  
           }  
       }  
       printf("Enter value");  
       scanf("%d",&item);  
       ptr->data = item;  
       ptr->next = temp->next;  
       ptr -> prev = temp;  
       temp->next = ptr;  
       temp->next->prev=ptr;  
       printf("\nnode inserted\n");  
   }  
}  
void deletion_beginning()  
{  
    struct node *ptr;  
    if(head == NULL)  
    {  
        printf("\n UNDERFLOW");  
    }  
    else if(head->next == NULL)  
    {  
        head = NULL;   
        free(head);  
        printf("\nnode deleted\n");  
    }  
    else  
    {  
        ptr = head;  
        head = head -> next;  
        head -> prev = NULL;  
        free(ptr);  
        printf("\nnode deleted\n");  
    }  
  
}  
void deletion_last()  
{  
    struct node *ptr;  
    if(head == NULL)  
    {  
        printf("\n UNDERFLOW");  
    }  
    else if(head->next == NULL)  
    {  
        head = NULL;   
        free(head);   
        printf("\nnode deleted\n");  
    }  
    else   
    {  
        ptr = head;   
        if(ptr->next != NULL)  
        {  
            ptr = ptr -> next;   
        }  
        ptr -> prev -> next = NULL;   
        free(ptr);  
        printf("\nnode deleted\n");  
    }  
}  
void deletion_specified()  
{  
    struct node *ptr, *temp;  
    int val;  
    printf("\n Enter the data after which the node is to be deleted : ");  
    scanf("%d", &val);  
    ptr = head;  
    while(ptr -> data != val)  
    ptr = ptr -> next;  
    if(ptr -> next == NULL)  
    {  
        printf("\nCan't delete\n");  
    }  
    else if(ptr -> next -> next == NULL)  
    {  
        ptr ->next = NULL;  
    }  
    else  
    {   
        temp = ptr -> next;  
        ptr -> next = temp -> next;  
        temp -> next -> prev = ptr;  
        free(temp);  
        printf("\nnode deleted\n");  
    }     
}  
void display()  
{  
    struct node *ptr;  
    printf("\n printing values...\n");  
    ptr = head;  
    while(ptr != NULL)  
    {  
        printf("%d\n",ptr->data);  
        ptr=ptr->next;  
    }  
}   
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("\nitem found at location %d ",i+1);  
                flag=0;  
                break;  
            }   
            else  
            {  
                flag=1;  
            }  
            i++;  
            ptr = ptr -> next;  
        }  
        if(flag==1)  
        {  
            printf("\nItem not found\n");  
        }  
    }     
          
}  
Output

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
8

 printing values...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
1

Enter Item value12

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
1

Enter Item value123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
1

Enter Item value1234

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
8

 printing values...
1234
123
12

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
2

Enter value89

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
3
Enter the location1
Enter value12345

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
8

 printing values...
1234
123
12345
12
89

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
5

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
8

 printing values...
123
12345

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted: 123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
8

 printing values...
123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
7

Enter item which you want to search?
123

item found at location 1 
*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted: 123

Can't delete

*********Main Menu*********

Choose one option from the following list ...

===============================================

1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit

Enter your choice?
9 

Exited.


by at No comments:
Tags , , , , , , , ,

Singly Linked List

One-way chain or single-linked list

  • A singly linked list is a collection of elements that are arranged in a specific order. 
  • The number of elements may vary depending on the program's requirements. In a single linked list, a node is made up of two parts: data and link. 
  • The data component of the node stores the actual data that the node will represent, while the link part stores the address of the node's immediate successor.
  • A one-way chain, also known as a singly linked list, can only be traversed in one direction. 
  • To put it another way, we may say that each node has only the next pointer, therefore we can't traverse the list backwards.

Consider the following scenario: the student's grades in three marks are maintained in a linked list, as indicated in the image.

Singly Linked List
Singly Linked List

  • The links are represented by the arrow in the diagram above. 
  • The marks earned by the student in each topic are stored in the data section of each node. 
  • The null pointer in the address part of the last node identifies it as the last node in the list. In the data section of the list, we can have as many elements as we like.

Operations on Singly Linked List

On a singly linked list, you can conduct a variety of actions. The following is a list of all such operations.
  1. Insertion in singly linked list at beginning.
  2. Insertion in singly linked list at end.
  3. Insertion in singly linked list after specific node.
    • Deletion and Traversing.
    1. Deletion at beginning.
    2. Deletion at the end of the list.
    3. Deletion after specified node.
    4. Traversing.
    5. Searching.

    Node Creation

    struct node   
    {  
        int data;   
        struct node *next;  
    };  
    struct node *head, *ptr;   
    ptr = (struct node *)malloc(sizeof(struct node *));  

    Insertion

    • Insertion into a singly linked list can take place at several points. The insertion is classified into the following types based on the position of the new node being inserted.

    Insertion in singly linked list at beginning

    • It's easy to add a new element to a single linked list at the start. Only a few changes to the node linkages are required. The steps below must be followed in order to add a new node to the list at the start.
    • Allocate space for the new node and place data in the node's data section. The following statements will accomplish this.
    ptr = (struct node *) malloc(sizeof(struct node *));  
                ptr → data = item   
    • Make the new node's link component point to the list's existing first node. The following expression will be used to do this.
    ptr->next = head;  
    • Finally, we must make the new node the first node in the list, which may be accomplished with the following statement.
    head= ptr ;

    Algorithm

    • Step 1: IF PTR = NULL
               Write OVERFLOW
               Go to Step 7
               [END OF IF]
    • Step 2: SET NEW_NODE = PTR
    • Step 3: SET PTR = PTR → NEXT
    • Step 4: SET NEW_NODE → DATA = VAL
    • Step 5: SET NEW_NODE → NEXT = HEAD
    • Step 6: SET HEAD = NEW_NODE
    • Step 7: EXIT
    Singly Linked List

    C program to insert new data (at the beginning) in singly linked list.
    #include<stdio.h>  
    #include<stdlib.h>  
    void beginsert(int);  
    struct node  
    {  
        int data;  
        struct node *next;  
    };  
    struct node *head;  
    void main ()  
    {  
        int choice,item;  
        do   
        {  
            printf("\nEnter the item which you want to insert?\n");  
            scanf("%d",&item);  
            beginsert(item);  
            printf("\nPress 0 to insert more ?\n");  
            scanf("%d",&choice);  
        }while(choice == 0);  
    }  
    void beginsert(int item)  
        {  
            struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
            if(ptr == NULL)  
            {  
                printf("\nOVERFLOW\n");  
            }  
            else  
            {  
                ptr->data = item;  
                ptr->next = head;  
                head = ptr;  
                printf("\nNode inserted\n");  
            }    
        }  

    Expected Output:
    Enter the item which you want to insert?
12
Node inserted
Press 0 to insert more ?
0
Enter the item which you want to insert?
23
Node inserted
Press 0 to insert more ?
2


    by at No comments:
    Tags , , , , ,
    Subscribe to: Posts (Atom)