Definition of List

List

A list or sequence or contiguous list is a data structure that implements an ordered collection of values, where the same value may occur more than once. Each value in the list is called an item, or an entry or element of the list. A list can often be constructed by writing the items in sequence, separated by commas, semicolons, or spaces,within a pair of delimiters such as parenthesis'()', brackets'[]', braces'{}', or angle brackets'<>'.

Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic "list" class and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications.

It differs from stack and queue in such a way that additions and removals can be made at any positions in the list.

Array Implementation of List:

A structure is used for representing nodes of the list. The structure consists of two data items: info and next. The info contains the data on the particular node, whereas the next contains the value for next node being represented.

Consider the following example:

/* Declaring the list */

#define MAX 10

struct nodetype {

int info, next;

};

struct nodetype node[MAX];

Here, -1 is used for representing NULL, i.e. if next consists the value -1, then the node is the end of the list.

Eg:

In the fig, 4 lists are shown. List 1 has the head value 1, the i.e. list starts from node[1]. Every next value on the successive nodes gives the next node info of the list. If the next consists value -1, i.e. NULL, (eg: node[6] in this case, then the list is considered to be ended.

The elements of all 4 lists are :

List 1: head = 1

elements = 32, 3, 39, 54

List 2: head = 10

elements = 96, 9, 4, 7, 27

List 3: head = 8

elements = 7, 2 , 23, 27

List 4: head = 13

elements = 19, 54

Initialization of the list elements can be done as follows:

/* initialization of list */

avail = 0

for (i=0; i

node[i].next = i+1;

node[MAX-1].next = -1;

The global variable “avail” is used to point the available list. In this case, its value 0 means the very first node of the available list. All list nodes are ordered sequentially by node[i] pointing to the node[i+1]. The ordering of the node is explicit and hence can be ordered in any other way. i.e. instead of node[0] pointing to node[1], we can also point node[0] to node[24] and so on.

The last node in our example is node[MAX-1], i.e. and so it is set to -1 (i.e. NULL) value.

Operations:

getnode: to create a new node

freenode: destroys a node

insertafter: insert an item into the list after a node

deleteafter: delete a node after the specified node

When a node is needed for use in a particular list, it is obtained from the available list. Similarly, if it is not needed then if is returned to the available list again.

getnode() is a function that removes a node from the available list. For insertion of new elements, a node is required which is provided by the following getnode() function:

/* for getting the available node */

int getnode(void){

int p;

if (avail == -1){

printf(“Overflow”);

exit(1);

}

p = avail;

avail = node[avail].next;

return p;

}

Similarly, when the node is not required, it has to be returned to the list. The following function freenode() does this job.

void freenode(int p){

node[p].next = avail;

avail = p;

return;

}

Similarly, for inserting an item to the node, the following function ‘insertafter()’ is used which accepts a pointer p to a node and an item x as a parameter.

/* for inserting item into the available node */

void insertafter(int p, int x){

int q;

if (p == -1){

printf(“Invalid Operation”);

exit(1);

}

q = getnode();

node[q].info = x;

node[q].next = node[p].next;

node[p].next = q;}

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”