implemention of linked list(add at beg,add at end, add at specific position, delete at beg, delete at end, delete at specific postion )

//add_at_beg, add_at_end,add_at_specific,del_at_beg, del_at_end,del_at_specific

#include<stdio.h>

#include<conio.h>
#include<malloc.h>

typedef struct node
{
int info;
struct node *next;
}node;
node *start=NULL;

void insert_at_end(int x);
void insert_at_beg(int x);
void insert_at_specific(int ,int);
void disp();
void del_at_beg();
void del_at_end();
void del_at_specific(int po);
int seq_search(int item);
void sort();

int main()
{
int n,po,ch;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insertion at end");
printf("\n\t\t\t2 : Insertion at beg");
printf("\n\t\t\t3 : Insertion at specific");
printf("\n\t\t\t4 : Display");
printf("\n\t\t\t5 : Deletion at beg");
printf("\n\t\t\t6 : Deletion at end");
printf("\n\t\t\t7 : Deletion at specific");
printf("\n\t\t\t8 : Search");
printf("\n\t\t\t9 : Sorting");
printf("\n\t\t\t10 : Exit");
printf("\n\t\t\tEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_end(n);
break;
case 2:
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_beg(n);
break;
case 3:
printf("\nEnter the position :");
scanf("%d",&po);
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_specific(n,po);
break;
case 4:
disp();
break;
case 5:
del_at_beg();
break;
case 6:
del_at_end();
break;
case 7:
printf("\nEnter the position :");
scanf("%d",&po);
del_at_specific(po);
break;
case 8:
printf("\nEnter the item :");
scanf("%d",&n);
po=seq_search(n);
if(po!=-1)
printf("\nFound at %d",po);
else
printf("\nNot Found.");
break;
case 9:
sort();
break;
case 10:
exit(0);
default:
printf("\nInvalid choice");
}
}
return 0;
}

void insert_at_end(int x)
{
node *temp,*new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=NULL;
if(start==NULL)
start=new_node;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}

void insert_at_beg(int x)
{
node *new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=start;
start=new_node;
}

void insert_at_specific(int x,int po)
{
int i;
node *new_node,*temp;
if(po<1 || po>count()+1)
{
printf("\nInvalid position");
return;
}
if(po==1)
insert_at_beg(x);
else
{
if(po==count()+1)
insert_at_end(x);
else
{
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=NULL;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
new_node->next=temp->next;
temp->next=new_node;
}
}
}

void disp()
{
node *temp;
printf("\nElements in the list are : ");
for(temp=start;temp!=NULL;temp=temp->next)
printf("%d ",temp->info);
}

int count()
{
node *temp;
int c=0;
for(temp=start;temp!=NULL;temp=temp->next)
c++;
return c;
}

void del_at_beg()
{
node *temp;
if(start==NULL)
{
printf("\nList Empty");
return;
}
temp=start;
start=start->next;
printf("\nDeleted node is %d",temp->info);
free(temp);
}

void del_at_end()
{
node *temp;
int i;
if(start==NULL)
{
printf("\nList Empty");
return;
}
if(count()==1)
{
del_at_beg();
return;
}
temp=start;
for(i=1;i<count()-1;i++)
temp=temp->next;
printf("\nDeleted node is %d",temp->next->info);
free(temp->next);
temp->next=NULL;
}

void del_at_specific(int po)
{
int i;
node *temp,*temp1;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
temp1=temp->next;
temp->next=temp1->next;
printf("\nDeleted node is %d",temp->info);
free(temp1);
}

int seq_search(int item)
{
int po=0;
node *temp;
temp=start;
while(temp!=NULL)
{
po++;
if(temp->info==item)
return po;
temp=temp->next;
}
return -1;
}


void sort()
{
int t;
node *i,*j;
for(i=start;i!=NULL;i=i->next)
{
for(j=i->next;j!=NULL;j=j->next)
{
if(i->info > j->info)
{
t=i->info;
i->info=j->info;
j->info=t;
}
}
}
}

merge two linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node
{
int info;
struct node *next;
}node;

node *start1=NULL,*start2=NULL,*start3=NULL,*cur;

void make_node(int x)
{
cur=(node*)malloc(sizeof(node)) ;
cur->info=x;
cur->next=NULL;
}
void create_list(node **first, int x)
{
node *temp;
make_node(x);
if(*first==NULL)
*first=cur;
else
{
temp=*first;
while(temp->next!=NULL)
temp=temp->next;
temp->next=cur;
}
}
void traverse(node *first)
{
while(first!=NULL)
{
printf("\t%d",first->info);
first=first->next;
}
}
void sort(node *first)
{
node *n;
int temp;
for(;first!=NULL;first=first->next)
{
for(n=first->next;n!=NULL;n=n->next)
{
if(first->info > n->info)
{
temp=first->info;
first->info=n->info;
n->info=temp;
}
}
}
}

void merge()
{
node *m,*n;
m=start1;
n=start2;
while(m!=NULL && n!=NULL)
{
if(m->info < n->info)
{
create_list(&start3,m->info);
m=m->next;
}
else
{
create_list(&start3,n->info);
n=n->next;
}
}
while(m!=NULL)
{
create_list(&start3,m->info);
m=m->next;
}
while(n!=NULL)
{
create_list(&start3,n->info);
n=n->next;
}
}

int main()
{
int n;
char ch;
printf("\nCreate the first list :\n");
do
{
printf("\nEnter the info :");
scanf("%d",&n);
create_list(&start1,n);
printf("\nWant to continue?[y/n] :");
ch=getche();
}while(toupper(ch)=='Y');
printf("\nCreate the second list :\n");
do
{
printf("\nEnter the info :");
scanf("%d",&n);
create_list(&start2,n);
printf("\nWant to continue?[y/n] :");
ch=getche();
}while(toupper(ch)=='Y');
printf("\n\nFirst List :");
traverse(start1);
printf("\n\nSecond List :");
traverse(start2);
sort(start1);
sort(start2);
merge();
printf("\n\nMerged List :");
traverse(start3);
getch();
return 0;
}


Simple stacks implementation using linked list : PUSH , POP

/*simple stacks implementation using linked list */

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct stack
 {
int data;
  struct node *link;
 };
void push(struct stack **top,int val)
 {
  struct stack *temp;
  temp =(struct stack *)malloc(sizeof(struct stack));
  if(temp==NULL)
  printf("\nstack overflow\n");
temp->data=val;
temp->link=*top;
*top=temp;
 }
int pop(struct stack **top)
 {
  struct stack *temp;
  int ret;
  if(*top==NULL)
  {
  printf("\nstack underflow\n");
  return NULL;
  }
  temp=*top;
  ret=temp->data;
  (*top)=(*top)->link;
  free(temp);
  return ret;
 }

void main()
 {
  struct stack *s1=NULL;
  int i;
 
  push(&s1,12);
  push(&s1,20);
  push(&s1,1);
  push(&s1,13);
 
  i=pop(&s1);          // i=13
  i=pop(&s1);          // i=1
 
  printf("%d\n",i);   // prints 1
 }

Program to Convert Infix expression to prefix Expression

/*Program to Convert Infix expression to prefix Expression*/

#include <stdio.h>
#include <string.h>
#include<malloc.h>

#define MAX 50

struct infix
{
char target[MAX];
char stack[MAX];
char *s,*t;
int top,l;
};



void initinfix ( struct infix *p )
{
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
strcpy ( p -> stack, "" ) ;
p -> l = 0 ;
}

void strrev(char *x)
 {
int i,j=0;
char *t;
t=(char *)malloc(sizeof(char)*strlen(x));
for(i=strlen(x)-1;i>=0;i--)
{
t[j++]=x[i];
}
x=t;
//return x;
 }
void setexpr ( struct infix *p, char *str )
{
p->s=str;
strrev(p->s);
p->l=strlen(p->s);
*(p->target+p->l)='\0';
p->t=p->target + (p->l-1);
}


void push ( struct infix *p, char c )
{
if (p->top==MAX-1)
printf ("Stack is full.\n");
else
{
p->top++;
p->stack[p->top]=c;
}
}


char pop (struct infix *p)
{
if (p->top==-1)
{
printf("Stack is empty.\n");
return -1;
}
else
{
char item = p->stack[p->top];
p->top--;
return item ;
}
}

int priority (char c)
{

if(c=='*'||c=='/'||c=='%')
return 2 ;
else
{
if(c=='+'||c=='-')
return 1 ;

else return 0 ;
}
}

void convert (struct infix *p)
{
char opr;

while (*(p->s))
{
if(*(p->s) == ' ' || *(p->s) == '\t')
{
p->s++;
continue ;
}

if (isdigit(*(p->s))||isalpha(*(p->s)))
{
while(isdigit(*(p->s)) || isalpha(*(p->s)))
{
*(p->t) = *(p->s);
p->s++;
p->t--;
}
}

if(*(p->s)==')')
{
push(p,*(p->s));
p->s++;
}

if (*(p->s) == '*' || *(p->s) == '+'||  *(p->s) == '/' || *(p->s ) == '%'|| *(p->s) == '-'|| *(p->s) == '$' )
{
if (p->top!=-1)
{
opr=pop(p);

while (priority(opr)>priority(*(p->s)))
{
*(p->t) = opr;
p->t--;
opr = pop(p);
}
push (p,opr);
push (p,*(p->s));
}
else
push (p,*(p->s));
p->s++;
}

if(*(p->s) == '(')
{
opr=pop(p);
while (opr!=')')
{
*(p->t)=opr;
p->t--;
opr=pop(p) ;
}
p->s++;
}
}

while (p->top!=-1)
{
opr=pop(p);
*(p->t)=opr;
p->t--;
}
p->t++;
}




void show (struct infix p)
{
while(*(p.t))
{
printf(" %c",*(p.t));
p.t++;
}
}






int main()
{
struct infix q ;
char expr[MAX] ;

initinfix(&q);

printf("Enter infix expression : " ) ;
gets(expr);

setexpr(&q,expr);
convert(&q);

printf ("\nThe Prefix expression is: ");
show(q);
printf("\n");

return 0;
}

Header file for LIST IMPLEMENTATION in C using arrays in linked list

/***************** LIST IMPLEMENTATION **************/



#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int *list; 
int len;
int cap;                            //capacity
int current_position;
}list;
void initialize_list(list *l)
{
int i;
l->len=0;
l->cap=99;
l->current_position = 0;
l->list = (int *)malloc(sizeof(int) * (l->cap+1));
for(i = 0; i <= l->cap+1; i++)
{
l->list[i] = 0;
} 
}
void print_list(list *l)
{

int k; 
for(k=0; k < l->len; k++)
printf("%d ", l->list[k]);
}
void insert_at_position(list *l, int pos, int item)
{//this function should insert the item at a given position in the list
int i, temp;
if(l->len+1 > l->cap)
{
printf("cap is full!");
}
else
{
l -> len++;
for(i = (l -> len); i >= pos; i--)
{
l -> list[i] = l -> list[i-1];
}
l->list[pos-1] = item;
}
l -> current_position = pos-1;
}
void append_l(list *l, int item)
{
int i = l -> len;
// This function will be inserting the item at the end of the list
if(l -> len+1 < l -> cap)
{
l -> list[i] = item;
(l -> len)++;
}
l -> current_position = l -> len;
}
int remove_l(list *l, int at_position)
{
// This function will remove an element from the specified position
// and return the removed value to the calling function
int i;
for(i = at_position-1; i <= l -> len; i++)
{
l -> list[i] = l -> list[i+1];
}
//l->list[pos-1] = item;
l -> len--;
l -> current_position = at_position-1;
}
void move_to_start(list *l)
{
//This function will be setting the current_position to the start of the 
//list
l -> current_position = 0; 

}
void move_to_end(list *l)
{
//This function will be setting the current_postion to last element
//of the list
l -> current_position = l -> len - 1; 
}
int current_position(list *l)
{
//This function will return the value stored in current position
//int i = l -> current_position - 1;
return l -> list[l -> current_position];

}
void move_to_position(list *l, int pos)
{
//This function will change the value of current_postition to pos
l -> current_position = pos-1;
}
void prev(list *l)
{
//This function will decrement current_postion by one, none if at start
if(l -> current_position > 1)
l -> current_position--;
}
void next(list *l)
{
//This function will increment current_position by one, none if 
//at the end
if(l -> current_position < l -> len)
l -> current_position++;
}
int find_value_at_position(list *l, int pos)
{
//This function finds the value at a given position pos in the list
return l -> list[pos-1];
}
int find_position_of_a_value(list *l, int value)
{
//This function will return the position if the value is present
//or else a negative number
int i;
for(i = 0; i < l -> len; i++)
{
if(l -> list[i] == value)
return i+1;
}
}
int size(list *l)
{
//Returns the current size of the list
return l -> len;
}

linked list C program to remove duplicates / repetition of numbers

/* linked list C program to remove duplicates / repetition of numbers */

#include<stdio.h>
#include<stdlib.h>

struct node
{
int n;           
struct node *next;
};

struct node *start,*last,*temp,*temp1,*temp2;

void create()
{
int c=1;
start=NULL;
while(c==1)
{
if(start==NULL)
{
start=(struct node*)malloc(sizeof(struct node));
temp=start;
printf("Enter element ::");
scanf("%d",&temp->n);
start->next=NULL;
}
else
{
last=(struct node*)malloc(sizeof(struct node));
temp->next=last;
temp=last;
printf("Enter element ::");
scanf("%d",&temp->n);
last->next=NULL;
}
printf("to continue enter 1 :");
scanf("%d",&c);
}
}

void manipulate()
{
temp=start;
temp1=start;
if(start->next==NULL)
{
printf("No repitition of Numbers.");
}
else
{
while(temp!=NULL)
{
temp1=temp->next;
temp2=temp;
while(temp1!=NULL)
{
if((temp->n)==(temp1->n))
{
temp2->next=temp1->next;
free(temp1);
temp1=temp2->next;
}
else
{
temp2=temp1;
temp1=temp1->next;
}
}
temp=temp->next;
}
}
}

void display()
{
temp=start;
printf("The list is :: ");
while(temp!=NULL)
{
printf("\n%d\n",temp->n);
temp=temp->next;
}
}

void main()
{
create();
display();
manipulate();
display();
}