Page 17 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Postconditions: list elements are printed in the order they are present in the list. List remains
unchanged.
5. modify:
Function: searches for an element and replaces it with a new value.
Preconditions: the list already exists.

Postconditions: the element if present is modified by a new value.
These are the basic set of operations that might be needed to create and maintain a list of elements.
Other operations, which can be performed on linked lists, are:

1. Counting the elements in a list.
2. Concatenating two lists.
Users can think of more operations like comparing two lists, adding the elements of two lists, etc.

depending on a specific problem and try building ADT’s of their own.
1.5.2 Implementation

Each element of the list is called a node and consists of two or more members. Some members can
contain the information pertaining to that node and the others may be pointers to other nodes.
In case of a singly linked list, one member consists of such a pointer. A linked list is therefore a
collection of structures ordered not by their physical placement in memory but by logical links
that are stored as part of data in the structure itself. The link is in form of a pointer to another
structure of the same type.
Such a structure is represented in ‘C/C++’ as follows:
struct node
{
int item;
struct node *next;
};

The first member is an integer item and the second a pointer to the next node in the list as shown.
The item can be any complex data type. That is it can contain a collection of basic data types.
Further, as we will study doubly linked lists later, we can have more than two pointers. One,
pointing to the successor node and the other to the predecessor. The pointer type is the type of
the node itself. This node can be shown as follows:
struct node
{
int item;
float info;
char str;
struct node *next;
};
Right now, we will limit our discussion to singly linked lists with only two members, i.e. one
containing the data and the other a pointer to the next node.

12 LOVELY PROFESSIONAL UNIVERSITY