Thursday, June 21, 2012

linked list program in C.

This is single linked list implementation in C. It contains all the possible operations in single linked list.
#include<stdio.h>
#include<stdlib.h>

//linked list structure
struct node
{
 int info;
 struct node *next;
};

//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;

//inserting or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}

//deleting a node from list. It has three cases
//1. empty list
//2. deleting first node in the list (this is similar to deleting current node in the list)
//3. other than first node 
void deleteNode(Node *head, int info)
{
    Node *h = head;
    Node *temp=NULL;
    if(h==NULL)
    {
        printf("Linked list is empty\n");
        return ;
    }
    if(head->info == info)
    {
        if(head->next == NULL)
            head = NULL;
        else
        {
            head->info = head->next->info;
            temp = head->next;
            head->next = head->next->next;
            free(temp);
            h = head->next;
        }
        printf("----------------- given %d element is deleted from the list----------------- \n",info);
        return ;
    }
    while(h->next!=NULL)
    {
        if((h->next->info == info))
        {
                temp = h->next;
                h->next=h->next->next;
                free(temp);
                printf("----------------- given %d element is deleted from the list----------------- \n",info);
            return;
        }
        h=h->next;
    }
    printf("-------------- %d is not in the list ------------\n",info);
    return ;
}

//deleting current node
void deleteCurrent(Node *current)
{
 current->info = current->next->info;
 current->next = current->next->next;
}

/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}


//reversing a linked list
Node *reverseList(Node *head)
{
    Node *newHead,*temp;
    temp = head;
    newHead = head;
    if(newHead == temp)
    {
        temp=head->next;
        head = head->next;
        newHead->next = NULL;
    }
    while(head!=NULL)
    {
        temp=head->next;
        head->next = newHead;
        newHead = head;
        head = temp;
    }
    return newHead;
}

// looking for a element in the list
void search(Node *head, int element)
{
    Node *tmp = head;
    while(tmp)
    {
        if(tmp->info == element)
        {
            printf("%d found in the list\n",element);
            break;
        }
        tmp=tmp->next;
    }
    printf("%d not found in the list\n",element);
}

//finding the size of the linked list
int listSize(Node *head)
{
    Node *tmp = head;
 int size=0;
    while(tmp)
    {
  size++;
        tmp=tmp->next;
    }
 return size;
}

//adding the  new node to  a linked list @specified position
Node *add(Node *head,int element, int location)
{
 Node *tmp = head;
 Node *newNode = (Node *)malloc(sizeof(Node));
 newNode->info = element;
 newNode->next = NULL;
 if(!location)
 {
  newNode->next = head;
  head = newNode;
  return head;
 }
 while(tmp!=NULL)
 {
  if(!location)
  {
   newNode->next = tmp->next;
   tmp->next = newNode;
  }
  tmp = tmp->next;
  location--;
 }
 return head;
}


int main()
{
 Node *head = NULL;
 int i,n,element,choice,pos,size;
 printf("Enter no. of elements in the list\n");
 scanf("%d",&n);
 printf("Enter the elements in the list\n");
// printf("info value is %d\n",head->info);
 for (i=0;i<n;i++)
 {
  scanf("%d",&element);
  head = insert(head,element);
 }
 printf("Below are the operation we can perform on the linked list\n");
 printf("1. Adding Element\n2. Deleting Element\n3. Display list\n4. Reverse list\n5. Finding element\n6. Finding nth element from last\n");
 printf("7. Linked list Size\n8. Exit\n");
 scanf("%d",&choice);
 while(choice!=8)
 {
  switch(choice)
  {
   case 1:
     printf("Enter the element to add to the list\n");
     scanf("%d",&element);
     printf("Enter the position where to ad the element \n");
     scanf("%d",&pos);
     head = add(head,element,pos);
     break;
   case 2:
     printf("Enter the element to delete from the list\n");
     scanf("%d",&element);
     deleteNode(head,element);
     break;
   case 3:
     printf("----------------- list of elements in the linked list are----------------- \n");
     display(head);
     printf("----------------- ----------------- ----------------- ----------------- \n");
     break;
   case 4:
     head=reverseList(head);
     printf("----------------- given linked list is reversed ----------------- \n");
     break;
   case 5:
     printf("Enter the element to be searched in the list\n");
     scanf("%d",&element);
     search(head,element);
     break;
   case 6:
     printf("Enter the position from last\n");
     scanf("%d",&pos);
     Node *tmp=nthFrmLast(head,pos);
     if(tmp)
      printf("%dth element from last is %d\n",pos,tmp->info);
     else
      printf("enter the pos less the list size\n");
     break;
   case 7:
     size = listSize(head);
     if(size)
      printf("----------------- linked list size is %d----------------- \n",size);
     else
      printf("----------------- list is empty----------------- \n");
     break;
   case 8:
     return 0;
     break;
   default:
     printf("Enter the choice between 1-9 only\n");
     break;
  }
  printf("1. Adding Element\n2. Deleting Element\n3. Display list\n4. Reverse list\n5. Finding element\n6. Finding nth element from last\n");
  printf("7. Linked list Size\n8. Exit\n");
  scanf("%d",&choice);
 }
}

No comments:

Popular Posts