MODULE II

LINKED LIST
DEFINITION
A linked list is an ordered collection of finite, homogeneous data elements called nodes where the linear
order is maintained by means of links or pointers. The linked list can be classified into three major groups:
single linked list, circular linked list, and double linked list.

SINGLE LINKED LIST

In a single linked list each node contains only one link which points to the subsequent node in the list.
Figure shows a linked list with six nodes. Here, Nl, N2, ... , N6 are the constituent nodes in the list.
HEADER is an empty node (having data content NULL) and only used to store a pointer to the first node
Nl. Thus, if one knows the address of the HEADER node from the link field of this node, the next node can
be traced, and so on. This means that starting from the first node one can reach to the last node whose link
field does not contain any address but has a null value.

REPRESENTATION OF LINKED LIST IN MEMORY

There are two ways to represent a linked list in memory:
Static representation using array and Dynamic representation using free pool of storage
Static representation: In static representation of a single linked list, two arrays are maintained: one array for
data and the other for links. The static representation of the linked list in above Figure is shown in below
Figure.

1
 Two parallel arrays of equal size are allocated which should be sufficient to store the entire linked list.
Nevertheless this contradicts the idea of the linked list (that is non-contagious location of elements). But in
some programming languages, for example, ALGOL, FORTRAN, BASIC, etc. such a representation is the
only representation to manage a linked list.
Dynamic representation
The efficient way of representing a linked list is using the free pool of storage. In this method, there is a
memory bank (which "is nothing but a collection of free memory spaces) and a memory manager (a
program, in fact). During the creation of a linked list, whenever a node is required the request is placed to

the memory manager; the memory manager will then search the memory bank for the block requested and,
if found, grants the desired block to the caller. Again, there is also another program called the garbage
collector; it plays whenever a node is no more in use; it returns the unused node to the memory bank. It may
be noted that memory bank is basically a list of memory' spaces which is available to a programmer. Such a
memory management is known as dynamic memory management. The dynamic representation of linked
list uses the dynamic memory management policy.
The mechanism of dynamic representation of single linked list is illustrated in Figures (a) and (b). A list of
available memory spaces is there whose pointer is stored in AVAIL. For a request of a node, the list AVAIL
is searched for the block of right size. If AVAIL is null or if the block of desired size is not found, the
memory manager will return a message accordingly. Suppose the block is found and let it be XY. Then the
memory manager will return the pointer of XY to the caller in a temporary buffer, say NEW. The newly
availed node XY then can be inserted at any position in the linked list by changing the pointers of the

2
concerned nodes. In Figure (a), the node XY is inserted at the end and change of pointers is shown by the
dotted arrows. Figure (b) explains the mechanism of how a node can be returned from a linked list to the
memory bank.

The pointers which are required to be manipulated while returning a node are shown with dotted arrows.
Note that such allocations or deallocations are carried out by changing the pointers only.

OPERATIONS ON SINGLY LINKED LIST

The operations possible on a single linked list are listed below: Traversing the list, Inserting a node into the
list, Deleting a node from the list, Copying the list to make a duplicate of it, Merging the linked list with
another one to make a larger list, Searching for an element in the list.

suppose X is a pointer to a node. The values in the DATA field and LINK field will be denoted by
XDDATA and XDLINK, respectively, We will write NULL to imply nil value in the DATA and LINK
fields.

1. Traversing a single linked list

In traversing a single linked list, we visit every node in the list starting from the first node to the last node.
The following is the algorithm Traverse_SL for the same.
Algorithm Traverse_SL
Input: HEADER is the pointer to the header node.
Output: According to the Process( )
Data structures: A single linked list :-vhose address of the starting node is known from the HEADER.

2. Inserting a node into a single linked list

There are various positions where a node can be inserted:
(i) Inserting at the front (as a first element)
(ii) Inserting at the end (as a last element)
(iii) Inserting at any other position.

3
Let us assume a procedure GetNode(NODE) to get a pointer of a memory block which suits the type NODE.

The procedure may be defined as follows:

Inserting a node at the front of a single linked list

The algorithm lnsertliront Sl: is used to insert a node at the front of a single linked list.

4
Inserting a node at the end of a single linked list
The algorithm InsertEnd_SL is used to insert a node at the end of a single linked list

5
Inserting a node into a single linked list at any position in the list
The algorithm InsertAny _SL is used to insert a node into a single linked list at any position in
the list.

6
3. Deleting a node from a single linked list
Like insertions, there are also three cases of deletions:
(i) Deleting from the front of the list
(ii) Deleting from the end of the list
(iii) Deleting from any position in the list
Assume a procedur namely ReturnNode(ptr) which returns a node having pointer ptr to the free pool of

storage. The procedure ReturnNode(ptr) is defined as fallows.

Deleting the node at the front of a single linked list

The algorithm Deleteliront Sl: is used to delete the node at the front of a single linked list. Such
a deletion operation is explained in Figure 3.6(a).

7
Deleting the node at the end of a single linked list
The algorithm DeleteEnd_SL is used to delete the node at the end of a single linked list.

8
DeletIng the node from any position of a single linked list

The algorithm DeleteAny _SL is used to delete a node from any position in a single linked list.

4. Searching an element in a single linked list

9
CIRCULAR LINKED LIST

In a single linked list, the link field of the last node is null (hereafter a single linked list may be read as
ordinary linked list), but a number of advantages can be gained if we utilize this link field to store the
pointer of the header node. A linked list where the last node points the header node is called the circular
linked list. Figure shows a pictorial representation of a circular linked list.

Circular linked lists have certain advantages over ordinary linked lists. Some advantages of circular
linked lists are discussed below:
Accessibility of a member node in the list
In an ordinary list, a member node is accessible from a particular node, that is, from the header node only.
But in a circular linked list, every member node is accessible from any node by merely chaining through the
list.

Example: Suppose, we are manipulating some information which is stored in a list. Also, think of a case
where for a given data, we want to find the earlier occurrence(s) as well as post occurrence(s). Post
occurrence(s) can be traced out by chaining through the list from the current node irrespective of whether
the list is maintained as a circular linked or an ordinary linked list. In order to find all the earlier
occurrences, in case of ordinary linked lists, we have to start our traversing from the header node at the cost
of maintaining the pointer for the header in addition to the pointers for the current node and another for
chaining. But in the case of a circular linked list, one can trace out the same without maintaining the header
information, rather maintaining only two pointers. Note that in ordinary linked lists, one can chain through

10
left to right only whereas it is virtually in both the directions for circular linked lists.

Null link problem

The null value in the link field may create some problem during the execution of programs if proper care is
not taken. This is illustrated below by mentioning two algorithms to perform search on ordinary linked
lists and circular linked lists.

Some easy-to-implement operations

Some operations can more easily be implemented with a circular linked list than with an ordinary linked list.
Operations like merging (concatenation), splitting (decatenation), deleting, disposing of an entire list, etc.

11
 DOUBLE LINKED LISTS
In a single linked list one can move beginning from the header node to any node in one direction only (from
left to right). This is why a single linked list is also termed a one-way list. On the other hand, a double
linked list is a two-way list because one can move in either direction, either from left to right or from right
to left. This is accomplished by maintaining two link fields instead of one as in a single linked list. A
structure of a node for a double linked list is represented as in Figure.

Figure Structure of a node and a double linked list.

From the figure, it can be noticed that two links, viz. RLINK and LLINK, point to the nodes on the right
side and left side of the node, respectively. Thus, every node, except the header node and the last node,
points to its immediate predecessor and immediate successor.

REPRESENTATION OF STACK AS ALINKED LIST

First, we have to understand what a linked list is, to understand linked list representation of a stack. A Linked
List is a Data Structure which consists of two parts:

 The data/value part.

 The pointer which gives the location of the next node in the list.

Stack can also be represented by using a linked list. We know that in the case of arrays we face a limitation , i.e
, array is a data structure of limited size. Hence before using an array to represent a stack we will have to
consider an enough amount of space to suffice the memory required by the stack.

12
However, a Linked List is a much more flexible data structure. Both the push and pop operations can be
performed on either ends.. But We prefer performing the Push and pop operation at the beginning.

But performing the operations at the beginning occurs in constant time. Let us understand this with the help of
an example.

Let us consider a linked list as shown here.

In the given data we can see that we have-

 Head = 200.
 Top = 33.

13
 Push / Pop At the end Of a Linked List
Consider the Linked List as shown above. Now if we want to push/pop a node at the end, we have to traverse
all the n number of nodes, until we reach the end of the linked list.

We traverse the whole list from the beginning to the end.

 Now if we want to insert a node at the end of the linked list, we traverse from the first node to the
second node to the last node.
 We find the end of the list where the node points to the null and the node to be inserted is as shown
here.

 The new node is pushed at the end of the list.

 The second last node , i.e, 08 now points to the location of the last node.
 The newly inserted node at the end now points to null.

Push / Pop operation at the beginning of the Linked List

Pushing a new node at the beginning of a linked list takes place in constant time. When inserting the new node
the number of traversals that occur is equal to 1. So it is much faster than the previous method of insertion

Let us consider the previous example only. We are given a Linked List as follows:

14
 A new node to be inserted to the Linked List is shown here.
 The new node 40 is to be inserted at the beginning of the list.

 The new node is inserted at the beginning where we have just a single traversal after spotting the head
of the Linked List.
 The value of head changes from 200 to 100.
 The pointer of the new node stores the address of the next node.
 The final linked list is shown here.

15
REPRESENTATION OF QUEUE AS ALINKED LIST
enqueue(data)

 Build a new node with given data.

 Check if the queue is empty or not.
 If queue is empty then assign new node to front and rear.
 Else make next of rear as new node and rear as new node.

dequeue()

 Check if queue is empty or not.

 If queue is empty then dequeue is not possible.
 Else store front in temp
 And make next of front as front.

print()

 Check if there is some data in the queue or not.

 If the queue is empty print “No data in the queue.”
 Else define a node pointer and initialize it with front.
 Print data of node pointer until the next of node pointer becomes NULL.

16
Algorithm for enqueue(int d)

 STRUCT NODE* NEW_N

 NEW_N->DATA = D
 NEW_N->NEXT = NULL
 IF((FRONT == NULL)&&(REAR == NULL))
 FRONT = REAR = NEW_N
 ELSE
 REAR->NEXT = NEW_N
 REAR = NEW_N

Algorithm for dequeue()

 STRUCT NODE *TEMP

 TEMP = FRONT
 IF((FRONT == NULL)&&(REAR == NULL))
 RETURN
 ELSE
 FRONT = FRONT->NEXT
 FREE(TEMP)

print()

 STRUCT NODE* TEMP

 IF((FRONT == NULL)&&(REAR == NULL))
 RETURN
 ELSE
 TEMP = FRONT
 WHILE(TEMP)
 RETURN TEMP->DATA
 TEMP = TEMP->NEXT

17
18