Page 30 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 2: Linked Lists

The standard template library provides a rather different data structure called a list. The STL Notes
(Standard Template Library) list provides only those operations that can be implemented

efficiently in a List implementation known as doubly linked, which we shall study shortly. In
particular, the STL list does not allow random access to an arbitrary list position, as provided
by our List operations for insertion, removal, retrieval, and replacement. Another STL template
class, called a vector, does provide some random access to a sequence of data values. An STL
vector bears some similarity to our List ADT, in particular, it provides the operations that can be

implemented efficiently in the List implementation that we shall call contiguous. In this way, our
study of the List ADT provides an introduction to the STL classes list and vector.
2.1 Concept of Linked Lists

An array is represented in memory using sequential mapping, which has the property that

elements are fixed distance apart. But this has the following disadvantage. It makes insertion
or deletion at any arbitrary position in an array a costly operation, because this involves the
movement of some of the existing elements.
When we want to represent several lists by using arrays of varying size, either we have to
represent each list using a separate array of maximum size or we have to represent each of the

lists using one single array. The first one will lead to wastage of storage, and the second will
involve a lot of data movement.
So we have to use an alternative representation to overcome these disadvantages. One alternative
is a linked representation. In a linked representation, it is not necessary that the elements be at a
fixed distance apart. Instead, we can place elements anywhere in memory, but to make it a part

of the same list, an element is required to be linked with a previous element of the list. This can
be done by storing the address of the next element in the previous element itself. This requires
that every element be capable of holding the data as well as the address of the next element. Thus

every element must be a structure with a minimum of two fields, one for holding the data value,

which we call a data field, and the other for holding the address of the next element, which we
call link fi eld.
Therefore, a linked list is a list of elements in which the elements of the list can be placed anywhere

in memory, and these elements are linked with each other using an explicit link field, that is, by

storing the address of the next element in the link field of the previous element.
This program uses a strategy of inserting a node in an existing list to get the list created. An
insert function is used for this. The insert function takes a pointer to an existing list as the fi rst
parameter, and a data value with which the new node is to be created as a second parameter,
creates a new node by using the data value, appends it to the end of the list, and returns a pointer

to the first node of the list. Initially the list is empty, so the pointer to the starting node is NULL.
Therefore, when insert is called first time, the new node created by the insert becomes the start

node. Subsequently, the insert traverses the list to get the pointer to the last node of the existing
list, and puts the address of the newly created node in the link field of the last node, thereby

appending the new node to the existing list. The main function reads the value of the number of
nodes in the list. Calls iterate that many times by going in a while loop to create the links with the
specified number of nodes.

2.2 Representation of Linked List

Because each node of an element contains two parts, we have to represent each node through a
structure.

LOVELY PROFESSIONAL UNIVERSITY 25