Array Based Implementation

Array Based Implementation  

AU: May-14, Dec.-18, Marks 16

•  The linked list that can be represented by arrays is called static linked list.

• In this section we will discuss in detail how exactly the list can be represented using arrays.

• Basically list is a collection of elements.

• To show the list using arrays we will have 'data' and 'link' fields in the array.

• The array can be created as array of structure as

struct node

{

int data;

int next;

} a[10];

• For instance : Consider a list of (10,20,30,40,50). We can store it in arrays as:

First node. The next field in this node gives the index as 0. Then we get the address of next node. We can further trace the list using next field

Last node. The next field gives the index as - 1 and - 1 is not any subscript in the array. Hence - 1 is taken as end of the list.

• Various operations that can be performed on static linked list are -

1. Creation of list.

2. Display of list.

3. Insertion of any element in the list.

4. Deletion of any element from the list.

5. Searching of desired element in the list.

Let us understand each operation one by one.

1. Creation of list

The list can be created by placing the node of list in an array. Each node consists of two fields 'data' and 'next' pointer. We need to give the address of starting node which is to be placed in the array.

Thus the list can be created as follows

While creating the list we have to first enter the location in an array where the first node is placed and then input the pair: data and next.

Int Create()

{

int head,i;

printf("\n Enter the index for first node");

scanf("%d", &i);

head=i;

while(i!= -1)/*means terminate*/

{

2. Display

After creation we can display the list. Normally when the list is displayed simply the data fields are to be displayed.

After creation we can display the list. Normally when the list is displayed simply the data fields are to be displayed.

void Display(int i)

{

printf("(");

while(i!= -1)

{

if(a[i].data==-1)/*no data item present at a[i]*/

printf(" ");

else

{

printf("%d, ",a[i].data);

}

i=a[i].next;

}

printf(" NULL)"); YSTS AS

}

In Insert function, consider that we have already created a list (10, 20, 30, 40) as -

Suppose we want to insert value 21 after 20 then

Now using for loop we will search 'temp' in array 'a'. When we get the value 'temp' we will come out of loop by using break statement and check for whether the next location is empty or not.

The list after insertion of 21 will look like this

3. Deletion of a node

While deleting a node from the list we simply manipulate the next pointer of previous node in the list. And the data field of the node to be deleted is initialized to - 1.

Consider that the list is

(10,20, 21,30,40)

While deleting this node copy 6 (a[i].next) to the next pointer of previous node in the list. Here 20 comes before 21 in the list. Hence we will copy a[2].next to a[1].next. And actual deletion takes place when a[2].data is assigned to -1.

Let us see a C program based on it -

/*************************************************************

Implementation of various List operations using arrays

*************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

/*data structure for list using array*/

struct node

{

int data;

int next;

}a[10];

void main()

{

char ans;

int i,head, choice;

int Create();

void Display(int);

void Insert();

void Delete();

void Search();

do

{

clrscr();

printf("\n Main Menu");

printf("\n1. Creation");

printf("\n2. Display");

printf("\n3. Insertion of element in the list");

 printf("\n4. Deletion of element from the list");

printf("\n5. Searching of element from the list");

printf("\n6. Exit");

printf("\n Enter Your choice");

scanf("%d", &choice);

switch(choice)

{

}

head=Create();

break;

This for loop initialize the data field of list to -1

case 2:Display(head);

break;

case 3:Insert();

break;

case 4:Delete();

break;

case 5:Search();

break;

case 6:exit(0);

}

printf("\n Do you Wish to go to Main Menu?");

ans=getch();

} while(ans =='y' || ans == 'Y');

getch();

}

int Create()

{

int head,i;

printf("\n Enter the index for first node");

scanf("%d",&i);

head=i;

while(i!= -1)

{

printf("\n Enter the data and index of the first element");

scanf("%d %d",&a[i].data,&a[i].next);

i=a[i].next;

}

return head;

}

void Display(int i)

{

At data field if value is -1 then it indicates that the location is empty.

printf("(");

while(i!= -1)

{

if(a[i].data==-1)

printf(" ");

else

{

printf("%d, ",a[i].data);

}

i=a[i].next;

}

printf(" NULL)");

}

void Insert()

{

int i,new_data,temp;

printf("\n Enter the new data which is to be inserted");

scanf("%d", &new_data);

printf("\n Enter the data after which you want to insert");

scanf("%d", &temp);

for(i=0;i<10;i++)

{

if(a[i].data==temp)

break;

}

if(a[i+1].data==-1)/*next location is empty*/

{

a[i+1].next=a[i].next;

a[i].next=i+1;

a[i+1].data=new_data;

}

}

void Delete()

{

int i,temp,current,new_next;

printf("\n Enter The node to be deleted");

scanf("%d",&temp);

for(i=0;i<10;i++)

{

if(a[i].data==temp)

{

if(a[i].next==-1)

{

a[i].data=-1;/*writing -1 means deleting the element*/

}

current=i;/*marking the index of an array at which record is placed*/ new_next=a[i].next;/*storing the next pointer value at that index*/

}

}

for(i=0;i<10;i++)

{

if(a[i].next== current)

{

a[i].next=new_next;

a[current].data=-1;

}

}

}

void Search()

{

int i,temp,flag=0;

printf("\n Enter the node to be searched ");

scanf("%d",&temp);

for(i=0;i<10;i++)

{

if(a[i].data==temp)

{

flag=1; /*flag 1 means the element is present*/

break;

}

}

if(flag==1)

printf("\n The %d node is present in the list",temp);

else

printf("\n The node is not present ");

}

Output

Main Menu

1. Creation

2. Display

3. Insertion of element in the list

4. Deletion of element from the list

5. Searching of element from the list

6. Exit

Enter Your choice1

Enter the index for first node4

Enter the data and index of the first element10 11

Enter the data and index of the first element20 6

Enter the data and index of the first element30 7

Enter the data and index of the first element40 -1

Do you Wish to go to Main Menu?

Main Menu

1. Creation

2. Display

3. Insertion of element in the list

4. Deletion of element from the list s odra

5. Searching of element from the list

6. Exit

Enter Your choice2

(10, 20, 30, 40, NULL)

Do you Wish to go to Main Menu?

Main Menu

1. Creation

2. Display

3. Insertion of element in the list

4. Deletion of element from the list

5. Searching of element from the list

6. Exit

Enter Your choice6

Although this type of implementation is possible using arrays, it is usually not preferred to have list implementation using arrays because of two main reasons-

Limitations

1. There is a limitation on the number of nodes in the list because of fixed size of array. Hence sometimes memory may get wasted because of less elements in the list or there may be large number of nodes in the list and we could not store some elements in the array.

2. Insertions and deletions of elements in the array(list) is complicated (Just refer the functions Insert() and Delete() and feel how complicated they are!)

Hence we will go for dynamic memory allocation for implementing the list.

Key Point: The list creation using dynamic memory management is called linked list.

 

Ex. 3.4.1: Consider an array A[1:n]. Given a position, write an algorithm to insert an element in the array. If the position is empty, the element is inserted easily. If the position is already occupied the element should be inserted with the minimum number of shifts.

 (Note: The elements can shift to the left or to the right to make the minimum number of moves) AU: May-14, Marks 16

Sol. :

Algorithm for Insertion of Element in array

Step 1: Enter the number of elements present in the array. Also enter the elements in the array.

printf("\n How many elements are present in the array?");

 scanf("%d",&n);

printf("\n Enter the elements (Type -99 for empty location): ");

for(c=0;c<n;c++)

scanf("%d",&array[c]);

Step 2: Enter the value of the element which is to be inserted in the array, say Key Element. Also enter the position at which this element is to be inserted.Say Key_Position.

printf("\n Enter the element to be inserted 2in the array: ");

scanf("%d", &Key_Element);

printf("\n Enter the position at which the element is to be inserted: ");

 scanf("%d", &Key_Postion);

Step 3:

//If the Key_Position is empty then insert the Key_Element at that position. if(array[Key_Postion] ==-99)

array[Key_Position]=Key_Element;

Step 4:

//Otherwise, Count the number of elements present left and right to this Key_Element. We call it as LeftElementCount and RightElementCount. for(i=0;i<=Key_Position-1;i++); //note the semicolon after this for loop

LeftElementCount=i;

for(j=n-1;j>=Key_Position;j—);

RightElementCount=j;

Step 5: If Left ElementCount < RightElementCount then

{

Search for empty location in this left sublist.

If empty location is present then move the elements to the left by creating ebon to space at Key_Position then

Insert Key_Element at Key_Position.

else goto step 8

 }

Step 6: If Left ElementCount> RightElementCount then

{

Search for empty location in this right sublist.

If empty location is present then move the elements to the right by creating space at Key_Position then

Insert Key_Element at Key_Position.

Else

 goto step 8

}

Step 7:

//Create the space at Key_Position by shifting the last position elements to the rightmost //empty space.

for(k=n-1;k>=Key_Position-1;k--)

{

array[k+1]=array[k];

array[Key_Position-1] =Key_Element;

}

Step 8: Display the list of elements in the array

for(c=0;c<=n;c++)

printf("%d", array[c]);

Review Question

1. What are the various operations on array ? Write a procedure to insert an element in the middle of the array. AU: Dec.-18, Marks 7