Data Structures: List
A. STATIC LIST & ITS ARRAY IMPLEMENTATION
List -> Static List -> Concept
I haven’t as yet told you about what actually a list is and so, here it goes…literally speaking, a list is nothing but a collection of similar data; means when you don’t just deal with one or two variables of same type (for ex. int, char, etc) but you have a bulk of data of same type (may be all int or char or anything). To deal with such enormous amount of data, as you can even imagine, nobody will use regular variables (which can hold only one data at a time) and only solution lies in a LIST.
In C, we have ARRAY to serve the purpose and that’s why its a LIST. Well, I am not here to discuss the ARRAY but we will still see how an array acts as a STATIC list.
Static List:
Let us assume, you have the following data — 12, 34, 56, 65, 23, 100 (all integers). Now, when you store these in an array, let’s say of size 6, the array is full and looks like this —
Now, at the run-time (while your program is running) if you want to add, let’s say, 200. I ask you, can you do it?…………No, you can’t, as that will make the array overflow (out of allotted space).
So, by now you know why do we call it a STATIC list. Well, people still use such data structures when they know the upper bound of their data. One more important point, that’s when you have lesser data than your allotted array size, you waste system’s memory.
List -> Static list -> Addition & Deletion of an element
Addition:-
Damn simple! I would say. Here, you can add an element to the array (i.e any static list) only if the current value of its index < its size and that the array doesn’t have any not NULL value for that INDEX, otherwise, it will overflow. I will elaborate this using an algorithm…
Algorithm:-
Step-1: Check for the current index value, whether < the array size; and the array does not have any not NULL value for that INDEX
Step-2: If step-1 returns true then go to step-3 else output an error message “List overflow or data already exists” and go to step-4
Step-3: array[current_index]=element;
Step-4: Repeat from 1 to 4 for the next element and index values.
Let us see its C implementation:-
int array[listsize];
addelement(int index, int element)
{
if(index<listsize && array[index]!=NULL)
array[index]=element;
else
printf("List overflow or data already exists");
}Note:- This algorithm is for inserting an element anywhere in the list and not just at the end. Kindly, try out that; its very simple!
Deletion:-
Quite similar to addition but this time you will have to check only one thing that is if the array has a NULL value for the given targeted INDEX, you will return “Data Underflow”; otherwise you will put a NULL value there, signifying — element has been deleted. Let me elaborate…
Algorithm:-
Step-1: Check whether the array has a NULL value for the given INDEX
Step-2: If step-1 returns a true value then go to step-3 else output an error message saying “List Underflow” and go to step-1
Step-3: deletedval=array[index]; array[index]=NULL;
Step-4: Return the “deletedval”. Repeat from 1 to 4 for more elements to be deleted
C implementation:-
int array[listsize];
int delelement(int index)
{
int deleteval;
if(array[index]!=NULL)
{
deleteval=array[index];
array[index]=NULL;
}
else
printf("List underflow");
}Note:- Same here, this algorithm for deletion is to delete an element from anywhere in the LIST. Please, try out the sequential deletion on your own.
List -> Static list -> Traversal
Obviously, it is very much what you guessed! It is nothing but reading the list from starting to end, or you can say printing out the LIST.
Algorithm:-
Step-1: Initialize the INDEX value to 0
Step-2: Print out the LIST (array) element for the current INDEX.
Step-3: Increment the INDEX by 1 till the time it is < LISTSIZE; otherwise STOP
Step-4: Go to step-2
C implementation:-
int list[LISTSIZE];
traverse()
{
int index=0;
while (index<LISTSIZE)
{
printf("%d",list[index]);
index++;
}
}List -> Static list -> Key Search
Key Search:-
Well, KEY is just a particular element you want to search in a LIST. It might be there or might not be even. If its there you are supposed to return the position (i.e its INDEX value) or else say “NOT there”.
See, I might be tackling this very lightly as per you, but don’t worry SEARCHING a Key has been covered properly in my last section of this tutorial.
For now, we will discuss, what you call a “Sequential Search”.
You can make out easily what it is? Start searching from the first element in the LIST, check for every next element till the time you find the KEY value or the LIST finishes. I will take help of an algorithm again…
Algorithm:-
Step-1: Initialize your list’s INDEX to 0
Step-2: Check whether the list element for the current INDEX matches the KEY
Step-3: If it matches — you say “found” and quit — or else — go to step-4
Step-4: Increment the INDEX by 1 till < LISTSIZE of the list
Step-5: Go to step-2
Let us see its C implementation:-
int list[listsize];
void keysearch(int key)
{
int index=0, found=0;
while(index<listsize)
{
if(list[index]==key) { found=1;printf("Found"); break;}
index=index+1;
}
if(found==0)printf("Not found");
}Note:- This searching would take a worst case of N comparisons to search a KEY in a LIST of size N.
List -> Static list -> List Sorting
Sorting:-
Like Searching, I will cover list sorting very briskly as I have given it a good coverage in my last section of this tutorial. But for now we’ll see, just a “Timepass” sort. I call it ‘Timepass’ because it actually consumes a lot of time in sorting and takes too many passes. This procedure has been devised by me so I would not suggest you to strictly follow it. Resembles very much to Bubble sort. Let’s see…
Algorithm:-
Step-1: Find out the smallest element from the LIST
Step-2: Swap it with the FIRST element of the list
Step-3: Now consider the LIST beyond the FIRST element of the current list
Step-4: Repeat from step-1 to 4 for N times provided you have N elements in the LIST
Let us see its C implementation:-
int list[N], least, index, pass, temp_index;
...
...
...
/*step-4: Repeat from step -1 to 4 for N times i.e N passes*/
for(pass=0;pass<=N-1;pass++)
{
/*step-1:find the smallest from the LIST*/
least=list[pass];
for(index=pass+1;index<=N-1;index++)
if(least>list[index])
{
least=list[index];
temp_index=index;
}
/*step-2: swap the least with the FIRST element of the list*/
temp=list[pass]; /*the first element*/
list[pass]=least;
list[temp_index]=temp;
/*Now consider the LIST beyond the FIRST element of the current list which
is been done by incrementing the value of PASS */
}
for(index=0;index<=5;index++)printf("\n%d", list[index]); /*print the sorted list out*/
..
..
..Note:- Given above is just a portion of code and you can use it in your program.
B. DYNAMIC LIST & ITS LINKED LIST IMPLEMENTATION
List -> Dynamic List -> Concept
Well, my favorite topic, because here starts that chain reaction; you would know what I mean after sometime!
We have seen STATIC list, ARRAY, in which, we realised that space is the constraint. At the run-time, it was not possible to add more space to the existing allotted space to the LIST. Now, solution lies here with the advent of Dynamic Linked Lists.
What it does is — starts with no fixed size and accumulates memory as and when needed (using garbage collection techniques); what you get in turn is no data overflow, no wastage of memory but a little more computation time. Let’s understand…
Dynamic LIST:
Linked list, as the name suggests has to have some LINKS. So, where is that link? Every element in the list has a link going to the NEXT element in the list and obviously the last element has a NULL link in that case. Theoretically, it looks like this -
Here, every box (i.e individual element) in the list is known as a NODE. A NODE in a Singly linked list has the following structure:
Get Akash Nath’s stories in your inbox
Join Medium for free to get updates from this writer.
struct NODE
{
int nodevalue;
struct NODE *next;
}
So, every linked list has a POINTER to the list, which holds the list. In this case, it is “list”. If you loose this pointer, you will loose the list. What I mean is — you have to have a pointer always pointing to the beginning of the list. Now the question is, how do you create a NODE?
In C, you have memory handling functions like malloc() and free(), which do the job of allocating and freeing of memory space for you; defined in alloc.h header file. So simple!
So, to get a fresh NODE, just call malloc() by providing it the size of your NODE and it allocates you that much of memory space. COOL no! Well, its hardly of our concern from where it collects that memory space.
With all that background, I think, we can create a Linked list…
Algorithm:-
Step-1: Get the value for your NEW node to be added to the list
Step-2: Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say “Memory shortage”
Step-3: Put the value inside the NEW node’s nodevalue field. Make its NEXT pointer to point to NULL
Step-4: Add this NEW node at the end of your LIST
Step-5: Go to step-1 till you have more values to be added to the LIST
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list, *tail;
main()
{
list = (struct NODE *)malloc(sizeof(NODE));/*list initialized*/
tail = list; /*tail is a pointer to keep track of the list's tail*/
..
..
createlist(48); /* call createlist() as and when you want to add a new node*/
..
createlist(34);
..
..
}
createlist(int value) /*our algorithm starts here*/
{
struct NODE *new;
if(tail==list && tail->nodevalue ==NULL)
/*check whether the list is empty*/
{
tail->nodevalue = value;
tail->next = NULL;
}
else /*the case when the list has atleast one non-empty node*/
{
if(new=(struct NODE*)malloc(sizeof(NODE)))
{
new->nodevalue = value;
new->next = NULL; /*depicts the [1] part in the figure*/
tail->next = new;
tail = new; /*depicts the [2] part in the figure*/
}
else
printf("Memory shortage");
}
}Note:- Remember that the “nodevalue” we have taken here can be anything — an integer or a character or an array, …..or any damn process. Well, programming languages like JAVA does all these memory operations on its own to make the programming simpler!
List -> Dynamic List -> Addnode & Delnode
Here I mean addition and deletion of node at any desired position in the LIST.
Addition of NODE:
In dynamic addition of NODE, we assume that the list is already there, means of non-zero length and there is a NODE pointer “target” that points to a node after which the operation(addnode) has to be done.
Algorithm:-
Step-1: Get the value for your NEW node to be added to the list and its Target position
Step-2: Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say “Memory shortage”
Step-3: Put the value inside the NEW node’s nodevalue field
Step-4: Add this NEW node at the desired position (pointed by the “target”) in the LIST
Step-5: Go to step-1 till you have more values to be added to the LIST
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list, *target;
main()
{
list = (struct NODE *)malloc(sizeof(NODE));/*list initialized*/
..
..
/*target is assigned, some how, the position number 2*/
addnode(48,target); /* call addnode() as and when you want to add a new node*/
..
/*target is assigned, some how, the position number 5*/
addnode(34,target);
..
..
}
addnode(int value, struct NODE *position) /*our algorithm starts here*/
{
struct NODE *new;
if(new=(struct NODE*)malloc(sizeof(NODE)))
{
new->nodevalue = value;
new->next = position->next; /*depicts [1] in the figure*/
position->next=new; /*depicts [2] in the figure*/
}
else
printf("Memory shortage");
}In the above figure, [1] & [2] simulate the Step-4 in the algorithm.
Note:- Complete implementation for addnode() has been left for your practice. Assignment of the TARGET position can be done using another function. Please, use your own logic for that.
Deletion of NODE:
Here again we will go by the TARGET value but TARGET here signifies directly the NODE to be deleted.
Algorithm:-
Step-1:Take the value in the ‘nodevalue’ field of the TARGET node in any intermediate variable
Step-2: Make the previous node of TARGET to point to where TARGET is pointing
Step-3: Free the TARGET
Step-4: Return the value in that intermediate variable
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list, *target;
main()
{
int delval;
list = (struct NODE *)malloc(sizeof(NODE));/*list initialized*/
..
..
/*target is assigned, some how, the position number 2*/
delval = deletenode(target); /* call deletenode() as and when you want to add a new node*/
..
/*target is assigned, some how, the position number 5*/
delval = deletenode(target);
..
..
}
int deletenode(struct NODE *position) /*our algorithm starts here*/
{
int deletedval = target->nodevalue; /*step-1 of the algo.*/
struct NODE *curr = list;
while(curr->next != target) /*this is to point a node one before the target*/
curr = curr->next;
curr->next = target->next; /*step-2 of the algo.*/
free(target); /*step-3 of the algo.*/
return(deletedval); /*step-4 of the algo.*/
}Note:- The way I have implemented addnode() and deletenode() might appear a little awkward as they are not the usual methods but I find these to be very simple and easy to understand and so you should, I guess!
List -> Dynamic List -> Traversal
We have seen the static list traversal and we mean the same here. Here, we will take an auxiliary pointer, ‘current’, which will initially point to the beginning of the list and will be moved to point to every other node in the list. Let’s see the algo. ….
Algorithm:-
Step-1: Initialize the ‘Current’ pointer with the beginning of the list
Step-2: Print the value for the ‘Current’ node
Step-3: Make it point to the next node in the list if its there and go to step-2; otherwise stop
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list;
main()
{
...
...
LLtraversal ( list ); /*step-1 of the algo.*/
}
LLtraversal(struct NODE *current)
{
while(current->next != NULL) /*step-3 of the algo.*/
{
printf("%d ->",current->nodevalue); /*step-2 of the algo.*/
current = current->next; /*step-3 of the algo.*/
};
printf("%d", current->nodevalue); /*find out the reason behind this*/
}Note:- For traversal I have assumed that the list already exists and the list pointer, “list”, is pointing to the beginning of the list.
List -> Dynamic List -> Sorting
Ya, again we will be doing the sorting very fast as I’ve already covered this topic properly in the last section of this tutorial; see you there!
But for now, let’s see the Insertion sort for the linked list. The principle goes like this — check for every element( in the unsorted list) whether there exists an element in the sorted list which is just greater than it, then just INSERT this current element exactly before it, in the sorted list. If you find no element in the sorted list to satisfy the condition, please insert the current element at the end of the sorted list. Check out the algo…
Algorithm:-
Step-1: Compare the current element in the UNSORTED list with each element in the SORTED list. If you find an element in the SORTED list to have just higher value than our current element then go to step-2 or else go to step-3
Step-2: Make the element with that just higher value as your TARGET position. Insert the current element at a position just before the TARGET. Consider the next element, if any and go to step-1 or else quit
Step-3: If you find the current element under consideration in the sorted list as the LAST element then just insert your current element from the unsorted list at the end of the Sorted list or else just move to the next element in the sorted list. Consider the next element, if any and go to step-1 or else quit
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *uslist, *slist;
struct NODE *cur_us, *cur_s; /*pointers to surf the lists*/
main()
{
..
/*uslist and slist have been initialised here*/
/*uslist holds the list to be sorted*/
/*slist is initially empty as nothing is sorted*/
..
..
LLsort();
}
LLsort ( )
{
int delval;
struct NODE *temp;
slist->nodevalue = 0; /*sorted list will have 0 as its first element initially*/
slist->next = NULL;
cur_us = uslist;
while( cur_us != NULL)
{
cur_s = slist;
while(cur_s != NULL)
{
if(cur_us->nodevalue < cur_s->nodevalue) /*step-1 of the algo.*/
{
target = cur_s; /*step-2: make cur_s as your TARGET*/
delval = delnode(cur_us); /*deletion has to be done to the UNSORTED list*/
addnode(delval, target); /*remember addition has to be done to the SORTED list*/
}
else
if(cur_s->next == NULL) /*step-3:if cur_s is the last element in the sorted list*/
{
delval = delnode(cur_us);
temp_us = (struct NODE *)malloc(sizeof(NODE));
temp_us ->nodevalue = delval;
cur_s->next = temp_us; /*step-3:append the unsorted element to the sorted list*/
temp_us->next = NULL;
}
cur_s = cur_s->next;
}
cur_us = cur_us->next;
}
}Note:-Write addnode() for this on your own, as I must say its a little different than what I have covered in the add & del section. Well, deletenode() can be referred from there but remember always, you’ll have to adjust the list pointer, ‘uslist’. Remember, while writing the addnode(), you will have to consider the case when you add an element to the beginning of the SORTED list (not always) and the list pointer, ‘slist’, has to be adjusted. Alright!
List -> Dynamic List -> Key Search
By this time you know what is a key and how does a sequential search work, otherwise, refer the static list ‘key search’ section.
Similar to Traversal, here also we will take an auxiliary pointer, current, which initially points to the beginning of the list and then surfs through the list comparing the KEY value with each nodevalue in the list and we return true if the key is found or else false.
Algorithm:-
Step-1: Initialise the Current pointer with the beginning of the List
Step-2: Compare the KEY value with the Current node value; if they match then quit there or else go to step-3
Step-3: Move the Current pointer to point to the next node in the list and go to step-2, till the list is not over or else quit
C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list;
#define TRUE 1
#define FALSE 0
main()
{
int key_to_be_searched;
...
/* the list already exists*/
...
keysearch (key_to_be_searched);
}
keysearch ( int key)
{
struct NODE *current = list;
int found = FALSE;
while (current->nodevalue != NULL)
{
if(current->nodevalue == key)
{
found = TRUE;
break;
}
current = current->next;
};
if (found == TRUE) printf("\nFound");
else printf("\nNot found");
}Note:- Generally Key search returns you the position of the Key in the list (if its there) but I have deliberately skipped that to make it simpler.
Link to other topics on Data Structures:
