Advantages of array implementation:
1.The elements are faster to access using random access
2.Searching an element is easier
Limitation of array implementation
An array store its nodes in consecutive memory locations.
- The number of elements in the array is fixed and it is not possible to change the number of elements .
- Insertion and deletion operation in array are expensive.
- Since insertion is performed by pushing the entire array one position down and deletion is performed by shifting the entire array one position up.
Applications of arrays:
Arrays are particularly used in programs that require storing large collection of similar type data elements
Differences between Array based and Linked based implementation
| Array | Linked List | |
| Definition | Array is a collection of elements having same data type with common name | Linked list is an ordered collection of elements which are connected by links/pointers |
| Access | Elements can be accessed using index/subscript, random access | Sequential access |
| Memory structure | Elements are stored in contiguous memory locations | Elements are stored at available memory space |
| Insertion & Deletion | Insertion and deletion takes more time in array | Insertion and deletion are fast and easy |
| Memory Allocation | Memory is allocated at compile time i.e static memory allocation | Memory is allocated at run time i.e dynamic memory allocation |
| Types | 1D,2D,multi-dimensional | SLL, DLL circular linked list |
| Dependency | Each elements is independent | Each node is dependent on each other as address part contains address of next node in the list |
Linked list based implementation:
Linked Lists:
A Linked list is an ordered collection of elements. Each element in the list is referred as a node. Each node contains two fields namely, Data field-The data field contains the actual data of the elements to be stored in the list Next field- The next field contains the address of the next node in the list
Advantages of Linked list:
- Insertion and deletion of elements can be done efficiently
- It uses dynamic memory allocation
- Memory utilization is efficient compared to arrays
Disadvantages of linked list:
- Linked list does not support random access
- Memory is required to store next field 3.Searching takes time compared to arrays
Types of Linked List
- Singly Linked List or One Way List
- Doubly Linked List or Two-Way Linked List
- Circular Linked List
Dynamic allocation
The process of allocating memory to the variables during execution of the program or at run time is known as dynamic memory allocation. C language has four library routines which allow this function.
Dynamic memory allocation gives best performance in situations in which we do not know memory requirements in advance. C provides four library routines to automatically allocate memory at the run time.
To use dynamic memory allocation functions, you must include the header file stdlib.h.
malloc()
The malloc function reserves a block of memory of specified size and returns a pointer of type void. This means that we can assign it to any type of pointer.
The general syntax of malloc() is ptr =(cast-type*)malloc(byte-size);
where ptr is pointer of type cast-type. malloc() returns a pointer (of cast type) to an area of memory with size byte-size.
calloc():
calloc() function is another function that reserves memory at the run time.
It is normally used to request multiple blocks of storage each of the same size and then sets all bytes to zero.
calloc() stands for contiguous memory allocation and is primarily used to allocate memory for arrays. The syntax of calloc() can be given as:
ptr=(cast-type*) calloc(n,elem-size);
The above statement allocates contiguous space for n blocks each of size elem-size bytes. The only difference between malloc() and calloc() is that when we use calloc(), all bytes are initialized to zero. calloc() returns a pointer to the first byte of the allocated region.
free():
The free() is used to release the block of memory.
Syntax:
The general syntax of the free()function is, free(ptr);
where ptr is a pointer that has been created by using malloc() or calloc(). When memory is deallocated using free(), it is returned back to the free list within the heap.
realloc():
At times the memory allocated by using calloc() or malloc() might be insufficient or in excess. In both the situations we can always use realloc() to change the memory size already allocated by calloc() and malloc(). This process is called reallocation of memory. The general syntax for realloc() can be given as,
ptr = realloc(ptr,newsize);
variable ptr. It returns a pointer to the first byte of the memory block. The allocated new block may be or may not be at the same region. Thus, we see that realloc() takes two arguments. The first is the pointer referencing the memory and the second is the total number of bytes you want to reallocate.
Singly Linked List
A singly linked list is a linked list in which each node contains only one link field pointing to the next node in the list.
SLL
SLL with a Header
Basic operations on a singly-linked list are:
- Insert – Inserts a new node in the list.
- Delete – Deletes any node from the list.
- Find – Finds the position( address ) of any node in the list.
- FindPrevious – Finds the position( address ) of the previous node in the list.
- FindNext- Finds the position( address ) of the next node in the list.
- Display-display the date in the list
- Search-find whether a element is present in the list or not
Declaration of Linked List
void insert(int X,List L,position P); void find(List L,int X); void delete(int x , List L); typedef
struct node *position; position L,p,newnode; struct node
{
int data; position next;
};
Creation of the list:
This routine creates a list by getting the number of nodes from the user. Assume n=4 for this example.
void create()
{
int i,n;
L=NULL;
newnode=(struct node*)malloc(sizeof(struct node)); printf(“\n Enter the number of nodes to be inserted\n”); scanf(“%d”,&n);
printf(“\n Enter the data\n”); scanf(“%d”,&newnode->data); newnode->next=NULL; L=newnode;
p=L;
for(i=2;i<=n;i++)
{
newnode=(struct node *)malloc(sizeof(struct node)); scanf(“%d”,&newnode->data);
newnode->next=NULL;
p->next=newnode; p=newnode;
}
}
Initially the list is empty
List L
Case 1:Routine to insert an element in list at the beginning
void insert(int X, List L, position p)
{
p=L;
newnode=(struct node*)malloc(sizeof(struct node)); printf(“\nEnter the data to be Inserted\n”);scanf(“%d”,&newnode->data); newnode->next=L; L=newnode;
}
Case 2:Routine to insert an element in list at Position
This routine inserts an element X after the position P. Void Insert(int X, List L, position p)
{
position newnode;
newnode =(struct node*) malloc( sizeof( struct node )); if( newnode = = NULL )
Fatal error( “ Out of Space ” );
else
{
}
}
Newnode -> data = x ; Newnode -> next = p ->next ; P -> next = newnode ;
Insert(25,L, P) – A new node with data 25 is inserted after the position P and the next field is updated to NULL. The next field of previous node is updated to store the address of new node.
Case 3:Routine to insert an element in list at the end of the list
void insert(int X, List L, position p)
{ p=L;
}
newnode=(struct node*)malloc(sizeof(struct node)); printf(“\nEnter the data to be inserted\n”); scanf(“%d”,&newnode->data);
while(p->next!=NULL) p=p->next;
newnode->next=NULL; p->next=newnode; p=newnode;
Routine to check whether a list is Empty
This routine checks whether the list is empty .If the lis t is empty it returns 1 int Is Empty( List L )
{
if ( L -> next = = NULL )
return(1); L
}
Null
Routine to check whether the current position is last in the List
This routine checks whether the current position p is the last position in the list. It returns 1 if position p is the last position
int IsLast(List L , position p)
{
if( p -> next= =NULL) return(1);
}
Routine to Find the Element in the List:
P This routine returns the position of X in the list L
position find(List L, int X)
{
position p; p=L->next;
while(p!=NULL && p->data!=X) p=p->next;
return(p);
}
Find(List L, 20) – To find an element X traverse from the first node of the list and move to the next with the help of the address stored in the next field until data is equal to X or till the end of the list
Null
X P
Find Previous
It returns the position of its predecessor. position FindPrevious (int X, List L)
{
position p; p = L;
while( p -> next ! = NULL && p -> next -> data! = X ) p = p -> next;
return P;
}
Routine to find next Element in the List
It returns the position of successor. void FindNext(int X, List L)
{
position P; P=L->next;
while(P!=NULL && P->data!=X) P = P->next;
return P->next;
}
Routine to Count the Element in the List:
This routine counts the number of elements in the list void count(List L)
{
P = L -> next; while( p != NULL )
{
}
print count;
}
count++;
p = p -> next;
Routine to Delete an Element in the List:
It delete the first occurrence of element X from the list L void Delete( int x , List L){
position p, Temp;
p = FindPrevious( X, L); if( ! IsLast (p, L)){
temp = p -> next;
P -> next = temp -> next; free ( temp );
}
}
Routine to Delete the List
This routine deleted the entire list.
void Delete_list(List L)
{
position P,temp; P=L->next;
L->next=NULL; while(P!=NULL)
{
temp=P->next; free(P); P=temp;
}
}
| Program 1: Implementation of Singly linked List | Output |
| #include<stdio.h> #include<conio.h> #include<stdlib.h> void create(); void display(); void insert(); void find(); void delete(); typedef struct node *position; position L,p,newnode; struct node { | 1.create 2.display 3.insert 4.find 5.delete Enter your choice |
| int data; position next; }; void main() { int choice; clrscr(); do { printf(“1.create\n2.display\n3.insert\n4.find\n5.delete\n\n\n”); printf(“Enter your choice\n\n”); scanf(“%d”,&choice); switch(choice) { case 1: create(); break; case 2: display(); break; case 3: insert(); break; case 4: find(); break; case 5: delete(); break; case 6: exit(0); } } while(choice<7); getch(); } void create() { int i,n; L=NULL; newnode=(struct node*)malloc(sizeof(struct node)); printf(“\n Enter the number of nodes to be inserted\n”); scanf(“%d”,&n); printf(“\n Enter the data\n”); scanf(“%d”,&newnode->data); newnode->next=NULL; | 1 Enter the number of nodes to be inserted 5 Enter the data 1 2 3 4 5 1.create 2.display 3.insert 4.find 5.delete Enter your choice 2 1 -> 2 -> 3 -> 4 -> 5 -> Null 1.create 2.display 3.insert 4.find 5.delete Enter your choice 3 |
| L=newnode; p=L; for(i=2;i<=n;i++) { newnode=(struct node *)malloc(sizeof(struct node)); scanf(“%d”,&newnode->data); newnode->next=NULL; p->next=newnode; p=newnode; } } void display() { p=L; while(p!=NULL) { printf(“%d -> “,p->data); p=p->next; } printf(“Null\n”); } void insert() { int ch; printf(“\nEnter ur choice\n”); printf(“\n1.first\n2.middle\n3.end\n”); scanf(“%d”,&ch); switch(ch) { case 2: { int pos,i=1; p=L; newnode=(struct node*)malloc(sizeof(struct node)); printf(“\nEnter the data to be inserted\n”); scanf(“%d”,&newnode->data); printf(“\nEnter the position to be inserted\n”); scanf(“%d”,&pos); newnode->next=NULL; while(i<pos-1) { p=p->next; i++; } newnode->next=p->next; p->next=newnode; | Enter your choice 1.first 2.middle 3.end 1 Enter the data to be inserted 7 7 -> 1 -> 2 -> 3 -> 4 -> 5 – > Null 1.create 2.display 3.insert 4.find 5.delete Enter your choice |
| p=newnode; display(); break; } case 1: { p=L; newnode=(struct node*)malloc(sizeof(struct node)); printf(“\nEnter the data to be inserted\n”); scanf(“%d”,&newnode->data); newnode->next=L; L=newnode; display(); break; } case 3: { p=L; newnode=(struct node*)malloc(sizeof(struct node)); printf(“\nEnter the data to be inserted\n”); scanf(“%d”,&newnode->data); while(p->next!=NULL) p=p->next; newnode->next=NULL; p->next=newnode; p=newnode; display(); break; } } } void find() { int search,count=0; printf(“\n Enter the element to be found:\n”); scanf(“%d”,&search); p=L; while(p!=NULL) { if(p->data==search) { count++; break; } p=p->next; |
| if(count==0) printf(“\n Element Not present\n”); else printf(“\n Element present in the list \n\n”); } void delete() { position p,temp; int x; p=L; if(p==NULL) { printf(“empty list\n”); } else { printf(“\nEnter the data to be deleted\n”); scanf(“%d”,&x); if(x==p->data) { temp=p; L=p->next; free(temp); display(); } else { while(p->next!=NULL && p->next->data!=x) { p=p->next; } temp=p->next; p->next=p->next->next; free(temp); display(); } } } Advantages of SLL |
- Occupies less memory than DLL as it has only one next field.
Disadvantages of SLL
- Traversal in the backwards is not possible
- Less efficient to for insertion and deletion.
OTHER COURSES