Page 16 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 1: Introduction to Data Structure and Arrays

List ADT Specifi cation Notes

Value Defi nition: The value defi nition of a linked list contains a data type for storing the value
of the node along with the pointer to the next node. The value can be represented using a simple
data type or a collection of basic data types. However, it must necessarily contain at least one
pointer to the next structure. This can be shown as follows:
struct datatype
{
int item;
struct datatype *next;
}
or,
struct datatype
{
int item;
float info;
char str;
struct datatype *next;
}

Defi nition clause: The nodes of the list are all of the same type, and have a key field called key.
The list is logically ordered from smallest unique element of key to the largest value i.e. at any
position the key of the element is greater than its predecessor and smaller than its successor.

Operations

1. crlist:
Function: creates a list and initializes it as empty.
Preconditions: none.
Postconditions: list is created and is initialized as empty.

2. insert:
Function: inserts new element into the list either at the beginning, in the middle or at the
end.
Preconditions: a list already exists.

Postconditions: list is returned with the new element inserted in it.
3. delete:
Function: searches a list for the element and removes the element from the list.
Preconditions: the list already exists.
Postconditions: the list is returned with the element removed from it.
4. print:
Function: traverses the list and prints each element.

Preconditions: the list already exists.

LOVELY PROFESSIONAL UNIVERSITY 11