8
LISTS
In Chapter 6, stacks and queues were considered. As a data structure they are a sequence of data elements where only two types of operations can be performed: insertion and deletion. Moreover, these operations are restricted to the ends of stacks and queues which are nothing but special types of lists. But in the case of a general list, there is no restriction. An element can be inserted into or deleted from any position of the existing list. In fact, a general list may require some more operations on it. Lists, in general, together with different types of list implementations are discussed in this chapter in detail.
8.1 SEQUENTIAL LISTS
In general, we use the term ‘list’ to signify a series of elements. It is to be noted here that for our purpose the series of elements in a list also maintains an order, that is, first element of the list, second element of the list, and so on.
As a data structure, a list is a finite sequence of elements. In fact, a list may be an empty list also. There are several types of operations involved in a list and they greatly depend on the application. The common operations on list include
(i) create an empty list.
(ii) check if a list is empty.
(iii) traverse the list or a portion of the list.
(iv) insert an element into the list.
(v) delete an element from the list.
By definition, a list is a finite sequence of elements and hence an array may seem to be most natural as the storage structure of the sequential implementation of list. In this implementation the list elements are stored as consecutive array elements. This implies that ith list element is stored as ith array element.
It is to be noted at this point that an array has a fixed length. Once the array is defined we are restricting the size (number of elements ) of the list. For the time being let us compromise with the above fact by defining an array of sufficiently large size so that all the list elements can be accommodated. Let MAXLEN be the constant that defines the maximum length of the list (array). Also consider that we inserted n elements to this list (array) sequentially, that is, ith list element is in the ith element (with index (i-1)) of the array and n < MAXLEN. Obviously, then some of the array elements will be empty at its tail. So we should have an auxiliary variable to maintain the current length of the list.
With this background we may assume the following definitions and declarations.
#define MAXLEN…/*Maximum length of the array(list)*/
typedef………itemtype; /*Type of list elements */
struct listtype {
itemtype item[MAXLEN];
int len;
} ;
struct listtype list;
itemtype element;
With the above definitions and declarations the first three list operations mentioned above can be implemented very easily, but the last two will be little inefficient.
To create an empty list we can simply set the length of list to zero by using a statement like
list.len=0;
Now it is trivial to return 1 if the list is empty by using a statement like
return(list.len==0);
which might be used to check if a list is empty.
We can traverse or look through the list elements one by one from the beginning of the list by passing through all the array elements from the beginning. This may be of the form
for(i=0; i<list.len; i++)
{
process list.item[i];
}
Now, to insert an item into the list we must first decide at what point it is to be inserted. Generally speaking, we need to know after which member of the list the item is to be inserted. As we are considering sequential implementation we know that the ith member of the list is stored in array index(i-1). Consider that our item should be the mth member of the list. So it should be stored in index(m-1) of the list array. Therefore, we must first make the room empty at the index(m-1) of the list array by shifting all the members of the list one step to the right and then put the item at this empty place. For shifting the members of a list array one step to the right we may use the code
for(i=len-1; i>=m-1; i--) list.item[i+1]=list.item[i];
and finally put the element at its proper place by setting
list. item[m-1] =element; and increasing len by list. len++;
Note that we can safely assume the fact that len>=m-1. One more thing must be kept in mind that before doing the shifting of list members we must be sure that the list array is not full.
Clearly, the number of list members that must be shifted, plays a very important role in measuring the efficiency of this insertion process. If there are n members in the list then both the worst case and average case complexities for their process are O(n).
The reverse process is delete. Here if we want to remove the mth member we need to shift some list members to the left and may use the code
for(i=m-1; i<len-l; i++) list.len[i]=list.len[i+1]; list.len--;
Here also measure of efficiency depends on the number of list members to be shifted and again both the worst case and average case complexities are O(n), where n is the total number of members in the list.
From the above discussion we see that if we need to maintain a huge list where the frequency of insertion and deletion is very high, this sequential implementation will be simply an inefficient one since most of the time will be consumed in shifting of list members. There are other better implementation which is discussed in the next section.
8.2 LINKED LISTS
In the sequential implementation we have seen that an array may be thought of a list whose ordering of elements is implicit. This is obvious because the ith member of the list is stored in the (i-1)th location of the array. Actually, their implicit ordering is responsible for shifting the elements of the list to the right or left when we need to insert or delete an element to or from the list, respectively.
In the linked implementation of lists the ordering of list members (elements) is kept explicitly. This is possible only when we can
(a) get the first element of the list, and
(b) for any given list element we can determine its successor element.
This suggests a trivial linked-list implementation which requires to maintain the following.
(a) A collection of nodes that stores two items of information:
(i) The list member or element, and
(ii) A pointer that explicitly gives the location of the successor node.
(b) A pointer that holds the location of the first node of the list.
The pointers are basically establishing a link between the current node and its successor node. That is why these pointers are termed as links in some of the books. We use the terms ‘link’ and ‘pointers’ synonimously.
As an example, a list of the following names of places Bangalore, Jamshedpur, Pune might pictorially be represented as
In the above diagram arrows indicates links. So in the above list head is a pointer that points to the first node whose information (data) part contains Bangalore. This is actually the first list member. This node has got another part called the link part which keeps the information about the location of its successor (next) node. This link part is basically a pointer to the successor node. In the successor node of the first node the information part contains Jamshedpur and the link part points to its successor. Through this link we reach the node where Pune is in the information part and its link part shows an electrical ground symbol indicating that there are no more nodes, that is, this node is the terminal node. The pointer value at this node is NULL. For illustration purpose, in future we will denote the information part of a node pointed by ptr->info and the link part by ptr->link
Now we are in a position to look as to how the five basic list operations given in Section 8.1 can be implemented. The first list operation is to create an empty list which is simply to assign a NULL pointer to the pointer variable head. This is to be done to create an empty list to indicate that head points to no node. The second operation is to check if a list is empty. This can trivially be implemented by testing whether head is holding the NULL pointer or not. The next list operation is traversing a linked list. A list traversal is essential when we need to process each list element exactly once. Consider, for instance, that processing a list element consists of only printing the element. We do this by initializing an additional pointer variablepsntptr(say) to point to the starting node. This may pictorially be represented as
This can be achieved by assigning psntptr equal to head.
Before going further into the algorithm for traversing a list, note the following notations to be used in the illustration. We have already seen that a linked list is a sequence of nodes. Let ptr be a pointer which points to a node. A node has an information part and a link part. We use the notation ptr->info to indicate the information part of the node pointed by the pointer ptr. Similarly, ptr->link is used to indicate the link part of the same. With these notations we resume our illustration of list traversal process.
As the pointer variable psntptr presently points to the first node we can process (print) the information part of it by printing it, that is,
Print psntptr->info
This will print the list element ‘Bangalore’. Then psntptr is to be shifted to point the next node and print the information part of the next node. This can be done by
assign psntptr equal to psntptr->link Print psntptr->info
The above assignment is represented pictorially as
and then prints ‘Jamshedpur’. Now again psntptr is shifted to point the next node by
assign psntptr equal to psntptr->link
which may be depicted as
In a similar fashion ‘Pune’ will be printed by
Print psntptr->info
Now notice that there is no more in the node list. So the value of psntptr-link is a NULL pointer. Hence the assignment
assign psntptr equal to psntptr->link
makes psntptr to hold a NULL pointer. At this point all the list elements are processed (printed) and we can terminate. The above discussion now suggests the following algorithm for a linked list traversal. It is also valid for an empty list.
assign psntptr equal to head;
while (psntptr ! = NULL)
{
print psntptr → info
assign psntptr equal to psntptr->link;
}
We are now left with the last two basic operations, insertion and deletion.
It is quite obvious that to insert an element into a list we should have the list member to insert and at which point of the list the member should be inserted. It is also clear that the member cannot be inserted directly. First we should have a free node whose information part is to be filled with the value of the list member and then this node is to be inserted at the right point of the list. This again yields an obvious question that where from we get a free node? To answer this question let us assume that we have a storage pool of free nodes where from we can get such a node and we have a function called fetchnode ( ) that returns a pointer to a free node, which we can use to serve our purpose. For the time being let us not turn our attention to how the function fetchnode ( ) returns the pointer to a node. To insert a node to a given linked list (means the head of the list is given) we need to consider the following two cases.
(i) The node to be inserted at the beginning of the linked list.
(ii) The node to be inserted after some given node within the list.
Clearly, in the first case the head of the list will change but in the second case the head will remain unaltered.
To illustrate the first case let the city name ‘Ahmedabad’ be inserted at the beginning of the list. Firstly, we call the function fetchnode ( ) to get a pointer ptr (say) to a free node. Set the information part of this node by the value ‘Ahmedabad’. Now to connect this node to the beginning of the list whose first element is pointed by head, we set the link part of the node pointed by ptr with the value of head and then change head with the value of ptr.
This may be written as
assign ptr equal to fetchnode( ); assign ptr->info equal to ‘Ahmedabad'; assign ptr->link equal to head; assign head equal to ptr;
A stepwise pictorial representation may look like
Here head points to the first node of the list whose list members are the four city names ‘Ahmedabad’, ‘Bangalore’, ‘Jamshedpur’, and ‘Pune’.
Let us now consider the second case which seeks to insert a node that will contain the city name ‘Chennai’ after the node with the city name ‘Bangalore’. Consider also that we have in hand a pointer prevptr (say) that points to the node with the city name ‘Bangalore’. Precisely speaking, we seek to insert a node with the city name ‘Chennai’ after the node pointed by prevptr. As before, we first do the following:
assign ptr equal to fetchnode( ); assign ptr->info equal to ‘Chennai'
The status of the node and list may be depicted as
Now to insert the node pointed by ptr within the list after the node pointed by prevptr, we do the following in sequence. Clearly the link part of the node pointed by prevptr is the pointer that points to the next node to the node pointed by prevptr, and should be next node to the node pointed by ptr after insertion. So link part of the node pointed by prevptr is copied to the link part of the node pointed by ptr, that is,
assign ptr->link equal to prevptr->link
This status is represented as
After this, the node pointed by ptr should be the next node to the node pointed by prevptr and we can do it by assigning the link part of the node pointed by prevptr as ptr, which may be expressed as
assign prevptr->link equal to ptr
This completes the insertion operation as shown below.
We are now left with the deletion operation on linked list. Here also we need to consider two different cases as follows.
(i) The node is to be deleted from the beginning of the list, that is, the first node of the linked list is to be deleted.
(ii) The node to be deleted is situated after a node which is pointed by a given pointer, that is, the successor of a given node is to be deleted.
Note that here also the head (pointer to the first node of the list) will change in the first case after deletion and it will remain unchanged in the second case. Consider that presently we are starting with a list with five elements depicted as below, choose first element to be pointed by head.
One point should be noted here that after deleting a node it will not appear in the list. So the space used for the deleted node will not be useful anymore unless we make it free that is, we should treat the deleted node as an empty node so that we can reuse it whenever needed. For our purpose, let us assume that we have a function freenode (ptr) which allows the node pointed by the pointer ptr as a reuseable node.
To delete the first node from the above list we take the help of an additional pointer variable ptr(say). Firstly, we save the starting pointer head within the variable ptr. Then we simply set head such that it points to the very next node. This can be done by storing the value of ptr->link to head. Finally, we call freenode (ptr) to send back the first node (which is now pointed by ptr) to the storage pool so that this space can be reused.
More precisely, we perform the following steps in sequence,
assign ptr equal to head assign head equal to ptr->link Call the function freenode(ptr):
The step-by-step status of the list is depicted as follows.
In the final list we see that there are four nodes, each containing a city name whose first node is pointed by the pointer variable head. To illustrate the second case of deletion process, let us assume that we have another pointer variable prevptr which is pointer to the node with city name ‘Chennai’ (previous node of the node to be deleted) and we are to delete the node which comes immediately after this node in the linked list, that is, the node with city name ‘Jamshedpur’. So the current picture of the list looks like
Here also it is better to take the help of an additional pointer variable ptr (say) which will point to the node to be deleted. This can be achieved by executing the step and our linked list takes the form
assign ptr equal to prevptr->link
From the above figure it is clear that to delete the node pointed by ptr we should change the link part of the node pointed by prevptr so that it points the next node to the node pointed by ptr. Clearly, this is achieved by executing
assign prevptr->link equal to ptr->link
On execution of the above step the linked list takes the form
The only thing we need now is to return the deleted node to the storage pool which requires to execute
Call function freenode(ptr)
Finally, we are left with the following list.
In summary, as we have discussed earlier, it has been found that in a linked list there is no need of shifting the elements in case of insertion and deletion, as in the case of an array. But we have not yet seen how a linked list may be implemented. We have just discussed how different operations on a linked list work in an abstract representation. The next section deals with the different implementations of a linked list.
8.3 LIST IMPLEMENTATIONS
An introduction of list and different operations that are usually performed on lists are described in the previous section in detail. This discussion ensures that when we need to store a sequence of elements which may frequently change by inserting an element to it or by taking out an element from it, we choose a linked list data structure. This is because a shifting of elements is not necessary to achieve these tasks. Here we present how such a linked list may be implemented. We present two different implementions namely, (a) array-based implementation and (b) pointer-based implementation.
Though pointer-based implementation is good enough for our purpose, for a first-time C user it might not be very handy. So for a better visulization of the linked structure we choose to go through the array-based implementation. The readers may skip this if they find it too trivial for their purpose.
8.3.1 Array-based Linked-list Implementation
In the following an array is used as the storage structure to implement the linked-list data structure. We have already seen that a linked list is a sequence of nodes where a node is having two parts in it, namely, (a) an information part and (b) a link part.
The link part of a node is used to point to the next (successor) node in the linked list. If there is no successor node of a node, that is, it is the terminal node of the linked list, the link part of the node is to point to no node and hold a NULL pointer. There is one more pointer head (say) in a linked list which points to the starting node of the linked list. This suggests that a node may be represented by a structure in C and the linked list as an array of such structures. A node is simply an array element whose information part is used to store a list member and the link part stores the array index of its successor node in the linked list. The link part of the terminal node may be set to -1 (because this cannot be an array index) to indicate that there is no more node in the list. The above discussion leads us to declare the following to implement an array-based linked list.
#define SIZE…. /* Maximum number of list members possible */
struct nodetype {
char info[20]; /* Information part */
int link; /* index of successor node */
};
struct nodetype nodearray[SIZE];
In the above declaration we have considered that a list member (the information part of a node) may be a character array (or string ) of a maximum of 20 characters. Initially our list is having no member. So the pointer head that points to the first node of the list should have the value -1 to indicate that it is not pointing to any node. When we require to insert a node to the list we will need a free node which may be an array element of the nodearry. This is because the nodearry is a collection of empty nodes initially and hence we can think that initially this nodearry is the storage pool from which we take nodes whenever necessary. We will also organize this srorage pool of available free nodes as a linked list whose first node is pointed by the pointer (index), say avail. So we need to define two pointers (index) head and avail as
int head, avail;
We must also set head = - 1 initially to create an empty list. To organize the storage pool nodearry of available nodes as a linked list, the nodes of the array must be linked together one after the other. The simplest way to do this is to link the first node to the second, second node to the third, and so on. The pointer avail should have the value (zero) to point to the first node and the link part of the last node (at the index (SIZE-1)) should have the value -1 to indicate that there are no more nodes in the list. A pictorial representation of the above discussion is shown in Fig. 8.1. We take the value of SIZE as 10 for a better understanding.
Fig. 8.1 Nodearray organized as a storage pool of free nodes
AC function that initializes the storage pool may be of the following form which returns the index of the first node of the pool.
initpool( ) /* Function to initialize the storage pool */
{
int i, avail;
avail=0;
for(i=0; i<SIZE-1; i++)
nodearray[i].link=i+1;
nodearray[SIZE-1].link=-1;
return avail;
}
Having done this we can now write the function fetchnode ( ) that returns the index of an available node from the storage pool of the available list. The returned index may be used to store a list member. The fetchnode ( ) function simply returns the index of the first node of the available list if it is non empty and update the pointer (index) avail to point to the next node. The function may be written as given below.
fetchnode( ) /* Function to return the index of a free node if
available, otherwise returns -1 */
{
int ptr;
ptr=avail; /* Note that avail is an external variable */
if (avail==-l)
printf(“Available list is empty—can't return node
”);
else
avail = nodearray[avail].link;
return ptr;
}
Consider that the first city name that is to be inserted to the empty list pointed by head is ‘Pune’. At the beginning we ask a free node by calling the fetchnode ( ) function which will return an index. Let this index be stored in an auxiliary variable ptr(say). The information part of the node at the index ptr is then set to the value ‘Pune’. Actually, this node insertion to the empty list pointed by head is simply adding a node at the front of a list which may be coded in C as
int ptr; /'Definition of the auxiliary variable */ ptr = fetchnode( ); strcpy(nodearray[ptr].info,”Pune”); nodearray[ptr].link = head; head = ptr;
After inserting ‘Pune’ to the list the configuration of nodearray may be depicted as
Now if we want to insert ‘Bangalore’ to the front of the list we need to execute the same code, except for the second statement changes to strcpy (nodearray [ptr].info, “Bangalore”); and the configuration of nodearray takes the form
In a similar way, if we insert now the city name ‘Ahmedabad’ at the front of the list the second statement changes to
strcpy(nodearray[ptr].info,”Ahmedabad”);
And now the nodearray looks like
We can easily see that in this implementation the storage structure of our linked list is an array namely nodearry. Moreover this nodearry is holding two different lists:
(a) The list with city names whose first node is pointed by head.
(b) The list of available nodes which are used whenever necessary. The starting node of this list is pointed by avail.
Now if we want to insert the city name ‘Surat’ at the end of the list, that is, insert after the node pointed by prevptr which holds the index 0 (say) we take a node from the available list, store ‘Surat’ to the information part of the node. Clearly, the successor of this node should be the successor of current prevptr. Moreover the successor of prevptr should be set to the node we are inserting. A code in C language to implement this is presented below:
int ptr; ptr = fetchnode( ); strcpy(nodearray[ptr].info, “Surat”); nodearray[ptr].link=nodearray[prevptr].link; nodearray[prevptr].link=ptr;
On execution of this sequence of instructions nodearry takes the form Index info link
On insertion of the city name ‘Chennai’ after the node pointed by 1 (value of prevptr) using the code in the previous page the nodearry becomes
To get this form the same set of code as above was executed except the second statement which should be like
strcpy(nodearray[ptr].info, “Chennai”);
To insert ‘Mumbai’ after the node pointed by 4, which should be the value of prevptr the second statement should be changed as
strcpy(nodearray[ptr].info, “Mumbai”);
and configuration of nodearry becomes as in Fig. 8.2.
Fig. 8.2 Final configuration of nodearray after inserting six city names
At this point our linked list is identified by head and it contains 6 nodes each holding a different city name. The list is formed by inserting 6 nodes in succession within an empty list. Some were inserted at the front of the existing list while some were inserted after a specific given node in the list. The process of insertion is shown in the form of the function insertlist( ). Clearly, this function would require three arguments,
(a) pointer (index) to the first node of the existing list.
(b) pointer(index) after which the new node is to be inserted.
and (c) the value (string in this case) that should go to information part of the inserted node. The function insertlist ( ) for our purpose may be written as in the following, which returns the head, that is, the pointer to the first node of the list.
insertlist(int start, int prevptr, char element[])
/* start is the pointer(index) to the first node of the list */
/* prevptr is the pointer(index) to the node after which the node to be inserted. If prevptr is -1, it means that node is to be in serted at the beginning of the list */
/* element holds the value of the node to insert */
{
int ptr;
ptr = fetchnode( )
strcpy(nodearray[ptr].info, element);
if(prevptr == -1) /* Insert at the front of the list */
{
nodearray[ptr].link = start;
start = ptr;
} else { /* insert after prevptr */
nodearray[ptr]. link=nodearray[prevptr].link;
nodearray[prevptr]. link=ptr;
}
return start;
}
If we now try to print each of the list members one by one starting from the beginning of the list we need to traverse through each of the nodes of the list. Given the pointer to the start node of the list the list traversal can simply be achieved by performing the following steps.
Step i: Move to the first node of the list. This is the current node now.
Step ii: Process current node.
Step iii: Move to the next node using link part of the current node.
Step iv: Repeat Step (ii) and Step (iii) until the link part of the current node is -1 (NULL).
Strictly speaking the above steps are not really showing the algorithm for list traversal, instead it is a rough sketch of the algorithm. A proper C function that prints the list members (city names) of the list whose first node is pointed by head is presented in the function traverse_list( ). This function requires a single argument which is the pointer to the first node of the list.
traverse_list(int head)
{
int current;
current = head;
while (current!= -1)
{
printf(“%s
”, nodearray[current].info);
current = nodearray[current].link;
}
return;
}
Now it is the turn of the deletion operation to consider. To delete a node from the list we need to know the pointer to its previous node. That is, we can delete a node from a list when we know the pointer to the node which preceds the node to be deleted. Considering the present configuration of nodearray as in fig. 8.2 let us try to delete the node after the node which is pointed by the index 2 i.e., the value of the pointer prevptr (say) is 2. This means that we want to delete the node with city name ‘Bangalore’ from the list pointed by head. A code in C to delete the node may be written as in the following:
int ptr ; /* An auxiliary pointer variable */ ptr = nodearray[prevptr].link ; nodearray[prevptr].link = nodearray[ptr].link;
The first instruction of the above code simply stores the link part of node at prevptr within the variable ptr. Then simply sets the link part of this node by the link part of the node pointed by ptr, that is, by the link part of the node to be deleted. Now nodearry changes to
This configuration of nodearry shows that the first node of the list pointed by head holds the city name ‘Ahmedabad’, its next node is at 4 which holds ‘Chennai’. Next to it is the node at 5 holding the city name ‘Mumbai’, then the node at 0 which contains ‘Pune’ and then the final node at 3 (it is final node, because its link part shows -1) which holds ‘Surat’. Clearly, the node with city name ‘Bangalore’ is deleted from the list pointed by head. The area of deleted node is not useable now. It is possible to reuse the area of the deleted node if and only if this node is returned to the storage pool of available nodes. This can simply be done by inserting the deleted node to the front of the list of available nodes. Let this task be achieved by calling a function freenode ( ) that receives the pointer to the (deleted) node which is to be freed. So the call to the function as
freenode(ptr);
is to be done after executing the above two instructions to complete the deletion task properly. Now our nodearray takes the form
This configuration of nodearry shows any call to the function fetchnode ( ) will return the node at index 1 which is a deleted node and hence the deleted node is reuseable now. Note that though physically the node at index 1 holds the city name ‘Bangalore’ it is not treated so and considered as a junk value and clearly not relevant.
Let us now delete a node which is at the front of the list pointed by head. Clearly, we do not have any preceeding node of the node to be deleted. Such a situation can be handled very simply by executing the following C code. The code below also returns the deleted node to the storage pool of available nodes.
int ptr; /* Auxiliary pointer */ ptr = head; /* Store the current head to ptr */ head = nodearray[ptr].link ; /* Change head to point to the next node*/ freenode(ptr); /* Send back deleted node to storage pool of available nodes */
On execution of the above code our nodearray will take the form
The function deletelist ( ) is presented below. It returns pointer to the starting node of the list from which a node is deleted. The function requires two arguments, namely, (a) pointer (index) to the first node of the list from which the node to be deleted and (b) pointer to the node that precedes the node to be deleted.
Note that if no node precedes the node to be deleted, that is, if the first node is to be deleted then it is indicated to the function by passing the second argument as -1. The function will appear as given below:
deletelist (int start, int prevptr)
/* start is the pointer(index) to the start node of the list */
/* prevptr is the-pointer(index) to the preceeding node to
the node to delete, it is -1 when the first node is to be
deleted */
{
int ptr ;
if (prevptr == -1)
{
ptr = start;
start = nodearray[ptr].link;
} else {
ptr = nodearray[prevptr].link;
nodearray[prevptr].link = nodearray[ptr].link;
}
freenode(ptr);
return start;
}
The function freenode ( ) requires two arguments also. They are
(a) pointer to the first node of the list of available nodes; and
(b) the pointer to the free node that is to be attached to the front of the list of available nodes.
The function freenode ( ) returns the pointer to the beginning of the list of available nodes and is shown below
freenode(int avail, int ptr)
/* avail is the pointer(index) to the first node of the list
of available nodes */
/* ptr is the pointer(index) to the freed */
{
nodearray[ptr].link = avail;
avail = ptr;
return avail;
}
8.4 APPLICATION OF LINKED LIST (ARRAY BASED IMPLEMENTATION)
As an application to linked list we consider the problem of creating an index of a given document stored in an ASCII file. This index is an ordered list of all distinct words within the document. It may so happen that the document contains the same word at different places but its index will have the word only once.
One trivial solution to achieve this is to create a link list of words as described in the following. First create an empty list. Read the first word from the document. Insert the word into the list. Read the next word. If this is the same word simply ignore and read the next word. If this word is smaller (according to alphabetical order) than the previous one, insert the word at the front of the list. Otherwise if it is larger (according to alphabetical order) than the previous one, insert the word after it in the list. Read the next word from the document. Search the existing list from the beginning of the list to find whether the word is already in the list. If so, read the next word and repeat the search, otherwise, find after which node this word is to be inserted within the list and then insert it at its proper place. Continue reading and searching till the end of the document and finally print the list. Clearly, the above method is not efficient because each time we read a word we need to search the list from the beginning and on an average the number of comparisons is half the current length of the list. Evidently the list will become lengthy within a short span of time because we are continuously adding nodes to the list whenever we find a new word.
In order to reduce the search time we can split the list into a number of smaller lists.
For this particular problem, it is quite natural to use twenty six (26) lists, one for each alphabet that is, we may construct one list for all words starting with each different alphabet (letter). In other words, there will be a list for all words starting with ‘A’, a list for all words starting with the letter ‘B’, and so on. A program that constructs an index from a stored document (ASCII file) is given in Example 8.1. The data structure used is linear linked list while the storage structure is array-based.
Example 8.1
/* Index construction of a document (Array based) */
#include <stdio.h>
#define MAXWORD 15
#define POOLSIZE 1000
#define Null -1
#define TRUE 1
#define FALSE 0
typedef struct nodetag {
char info[MAXWORD];
int link;
} nodetype;
int free;
nodetype node[POOLSIZE] ;
main( )
{
int i, predptr, list[26];
char word[MAXWORD];
initpool( );
for (i=0; i<26; i++)
createlist(&list[i]);
while(getword(word)) /* returns word with len */
if(!search(list[word[0]-'A']/ word, &predptr))
insertlist(&list[word[0]-'A'], word.predptr);
for(i=0; i<26; i++)
if(!emptylist(list[i]))
traverselist(list[i]);
return;
}
initpool( )
{
int i ;
for(i=0; i<POOLSIZE; i++)
node[i].1ink= i +1;
node[P00LSIZE-1].link = Null;
free = 0;
return;
}
getnode( )
{
int ptr;
ptr = free;
if (free != Null)
free = node[free].link;
else {
printf(‘No available nodes
’);
printf(“Storage pool is empty
”);
ptr = Null;
}
return ptr;
}
createlist(int *ptrlist)
{
*ptrlist = Null;
return;
}
emptylist(int list)
{
return(list == Null);
}
traverselist(int list)
{
int curptr;
curptr = list;
while (curptr != Null)
{
printf(“%s ”, node[curptr].info);
curptr = node [curptr].link;
}
putchar(‘
’);
return;
}
search(int list, char item[], int *predptr)
{
int curptr, found;
curptr = list;
*predptr = Null;
while (curptr != Null)
if((found = strcmp(node[curptr].info, item)) >= 0) break;
else {
*predptr=curptr ;
curptr = node[curptr].link;
}
return ((found == 0)? TRUE : FALSE);
}
insertlist(int *ptrlist, char item[], int pred)
{
int temp;
temp = getnode( );
strcpy (node[temp].info, item);
if (pred == Null)
{
nodettemp].link=*ptrlist;
*ptrlist=temp;
} else {
node[temp].link=node[pred].link;
node[pred].link=temp;
}
return;
}
getword (char s[])
{
int i = 0
char c;
while(!isalpha(c=getchar( )))
if (c == EOF)
return i;
do {
s[i++]=c;
c = getchar( );
} while(isalpha(c));
s [ i ] =‘ 0’ ;
return i;
}
For the document
TWINKLE TWINKLE LITTLE STAR
HOW I WONDER WHAT YOU ARE
UP ABOVE THE WORLD SO HIGH
LIKE A DIAMOND IN THE SKY
WHEN THE BLAZING SUN IS GONE
WHEN THERE NOTHING SHINES UPON
THEN YOU SHOW YOUR LITTLE LIGHT
TWINKLE TWINKLE ALL THE NIGHT
the above program creates an array of (twenty six) linked lists which may be picturized in Fig. 8.3.
Fig. 8.3 Linked lists created by the program in listing 8.1
The output of the program for the given document is the following list of words.
A ABOVE ALL ARE BLAZING DIAMOND GONE HIGH HOW I IN IS LIGHT LIKE LITTLE NIGHT NOTHING SHINES SHOW SKY SO STAR SUN THE THEN THERE TWINKLE UP UPON WHAT WHEN WONDER WORLD YOU YOUR
8.5 POINTER BASED IMPLEMENTATION OF LINKED LISTS
As an about data structure the definition of a list does not impose any limit to the number of elements in a list. Furthermore, the size of an array is fixed at compile time and it is not possible to change this size during program execution. So an implementation of list that uses an array as the fundamental storage structure is not fool proof because it poses srestrictions on the number of elements in a list. A loyal implementation would require the capability of allocating and deallocating storage area for the nodes of the list dynamically at the time of program execution. C language provides functions like malloc ( ) and calloc ( ) to allocate a memory area dynamically. The function free ( ) can be used to deallocate a memory area which is allocated dynamically in C. In the following we will see a pointer based implementation of lists that uses pointers in conjunction with these dynamic memory allocation/ deallocation functions. We know that a linked list is a sequence of nodes where each node is having two parts in it. The first part is the information part while the second part of a node is a link part which is used to point to the successor node of the list if it exists, otherwise their link part should point to no node indicating that it is the terminal node of the list.
This suggests that a node in C may be implemented by using a self-referential structure that has a member that points to a structure of the same type. So to implement a node we may declare
typedef struct list_node{
char info[20]; /* information part */
struct list_node *link; /* link part */
} nodetype;
Now if head is the pointer to the starting node of the list we may define
nodetype *head;
to indicate that head is a pointer to a node of type nodetype. As in Section 8.3 we consider a list member (information part of a node) as an array of characters of a maximum of 20 characters.
Initially our list does not have any member in it.
So to create an empty list we just set
head=NULL;
To insert a node to this empty list pointed by head with city name ‘Pune’ we require a storage area which may be used as the node. In order to do this we need to call the function malloc ( ) which is provided in C library. This function malloc ( ) when called, allocates a specified number of bytes at the execution time. At this stage we need to take the help of the sizeof operator in C also.
For example, if we need to allocate the storage for an integer value and set a pointer to this address we do the following:
int *pi; pi=(int *)malloc(size(int));
sizeof (int) gives us the number of bytes required to store an integer value which is the argument of the function malloc ( ). Now a call to malloc ( ) returns a pointer (the memory address) where we can store an integer. This returned pointer is now casted as an integer pointer by using (int *).
So for our purpose if we want to allocate the storage of a node of our linked list we need to do the following:
nodetype *ptr; ptr=(nodetype *)malloc(sizeof(nodetype));
Clearly, a node insertion to an empty list is simply adding a node at the front of the list.
Consider an auxiliary array 'city' which holds the city name ‘Pune’ which is to be inserted, that is, we have an array 'city' which is defined as
char city[20];
and it holds the string ‘Pune’.
So to insert a node with city name ‘Pune’ we may use the following C code.
nodetype *ptr; ptr=(nodetype *) malloc(sizeof(nodetype)); strcpy(ptr->info, city); ptr->link = head; head = ptr;
After executing this code if city array holds the string ‘Bangalore’ and we re-execute the above code, another node with cityname ‘Bangalore’ will be inserted as front of the list. Similarly, putting the cityname ‘Ahmedabad’ in the array city and re-executing the same code we get a list like the following picture representation.
The above code is used to insert a node at the front of a given list (list is given when its head is given). But we may want to insert a node within a given list after some given node also. For example, we may want to insert a node with the city name ‘Surat’ after the node with cityname ‘Pune’ which is pointed by the pointer say prevptr. That is, we have with us in the value of the pointers head and prevptr. We also have an array city filled with the string ‘Surat’.
Our objective is to insert a node, with information part stored in the city array, into the list pointed by head after the node pointed by prevptr. To achieve this a C code may be written as
nodetype *ptr; ptr=(nodetype *)malloc(sizeof(nodetype)); strcpy(ptr->info, city); ptr->link=prevptr->link; preveptr->link=ptr;
On execution of this code the list takes the form
It prevptr points to the node with cityname ‘Banglore’ and the city array holds the string ‘Chennai’, the execution of the above code will change the linked list as
Thus we have seen that we can either insert a node at the beginning of a given list or insert a node after a given node within a list. This insertion process is shown in the form of a C function insertnode ( ).
Obviously, this function would require three arguments, namely
(a) a pointer to the starting node of the existing list say start;
(b) a pointer to the node after which the new node to be inserted say prevptr. The new node to be inserted at the front of the list is indicated by setting the value of prevptr as a NULL pointer, before calling the function;
(c) the information part of the new node.
The function should return the head, the pointer to the first node of the list, because insertion of a node at the front of a list changes the head of the list.
The function insertnode ( ) is presented below:
nodetype * insertnode (nodetype *start, nodetype *prevptr, char element!])
/* start is the pointer to head of the list */
/* prevptr is the pointer to the predecessor of the node to
insert */
/* element array holds the information part of the new node
*/
{
nodetype *ptr;
ptr = (nodetype *) malloc(sizeof(nodetype));
strcpy(ptr->info, element);
if(prevptr == NULL)
{ /*insert at the front of the list*/
ptr->link = start;
srart = ptr;
} else {
/* insert after node pointed by prevptr */
ptr->link = prevptr->link;
prevptr->link = ptr;
}
return ptr;
}
Now to print all the list members of a list we need to traverse through all the nodes of the list from the first node to the last node of the list. A simple list traversal algorithm may be presented as the following pseudo code.
Set current node = head of the list;
while(current node != NULL)
{
process current node;
move to the next node through the link part of the
current node and call it as current node;
}
A list traversal function traverse_list ( ) is presented below which prints all our list members. The function receives the list head as its argument and returns nothing.
traverse_list(nodetype *head)
{
nodetype *current;
current = head;
while (current != NULL)
{
printf(“%s
”, current->info);
current = current->link;
}
return;
}
Like the insert operation the deletion of a node from a list is either of the following two types:
(i) We may delete a node from the beginning of a given list, that is, the head of the list is to be deleted. After deletion the next to head will be the new head of the existing list.
(ii) We may delete a node which is situated after a given node.
As in the array implementation, the pointer implementation to delete a node from the front of list pointed by head may be written as
nodetype *ptr; /* Auxiliary pointer variable */ ptr = head; /* Save current head to ptr */ head = ptr->link; /* Change head to point to next node */ free(ptr); /* Deallocate the allocated memory are a pointed by ptr */
Consider now that we want to delete a node from a list, whose front node is pointed by head, which is situated after the node pointed by prevptr in the list as in the figure given below.
In the above figure there are five nodes in the list and they are numbered. The pointer prevptr points to the node number 3. We want to delete the node numbered 4 which appears just after the node pointed by prevptr. The following C code segment may be used to achieve the above task.
nodetype *ptr; /* Auxiliary pointer variable */ ptr=prevptr->link; /* Save the pointer to the node to delete in ptr */ prevptr->link = ptr->link ; /* Set the next node to prevptr as the next node to the node to delete */ free(ptr); /* Deallocate the allocated memory area pointed by ptr */
Combining the above two C segments the function deletenode ( ) to delete a node from a list may be written as presented below. The function receives two arguments, one of which is the list head and the other one is a pointer to the previous node of the node to be deleted. This pointer is NULL, if the node is to be removed from the beginning of the list. The function returns a pointer to the head of the list.
nodetype *deletenode(nodetype *start, nodetype *prevptr)
/* start is the pointer to the list head */
/* prevptr is the pointer to the preceding node to the node to delete */
{
nodetype *ptr;
if (prevptr == NULL)
{
/* delete from front of the list */
ptr = start;
start = ptr->link;
} else { /'delete the successor of the node pointed by prevptr */
ptr = prevptr->link;
prevptr->link = ptr->link;
}
free(ptr);
return start;
}
8.6 APPLICATION OF LINKED LIST ( POINTER BASED IMPLEMENTATION)
In Section 8.4 we considered the problem of creating the word index of a stored document (ASCII file). The data structure that was used to store the word index was an array of linked list of size 26, one for each letter of english alphabet. As the implementation of linked lists was array-based, the storage pool was implemented as an array of structure which was maintained by the programmer. Moreover, for this array implementation the size of storage pool became fixed. Clearly, this puts a restriction on the size of the linked lists which should not be.
In the pointer based implementation of linked lists, the storage pool is created by the system and its size is limited by the available memory size. The discussion in section 8.5 suggests that dynamic memory allocation/ deallocation functions may be used to handle this storage pool efficiently instead of the user defined functions fetchnode ( ) and freenode ( ). Some other user defined functions like initpool ( ) will also not be of use. A pointer based program that constructs a word index from a stored document (ASCII file ) is presented in Example 8.2. The input and output pattern of this program is identical to the program given in Example 8.1.
Example 8.2
#include <stdio.h>
#include <ctype.h>
#define MAXWARD 15
#define TRUE 1
#define FALSE 0
typedef struct node {
char info[MAXWORD];
struct node *link;
} nodetype;
typedef nodetype *nodeptr;
main( )
{
nodeptr list[26], prevptr;
char word[MAXWORD];
int i;
for(i=0; i<26; i++)
createlist(list + i);
while(getword(word)) /* returns word with len */
if(! search(list[wordtO]-'A'], word, &prevptr))
insertnode(&list[word[0]-'A'], word, prevptr);
for(i=0; i<26; i++)
if(!emptylist(list[i]))
traverselist(list[i]);
return;
}
createlist(nodeptr *ptrlist)
{
*ptrlist = NULL;
return;
}
emptylist(nodeptr list)
{
return(list == NULL);
}
traverselist(nodeptr list)
{
nodeptr curptr;
curptr = list;
while (curptr!=NULL)
{
printf(“%s ', curptr->info);
curptr = curptr->link;
}
putchar(‘
’);
return;
}
search(nodeptr head, char item[], nodeptr *prevptr)
{
nodeptr curptr;
int found;
curptr = head;
*prevptr = NULL;
while(curptr!=NULL)
if((found=strcmp(curptr->info)) >= 0)
break;
else {
*prevptr = curptr;
curptr = curptr->link;
}
return ((found == 0)? TRUE : FALSE);
}
insertnode(nodeptr *headptr, char item[], nodeptr prevptr)
{
nodeptr temp;
temp = (nodeptr)malloc(sizeof(nodetype));
strcpy(temp->info, item);
if (prevptr == NULL)
{
temp->link = *headptr;
*headptr = temp;
} else {
temp->link = prevptr->link;
prevptr->link = temp;
}
return;
}
getword(char s[])
{
int c, i=0;
while(!isalpha(c=getchar( )))
if (c == EOF)
return i;
do {
s[i++]=c;
c=getchar( );
} while (isalpha(c)) ;
s[i] = ‘ ’ ;
return i;
}
E
XERCISES
- What are the main advantages of linked lists over arrays in representing a group of items?
- Write a program to reverse a linked list so that the last element becomes the first one, the last but one becomes the second element and so on.
- Write a program to find the sum of integers in a singly linked list.
- Develop a line-oriented text editor that assigns a number to each line of text and maintains the lines in a linked list by line number order.
- Write a program that takes as input a polynomial as (coefficient, exponent) pairs, in any order. The polynomial is stored in a linked list of (coefficient, exponent) pairs. Write a program to print the polynomials in descending order.
- Write a function binary_search that accepts two parameters, an array of pointers to a group of stored numbers, and a single number. The function should use binary search to return a pointer to the single number if it is in the group. If the number is not present in the group, return the value NULL.
- Write a linked list program that cyclically permutes the elements of a given sequence. For example, if the response is
- Write a function that removes the first node in a linked list with a given value.
- Write a function that takes a pointer to a linked list and reverse the order of the nodes by simply altering the pointers.
If the original list where
- Write a function multiply(p, q) to multiply two long positive integers represented by singly linked lists.
- Write a C program to split a linked list into two lists, in such a manner that the first linked list contains the odd numbered nodes and second linked list contains the even numbered.
- A palindrome is some word/line that reads the same forwards or backwards.
Given a linked list of words, write a C function to create a palindrome list from it by concatenating its reverse list to the given list.