C LANGUAGE BOOK |
Linked lists
A linked list is a data structure in which the objects are arranged in a linear order.
Unlike an array, however, in which the linear order is determined by the array
indices, the order in a linked list is determined by a pointer in each object. Linked
lists provide a simple, flexible representation for dynamic sets.
Linked lists are a type of data structure for storing information as a list.
They are a memory efficient alternative to arrays because the size of the list is only ever
as large as the data. Plus they do not have to shift data and recopy when resizing
as dynamic arrays do.
They do have the extra overhead of 1 or 2 pointers per data node, so they make sense
only with larger records. You would not want to store a list of integers in a linked list
because it would actually double your memory overhead over the same list in an array.
Advantages of linked list
A linked list is a dynamic data structure and therefore the size of the linked list can grow or shrink in size during execution of the program. A linked list does not require any extra space therefore it does not waste extra memory. It provides flexibility in rearranging the items efficiently.
The limitation of linked list is that it consumes extra space when compared to a array since each node must also contain the address of the next item in the list to search for a single item in a linked list is cumbersome and time consuming process.
Types of Linked List
There are 4 different kinds of linked lists:
- Linear singly linked list
- Circular singly linked list
- Two way or doubly linked list
- Circular doubly linked list
Linked List Consist of Node.
A node has two field data and next Pointer.data is the value.and next pointer is the pointer
that point to next node.
1.Singly linked list :-
In Singly List List we have single pointer.
at start list is empty.once we add a node it
the pointer point to node.and next pointer of that
that point to null.
as you see in figure
head pointer point to starting node.next pointer point to next node via arrow(in figure)
and so on.the next pointer of last nodes point to null.
i will show you linked list
using structure.
struct me
{
int data;
struct me *link;
};
Memory allocation
data is value.link is next pointer
linked list are dyanamic .the memory are initialized at runtime.
via malloc function .the memory is freed by free function
malloc and free are in header files alloc.h
struct me *p;
p = malloc(sizeof(struct me));
malloc function take size of stuct.
to free the memory allocated by malloc function.
free(p);
traversing the linked list.
Moving through a linked list and visiting all the nodes is called traversing the linked list.
To traverse a singly linked list you create a pointer and set it to head.
make sure to check that head is not NULL before trying to traverse the list.
you may also need to check that the next pointer of the current node is not NULL.
we set current equal to the next node effectively moving through the entire list until
we do encounter a next pointer that is NULL.
Adding nodes to a linked list
Adding nodes to a linked list is relatively easy. We will need to cover the different cases of adding at the beginning, the middle or the end.
When adding a first node to a linked list, you create a temporary node pointer and allocate memory for the new node. Then set head's next pointer so that it points to the new node.
adding at the beginning:-
if List is Empty
create a temporary node assign data.
set its next pointer of temporary node to point to Null
set the head pointer of list to point to temporary node.
if List is not Empty
create a temporary node assign data.
set its next pointer of temporary node to point to the starting node of list.
set the head pointer of list to point to temporary node.
adding at the middle of the linked list specified by Position:-
check List is not Empty
check list is not short.and position exist.
create a temporary node assign data.
go the poistion specified.
set the next pointer of temporary node to point to next node specified by position.
set the next pointer of previous node specified by position to point to temporary node.
adding at the end of the linked list :-
if list is empty.then add it like add at beginning.
if list is not empty.
create a temporary node assign data.
set the next pointer of temporary node to point to Null.
go to the last node of the linked list.
set its next pointer to point to temporary node.
deleting at the beginning:-
check list is not empty.
if list is having one node.
if so assign the node to temporary node
set head pointer of list to point to null.
free the temporary node.
if list is having more than one node.
assign the starting node to temporary node
point the head pointer to point to next node of starting node
free the temporary node.
deleting at the middle specified by position:-
check List is not Empty
check list is not short.and position exist.
go the position specified.
assign the node to temporary node
assign the next pointer of previous node of that node to point
to next node of that node.
free temporary node.
deleting at the end :-
check List is not Empty
check list is having one node.
if so assign the node to temporary node
set head pointer of list to point to null.
free the temporary node.
check if list is having more than one node.
go to previous node of last node of linked list.
assign the last node to temporary node
set the next pointer of Previous node to point to null.
free temporary node.
/* WAP to perform Linked List operation.
*/
#include<alloc.h>
#include<stdio.h>
struct me
{
int data;
struct me *link;
};
void main()
{
struct me *p;
int j,m,n;
do
{
printf("\n\tLinked List");
printf("\n\t1.Insertion");
printf("\n\t2.Deletion");
printf("\n\t3.Sorting");
printf("\n\t4.Display");
printf("\n\t5.Exit\n");
printf("\n\n\twhat do you want to do (Press 1 to 5): ");
scanf("%d", &j);
printf("\n");
switch(j)
{
case 1: Insertion(&p);
break;
case 2: Deletion(&p);
break;
case 3: Sorting(&p);
break;
case 4: Display(p);
printf("\n");
break;
case 5: exit(1);
default : printf("Wrong Choice\n");
}
}while(j>=1 && j<=5);
}
Insertion(struct me **q)
{
int i,m,n;
do
{
printf("\n\tInsertion");
printf("\n\t1.Insert At Begining");
printf("\n\t2.Insert At Position");
printf("\n\t3.Insert At End");
printf("\n\t4.Return\n");
printf("\n\n\twhat do you want to do (Press 1 to 4): ");
scanf("%d", &i);
printf("\n\n i=%d ",i);
printf("\n");
switch(i)
{
case 1: printf("Enter the number : ");
scanf("%d", &m);
AddAtBeg(&(*q),m);
printf("\n");
break;
case 2: printf("Enter the number : ");
scanf("%d", &m);
printf("Enter the position : ");
scanf("%d", &n);
AddAtPos(*q , m, n);
printf("\n");
break;
case 3: printf("Enter the number : ");
scanf("%d", &m);
AddAtEnd(&(*q) , m);
printf("\n");
break;
case 4: return;
default : printf(" Wrong Choice\n");
}
}while(i>=1 && i<=4);
}
Deletion(struct me **q)
{
int i,m,n;
do
{
printf("\n\tDeletion");
printf("\n\t1.Deletion At Begining");
printf("\n\t2.Deletion At Position");
printf("\n\t3.Deletion At End");
printf("\n\t4.Return\n");
printf("\n\n\twhat do you want to do (Press 1 to 4): ");
scanf("%d", &i);
printf("\n");
switch(i)
{
case 1: DeleteAtBeg(&(*q));
printf("\n");
break;
case 2: printf("Enter the position : ");
scanf("%d", &n);
DeleteAtPos(*q ,n);
printf("\n");
break;
case 3: DeleteAtEnd(&(*q));
printf("\n");
break;
case 4: return;
default : printf("Wrong Choice\n");
}
}while(i>=1 && i<=4);
}
Sorting(struct me **q)
{
int i;
do
{
printf("\n\tSorting");
printf("\n\t1.Using Bubble Sort");
printf("\n\t2.Return");
printf("\n\n\twhat do you want to do (Press 1 to 2): ");
scanf("%d", &i);
printf("\n");
switch(i)
{
case 1: UsingBubbleSort(&(*q));
printf("\n");
break;
case 2: return;
default : printf("Wrong Choice\n");
}
}while(i>=1 && i<=2);
}
AddAtBeg(struct me **q,int x)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
w = malloc(sizeof(struct me));
w->data = x;
w->link = NULL;
*q = w;
}
else
{
w = malloc(sizeof(struct me));
w->data = x;
w->link = *q;
*q = w;
}
return;
}
AddAtPos(struct me *q,int x,int y)
{
struct me *p,*w,*z;
int i;
w = q;
z = q;
if(w == NULL)
{
printf("The List is Empty");
return;
}
for(i = 0; i < y; i++)
{
z = z->link;
if(z == NULL)
{
printf("there are less than %d elements in the list", y);
return;
}
}
{
printf(" \n\n heelloioyuo \n");
p = malloc(sizeof(struct me));
p->data = x;
p->link = z->link;
z->link = p;
}
}
AddAtEnd(struct me **q, int y)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
p = malloc(sizeof(struct me));
p->data = y;
p->link = NULL;
*q = p;
}
else
{
while(p->link != NULL)
{
p = p->link;
}
w = malloc(sizeof(struct me));
w->data = y;
w->link = p->link;
p->link = w;
}
return;
}
DeleteAtBeg(struct me **q)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
printf("The List is Empty");
}
else
{
if(p->link == NULL)
{
printf("the list");
*q = p->link;
free(p);
}
else
{
w = p;
*q = w->link;
free(w);
}
}
return;
}
DeleteAtPos(struct me *q,int x)
{
struct me *p,*w, *z;
int i;
p = q;
w = q;
if(p == NULL)
{
printf("The List is Empty");
}
else
{
for(i = 0; i < x; i++)
{
w = w->link;
}
printf("hello");
z = w->link;
w->link = z->link;
free(z);
return;
}
}
DeleteAtEnd(struct me **q)
{
struct me *p,*w,*z;
p = *q;
w = *q;
if(p == NULL)
{
printf("The List is Empty");
}
else
if(p->link == NULL)
{
*q = p->link;
free(p);
}
else
{
while(p->link->link != NULL)
{
p = p->link;
}
z = p->link;
p->link = z->link;
free(z);
}
return;
}
UsingBubbleSort(struct me **q)
{
int c = 0;
int i,x,j,y;
struct me *p, *w, *z,*v;
p = *q;
v = *q;
while( p != NULL)
{
c++;
p = p->link;
}
printf("\n\n\nThe Number Of Nodes In LinkedList is : %d\n\n",c);
if(v == NULL)
{
printf("\nThe List Is Empty");
}
else if(v->link == NULL)
{
printf("\nThe List Is Already Sorted");
}
else
{
for(w = *q ; w != NULL; w = w->link)
{
for(z = *q ; z->link != NULL; z = z->link)
{
if(z->data>z->link->data)
{
x = z->link->data;
z->link->data = z->data;
z->data = x;
}
}
for(p = *q ; p != NULL; p = p->link)
printf("\nlist: %d", p->data);
printf("\n");
}
}
}
Display(struct me *q)
{
struct me *z;
z = q;
if(z==NULL)
{
printf("The list is empty");
}
while(z != NULL)
{
printf("%d", z->data);
z = z->link;
printf("\n");
}
}
C LANGUAGE BOOK |
No comments:
Post a Comment