Linked List

Posted Date: 16 Jan 2008 Resource Type: Articles/Knowledge Sharing Category: Computer & Technology

Posted By: Sagaya James Immanuel Member Level: Bronze
Rating:

Points: 3

1) /* Linked List:(with a function to locate) */

#include
#include
#include
#include

struct list_element
{
char item[40];
struct list_element *next;
};

typedef struct list_element node;

int menu(void);
void create(node *pt);
node *insert(node *pt);
node *delete(node *pt);
void display(node *pt);
int choice;
void main()
{
node *start;
clrscr();
do
{
choice = menu();
switch(choice)
{
case 1 :
start = (node *) malloc(sizeof(node));
create(start);
printf("\n");
display(start);
continue;
case 2 :
start = insert(start);
printf("\n");
display(start);
continue;
case 3 :
start = delete(start);
printf("\n");
display(start);
continue;
case 4 :
display(start);
break;
default :
printf("End of Computation\n");
}
} while (choice != 5);
}

int menu(void)
{
do
{
printf("\nMain Menu : \n");
printf("1.Create the linked list\n");
printf("2.Add a component\n");
printf("3.Delete a component\n");
printf("4.Display Contents\n");
printf("5.End List\n");
printf("Please enter your choice (1,2,3 or 4) -> ");
scanf("%d", &choice);
if (choice < 1 || choice > 5)
printf("\nError - Please try again\n");
} while (choice < 1 || choice > 5);
printf("\n");
return(choice);
}

void create(node *record)
{
printf("Data item (type \'END\' when finished) : ");
scanf("%s", record->item);

if (strcmp(record->item, "END") == 0)
record->next = NULL;
else
{
record->next = (node *) malloc (sizeof(node));
create(record->next);
}
return;
}

void display(node *record)
{
if (record->next != NULL)
{
printf("%s\n", record->item);
display(record->next);
}
return;
}

node *insert(node *first)
{
node *locate(node *, char []);
node *newrecord;
node *tag;
char newitem[40];
char target[40];
printf("New data item : ");
scanf("%s", newitem);
printf("Place before (type \'END\' if last) : ");
scanf("%s", target);

if (strcmp(first->item, target) == 0)
{
newrecord = (node *) malloc(sizeof(node));
strcpy(newrecord->item, newitem);
newrecord->next = first;
first = newrecord;
}
else
{
tag = locate(first, target);
if (tag == NULL)
printf("\nMatch not found - Try again\n");
else
{
newrecord = (node *) malloc(sizeof(node));
strcpy(newrecord->item, newitem);
newrecord->next=tag->next;
tag->next=newrecord;
}
}
return(first);
}

node *locate(node *record, char target[])
{
if (strcmp(record->next->item, target) == 0)
return(record);
else
if (record->next->next == NULL)
return(NULL);
else
locate(record->next, target);
}

node *delete(node *first)
{
node *locate(node *, char []);
node *tag;
node *temp;
char target[40];

printf("\nData item to be deleted : ");
scanf("%s", target);

if (strcmp(first->item, target) == 0)
{
temp = first->next;
free(first);
first = temp;
}
else
{
tag = locate(first, target);
if (tag == NULL)
printf("\nMatch not found - Please try again\n");
else
{
temp = tag->next->next;
free(tag->next);
tag->next = temp;
}
}
return(first);
}

--------------------------------------------------------------------------------

2) /* Linked list and strings */
#include
#include
#define TRUE 1
void newname(void);
void listall(void);

struct prs
{
char name[1];
struct prs *ptrnext;
};
struct prs *ptrfirst, *ptrcurr, *ptrnew ;

void main()
{
char ch;
clrscr();
ptrfirst = (struct prs *) NULL;
while (TRUE)
{
printf("\n Type 'e' to enter new name");
printf("\n 'l' to list all name,");
printf("\n 'q' to quit : ");
ch = getche();

switch(ch)
{
case 'e' :
newname(); break;
case 'l' :
listall(); break;
case 'q' :
exit(0);
default :
puts("\nEnter only selections listed");
}
}
}

void newname()
{
char numstr[81];

ptrnew = (struct prs *) malloc (sizeof(struct prs) );

if (ptrfirst == (struct prs *) NULL)
ptrfirst = ptrcurr = ptrnew;
else
{
ptrcurr = ptrfirst;
while(ptrcurr->ptrnext != (struct prs *) NULL)
{
ptrcurr = ptrcurr->ptrnext;
}
ptrcurr->ptrnext = ptrnew;
ptrcurr = ptrnew;
}
printf("\nEnter name : ");
gets(ptrcurr->name);
ptrcurr->ptrnext = (struct prs *) NULL;
}
void listall()
{
if (ptrfirst == (struct prs *) NULL)
{
printf("\n Empty List\n");
return;
}
ptrcurr = ptrfirst;
do
{
printf("\nName %s", ptrcurr->name);
ptrcurr = ptrcurr->ptrnext;
} while (ptrcurr != (struct prs *) NULL);
}

--------------------------------------------------------------------------------

3) /* Linked list using recursion */

#include
#include
struct list
{
int i;
struct list *next;
};
typedef struct list node;
main()
{
node *head;
clrscr();
head=(node *)malloc(sizeof(node));
printf("\n size of structure : %d\n",sizeof(head));
create(head);
printf("->%d",(head->next)->i);
printlist(head);
free(head);
}
create(struct list *ln)
{

scanf("%d",&ln->i);
ln->next=(node *)malloc(sizeof(node));
if(ln->i!=999)
{
printf("%d->",ln->i);
create(ln->next);
}
else
{
ln->next=NULL;
printf("%d->",ln->i);
return;
}
}

printlist(struct list *ll)
{
printf("first value : %d ",ll->i);
while(ll->i!=999)
{
printf("%d->",ll->i);
ll=ll->next;
}
}

--------------------------------------------------------------------------------

4) /* Linked list using pointers */
#include
#include
#include
struct node
{
int info;
struct node *link;
};
typedef struct node *NODE;

NODE getnode()
{
NODE x;
x = (NODE) malloc(sizeof(struct node));
if (x == NULL)
{
printf("Out of Memory");
exit(0);
}
return x;
}

void freenode (NODE x)
{
free(x);
}

NODE insert_front(int item, NODE first)
{
NODE temp;
temp = getnode();
temp->info = item;
temp->link = first;
return temp;
}

void display(NODE first)
{
NODE temp;
if (first == NULL)
{
printf("List is empty\n");
return;
}
printf("The contents of linked list\n");
temp=first;
while(temp != NULL)
{
printf("%d ", temp->info);
temp = temp->link;
}
printf("\n");
}
NODE delete_front(NODE first)
{
NODE temp;
if (first == NULL)
{
printf("List is empty cannot be deleted\n");
return first;
}
temp = first;
first = first->link;

printf("The item deleted is %d\n", temp->info);
freenode(temp);
return first;
}

void main()
{
NODE first = NULL;
int choice, item;
clrscr();
for (;;)
{
printf("1:Insert Front\n2:Display\n");
printf("3.Delete\n");
printf("4:Quit\n");
printf("Enter the choice\n");
scanf("%d", &choice);
switch(choice)
{
case 1 :
printf("Enter the item to be inserted\n");
scanf("%d", &item);
first = insert_front(item, first);
break;
case 2 :
display(first);
break;
case 3:
first = delete_front(first);
break;
default :
exit(0);
}
}
}

--------------------------------------------------------------------------------

5) /* Insertion in sorted order and deleting the nth element */
#include
#include
#include
#define NULL '0'
struct n {
int info;
struct n *next;
};
typedef struct n node;
main()
{
node *first=NULL;
int ch;
node *create();
node *insert();
node *del();
void display();
clrscr();
do
{
printf("\n1.Create the linked list");
printf("\n2.Insert a new node");
printf("\n3.Delete a node at specified position");
printf("\n4.Display all elements of list");
printf("\n5.Quit");
printf("\nSelect any one of the above==>");
scanf("%d",&ch);
switch(ch)
{
case 1: first=create(first);
display(first);
break;
case 2: first=insert(first);
display(first);
break;
case 3: first=del(first);
display(first);
break;
case 4: display(first);
break;
default:printf("\nInvalid Choice! Please try again");
}
}while(ch!=5);
}
node *create(node *first)
{
node *temp,*prev=NULL,*ne;
int item;
first=prev;
printf("\nEnter the data & -999 to exit:");
scanf("%d",&item);
while(item!=-999)
{
temp=(node*)malloc(sizeof(node));
temp->next=NULL;
temp->info=item;
if(first==NULL)
first=temp;
else
{
prev=first;
for(ne=first;(ne!=NULL && ne->infonext)
prev=ne;
if(prev==first && ne==first)
{
first=temp;
temp->next=prev;
}
else
{
prev->next=temp;
temp->next=ne;
}
}
printf("\nEnter the data & -999 to exit:");
scanf("%d",&item);
}
return(first);
}
node *insert(node *first)
{
node *temp,*prev,*ne;
int item;
printf("\nEnter the data:");
scanf("%d",&item);
temp=(node*)malloc(sizeof(node));
temp->next=NULL;
temp->info=item;
if(first==NULL)
first=temp;
else
{
prev=first;
for(ne=first;(ne!=NULL && ne->infonext)
prev=ne;
if(prev==first && ne==first)
{
first=temp;
temp->next=prev;
}
else
{
prev->next=temp;
temp->next=ne;
}
}
return(first);
}
node *del(node *first)
{
node *temp,*prev;
int i=1,pos;
printf("Enter the position to be deleted:");
scanf("%d",&pos);
prev=first;
for(temp=first;(temp!=NULL && inext)
{
prev=temp;
i++;
}
if(prev==first && temp==first)
first=first->next;
if(temp!=NULL)
prev->next=temp->next;
else
printf("\nThe element was not found");
return(first);
}
void display(node *first)
{
node *temp;
for(temp=first;temp!=NULL;temp=temp->next)
{
printf("%d",temp->info);
if(temp->next!=NULL)
printf("====>");
}
getch();
}

--------------------------------------------------------------------------------

6) /* Inserting into a linked list after a specific number */
/* A program to insert into a linked list*/
#include
#include
#include

struct node
{
int num;
struct node *next;
};
typedef struct node list;
list *h,*c,*t;
main()
{

void create();
void insert();
void display();
clrscr();
create();
insert();
display();
getch();
return;
}
void create()
{
void display();
char ans='y';
h=(list *)malloc(sizeof(list));
c=h;
printf("create the list\n");
while(ans!='n')
{
printf("\nenter the number:");
scanf("%d",&c->num);
printf("to continue(y/n):");
scanf(" %c",&ans);
if(ans=='y')
{
t=(list *) malloc(sizeof(list));
c->next=t;
c=t;
}
}
c->next=NULL;
display();

}

void insert()
{
int lnumber;
list *new1;
new1=(list *)malloc(sizeof(list));
printf("\nenter the number to be inserted:");
scanf("%d",&new1->num);
printf("insert after which number:");
scanf("%d",&lnumber);
c=h;

while(c->num !=lnumber && c!= NULL)
c=c->next;
if(c!=NULL)
{
new1->next=c->next;
c->next=new1;
}
else
{
printf("%d is not in the list",lnumber);
}

}

void display()
{
c=h;
printf("\n the list is \n");
while(c!=NULL)
{
printf("%d\t",c->num);
c=c->next;
}
}

--------------------------------------------------------------------------------

7) /* Count the number of nodes in a list(function) */
/* counts the number of nodes present in the linked list representing a stack */
count ( struct node * q )
{
int c = 0 ;
/* traverse the entire linked list */
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}

--------------------------------------------------------------------------------

8) /* Sorting a linked list:(Bubble sort) */
/* Declare a structure with a member variable name .Implement L.L and sort the list using bubble sort. */

#include
#include
#include
#include

struct node
{
char name[20];
struct node *link ;
} *start, *visit ;

void main( )
{
getdata( ) ;
clrscr( ) ;
printf ( "\nLinked List Before Sorting:\n" ) ;
displaylist( ) ;
bubble_sort( ) ;
printf ( "\nLinked List After Bubble Sorting:\n" ) ;
displaylist( ) ;
getch( ) ;
}
getdata( )
{
int n ;
char name[20];
char ch ;
struct node *newnode;
clrscr( ) ;
newnode = NULL ;
do
{
printf ( "\nEnter a value: " ) ;
scanf ( "%s", name ) ;
append ( &newnode, name ) ;
printf ( "\nAny More Nodes (Y/N): " ) ;
ch = getche( ) ;
} while ( ch == 'y' || ch == 'Y' ) ;
start = newnode ;
return;
}

/* adds a node at the end of a linked list */
append ( struct node **q, char name[20] )
{
struct node *temp ; temp = *q ;
if ( *q == NULL ) /* if the list is empty, create first node */
{
*q = malloc ( sizeof ( struct node ) ) ;
temp = *q ;
}
else
{
/* go to last node */
while ( temp -> link != NULL )
temp = temp -> link ;
/* add node at the end */
temp -> link = malloc ( sizeof ( struct node ) ) ;
temp = temp -> link ;
}

/* assign data to the last node */

strcpy(temp -> name,name);
temp -> link = NULL ;
return;
}

/* displays the contents of the linked list */
displaylist( )
{

visit = start ;

/* traverse the entire linked list */

while ( visit != NULL )
{
printf ( "%s ", visit -> name ) ;
visit = visit -> link ;
}
return;
}

bubble_sort( )
{
struct node *p, *q, *r, *s, *temp ; s = NULL ;
/* r precedes p and s points to the node up to which comparisons are to
be made */
while ( s != start -> link )
{

r = p = start ;
q = p -> link ;

while ( p != s )
{
if (strcmp(p -> name , q -> name) > 0 )
{
if ( p == start )
{
temp = q -> link ;
q -> link = p ;
p -> link = temp ;
start = q ;
r = q ;
}
else
{
temp = q -> link ;
q -> link = p ;
p -> link = temp ;
r -> link = q ;
r = q ;
}
}
else
{
r = p ;
p = p -> link ;
}
q = p -> link ;
if ( q == s )
s = p ;
}
}
return;
}

--------------------------------------------------------------------------------

9) /* Using Linked list ,implementing Queue */
/* --------------------------------------------------------*/
Linked list implementation of QUEUE'S
/* --------------------------------------------------------*/

#include
#include
typedef struct list
{
int data;
struct list *next;
}node;

main()
{
int ch;
node *front,*rear;
node *head1;
node *insert(node **,node **);
clrscr();
front=(node *)malloc(sizeof(node));
rear=(node *)malloc(sizeof(node));
rear=front=NULL;
head1=front;
printf("\n1. Insert \n2. Delete \n3. Display \n4. Exit");

while(1)
{
printf("\nenter choice");
scanf("%d",&ch);
switch(ch)
{
case 1: insert(&front,&rear);display(front);
break;
case 2: delete(&front,&rear);break;
case 3: display(front);
break;
case 4: exit(0);
}
}
}

node *insert(node **f,node **r)
{
node *ln;
ln=(node *)malloc(sizeof(node));
printf("enter the value:");
scanf("%d",&ln->data);
ln->next=NULL;
(*r)->next=(node *)malloc(sizeof(node));
if(*f==NULL)
{
*f=ln;
*r=ln;
}
else
{
(*r)->next=ln;
*r=ln;
}
}

display(node *ln)
{
node *tmp;
while(ln!=NULL)
{
printf("%d->",ln->data);
ln=ln->next;
}
}
delete(node **f,node **r)
{
node *tmp;
tmp=*f;
if(*f==NULL)
{
printf("queue empty");
}
else
{

(*f)=(*f)->next;
free(tmp);
}
}

--------------------------------------------------------------------------------

10) /* Using Linked list,implementing Circular queue */
#include
#include
#include
#include
typedef struct node
{
char data;
struct node *next;
struct node *previous;
} NODE;
int initialise(NODE **circle);
int add(NODE **current, char key);
int isempty(NODE *circle);
char changeCase(char key);
int main()
{
NODE *current;
char key;
if (!initialise(¤t))
{
puts ("Unable to initialise circular queue!");
return 0;
}
puts("Enter a line of text...\n");
do
{
key = getchar();
if (!add(¤t, key))
{
puts ("Unable to allocate space for a new node in queue!");
return 0;
}
current = current->next;
} while (key != '\n');
puts ("\nHere are you characters in a different case!\n");
do
{
current = current->next;
key = current->data;
putchar(changeCase(key));
} while (key != '\n');
puts("\nand here they are in reverse order!\n");
do
{
current = current->previous;
key = current->data;
putchar(key);
} while (key != '\n');
return 0;
}
int initialise(NODE **circle)
{
if ((*circle = (NODE *)malloc(sizeof(NODE))) == NULL)
return 0;
(*circle)->next = NULL;
(*circle)->previous = NULL;
return 1;
}
int add(NODE **current, char key)
{
NODE *new_node;
/* Special case for the first node */
if (isempty(*current))
{
(*current)->data = key;
(*current)->next = (*current);
(*current)->previous = (*current);
}
else
{
if ((new_node = (NODE *)malloc(sizeof(NODE))) == NULL)
return 0;
/* Let the new node know about the circular queue */
new_node->data = key;
new_node->next = (*current)->next;
new_node->previous = (*current);
/* Let the circular queue know about the new node */
(*current)->next->previous = new_node;
(*current)->next = new_node;
}
return 1;
}
int isempty(NODE *circle)
{
return (circle->next == NULL);
}
char changeCase(char key)
{
if (islower(key))
return toupper(key);
return tolower(key);
}

--------------------------------------------------------------------------------

11) /* Using Linked list implementing a Stack */
#include
#include
#include
typedef struct node
{
char data; /* Store the keystroke by the user */
struct node *next; /* Pointer to the next node */
} STACKNODE;
void push(char key, STACKNODE **stack);
char pop(STACKNODE **stack);
int isempty(STACKNODE *stack);
char top(STACKNODE *stack);
int main()
{
STACKNODE *stack;
char key;
stack = NULL;
puts("Enter a line of text...\n");
do
{
key = getchar();
push(key, &stack);
} while (key != '\n');
puts("Here are the characters in reverse order:");
while (!isempty(stack))
putchar(pop(&stack));
putchar ('\n');
return 0;
}
char top(STACKNODE *stack)
{
return stack->data;
}
void push(char key, STACKNODE **stack)
{
STACKNODE *newnode;
newnode=(STACKNODE *)malloc(sizeof(STACKNODE));
newnode->data = key;
newnode->next = (*stack);
(*stack) = newnode;
}
char pop(STACKNODE **stack)
{
STACKNODE *oldnode;
char key;
oldnode = (*stack);
key = (*stack)->data;
(*stack) = (*stack)->next;
free(oldnode);
return key;
}
int isempty(STACKNODE *stack)
{
return (stack==NULL);
}

--------------------------------------------------------------------------------

12) /* Using Linked list implementing a Binary tree */
#include
#include
typedef struct treenode
{
char data;
struct treenode *left_branch;
struct treenode *right_branch;
} TREE;
void printtree(TREE *tree);
int add_to_tree (TREE **tree_pointer, char key);
int main()
{
TREE *tree;
char key;
puts ("Enter some text...");
tree = NULL;
do
{
key = getchar();
if (!add_to_tree(&tree, key))
{
puts ("Unable to allocate space for new element in tree!");
return 0;
}
} while (key != '\n');
putchar('\n');
printtree(tree);
putchar('\n');
return 1;
}
int add_to_tree (TREE **tree_pointer, char key)
{
/* Special case for first node */
if (*tree_pointer == NULL)
{
if ((*tree_pointer = (TREE *)malloc(sizeof(TREE))) == NULL)
return 0;
(*tree_pointer)->data = key;
(*tree_pointer)->left_branch = NULL;
(*tree_pointer)->right_branch = NULL;
return 1;
}
else
{
if (key > ((*tree_pointer)->data))
{
return add_to_tree(&((*tree_pointer)->right_branch), key);
}
else
return add_to_tree(&((*tree_pointer)->left_branch), key);
}
}
/* Function to print the tree using recursion */
void printtree (TREE *tree)
{
/* Traverse the left branch */
if (tree->left_branch != NULL)
printtree(tree->left_branch);
/* Print the current node */
putchar(tree->data);
/* Traverse the right branch */
if (tree->right_branch != NULL)
printtree(tree->right_branch);
}

Responses

No responses found. Be the first to respond and make money from revenue sharing program.

Feedbacks

Popular Tags

What are tags ?

Search Tags

(No tags found.)

Post Feedback

This is a strictly moderated forum. Only approved messages will appear in the site. Please use 'Spell Check' in Google toolbar before you submit.
You must Sign In to post a response.

	Next Resource: computer tricks
	Previous Resource: QUEUE & STACK
	Return to Discussion Resource Index
	Post New Resource
	Category: Computer & Technology

Post resources and earn money!

Related Resources

Fresher Jobs

Resources

Colleges

Linked List

Responses

Post Feedback