Definition of linked list

Linked list or singly list is a linear data structure consisting of a group of elements called nodes which
together represent a linear sequence. Each node in linked list is composed of a data called info part and
a reference called link to the next node in the sequence. The link part of the last node contains NULL
value. This type of structural arrangement allows for efficient insertion or removal of elements at any
position in the linked list. Linked lists are can be used to implement several other abstract data types like,
stacks, queues, trees, graphs.

Figure 3.1 Simple linked list

The nodes that may seem sequential are not stored contiguously in memory. Link is used to move
from one node to the next node in the list. The major benefit of using a linked list over a conventional
array is that the elements (nodes) of the linked list can easily be inserted or removed without having to
reallocate or reorganize of the entire structure.

It is possible because the elements are not stored contiguously and insert/delete operation only requires
you to change the link between the nodes. Let us have a look at some of the advantages and
disadvantages of using linked list.

Advantages:

1. Dimension or size of the Linked list is dynamic in nature, i.e. memory can be allocated and de-
allocated as and when needed during the execution of the program.

2. Insert and delete operations are less costly and can be easily implemented in a linked list.

3. Non-primary or abstract linear data structures such as stacks and queues can be easily
implemented with a linked list.

Disadvantages:

1. With each node having to save the link to the next node, it results in wastage of memory.

2. We cannot access the nodes in a linked list randomly, i.e. Nodes in a linked list must be read in order
from the beginning as linked lists are inherently sequential access.

3. Nodes are stored non-contiguously in memory greatly increasing the time required to access
individual elements within the list.
4. Singly linked lists allow you to traverse only in the forward direction. It is possible to traverse backward
using doubly linked list, but it takes a lot of space in memory.

Memory representation of linked list

Figure 3.2 Memory representation of linked list

Here START = 2 means that the first node is stored at location 2.

INFO[2] = H and LINK[2]= 5. The next node is stored at location 5.

INFO[5] = E and LINK[5]= 3. The next node is stored at location 3.

INFO[3] = L and LINK[3]= 1. The next node is stored at location 1.

INFO[1] = L and LINK[1]= 8. The next node is stored at location 8.

INFO[8] = H and LINK[8]= 0 or NULL. It means that this is the last node in the list.

Traversing a linked list

Traversing is the most basic operation on a linked list. Traversing a linked list is visiting each node the
linked list exactly once. We can traverse only in the forward direction using the linked list starting from the
first node to the last node.

Let LIST be the linked list to be traversed. START pointer contains the address of the first node. Each
node consists of two parts: INFO and LINK. LINK part of a node contains the address of the next node
and the LINK part of the last node contains NULL.

The algorithm uses a PTR pointer that points to the node being currently processed. The algorithm starts
by assigning the address of the first node to the PTR pointer and then processes each node in the
sequence till the last node is processed. PTR can point to the node next to the current node using the
following statement:

PTR = LINK[PTR]

Figure 3.3 PTR pointing to the next node in the LIST

ALGORITHM TRAVERSE (TRAVERSING A LINKED LIST) Apply PROCESS

operation to the linked list (LIST). PTR contains the address of the node being
currently processed and SRART contains the address of the first node in the list.

1. Set PTR = START [initialize the pointer the first node]

2. Repeat the steps 3 and 4 while PTR != NULL [till the end of the list]

3. Apply PROCESS to INFO[PTR] [perform the operation]

4. Set PTR = LINK[PTR] [PTR now points to the next node in the list]
[End of step 2 loop]

5. Exit

For example, the following algorithm finds the sum of all elements of the linked list.
 ALGORITHM SUM (INFO, LINK, START, COUNT) the algorithm finds the sum of all
elements of the linked list

1. Set COUNT = 0 [initialize the count]

2. Set PTR = START [initialize the pointer the first node]

3. Repeat the steps 3 and 4 while PTR != NULL [till the end of the list]

4. COUNT = COUNT + INFO[PTR] [compute sum of nodes till the current

node]

5. Set PTR = LINK[PTR] [PTR now points to the next node in the list]
[End of step 2 loop]

6. Display COUNT

7. Exit

Searching in a linked list

Let LIST be the linked list in memory. Suppose we want to search for ITEM in the linked list. The search
algorithm returns the LOC of the ITEM stored in memory. Linear search algorithm is used to search for
ITEM in the list. Beginning from the first node, algorithm searches for the ITEM in the list sequentially. The
search algorithm can be categories into following categories:

Searching in sorted LIST

The algorithm searches for ITEM in linked list sequentially beginning from the first node until a node with
greater value then ITEM is encountered.
 ALGORITHM SRCHSORTED (INFO, LINK, PTR, LOC, START, ITEM) the algorithm
searches for ITEM in sorted LIST. START points to the first node in the LIST and PTR
is used to traverse through the LIST.

1. Set PTR = START [Initialize PTR]

2. Repeat steps While PTR != NULL

3. if ITEM > INFO[PTR], Then

PTR = LINK[PTR] [PTR now points to the next node in the list]

else if ITEM = INFO[PTR], Then

set LOC = PTR and exit [search successful]

else

set LOC = NULL and exit [search unsuccessful]

[End of if]

[End of step 2 Loop]

4. Set LOC = NULL [search unsuccessful]

5. Exit

Searching in unsorted LIST

The algorithm searches for ITEM in linked list sequentially beginning from the first node till the last node.
Because the LIST is unsorted, there is no mechanism to identify the direction in which the ITEM is stored
in the LIST
 ALGORITHM SRCHSORTED (INFO, LINK, PTR, LOC, START, ITEM) The
algorithm searches for ITEM in unsorted LIST. START points to the first node
in the LIST and PTR is used to traverse through the LIST.

1. Set PTR = START [Initialize PTR]

2. Repeat steps While PTR != NULL

3. if ITEM = INFO[PTR], then

set LOC = PTR and exit [search successful]

else if

PTR = LINK[PTR] [PTR now points to the next node in the list]

[End of if]

[End of step 2 Loop]

4. Set LOC = NULL [search unsuccessful]

5. Exit

Memory allocation and garbage collection

A linked list is dynamic data structure and it is believed to have the possibility of inserting new nodes into
the list and hence requires some mechanism which provides information about unused memory space for
storing the new nodes. Also, some mechanism is needed whereby during the delete operation the
memory space of deleted node becomes available for future use. Together with the linked lists (that is
memory is use) in memory, a special list is maintained which consists of all unused memory cells. Such a
list is called free- storage list or free pool.

The unused memory cells are linked together to form a linked list with AVAIL as its pointer variable.
AVAIL points to the first node in the free pool list.
 Figure 3.4 Memory representation of AVAIL LIST

The memory cells in the figure above are divided into two categories: used and unused cells. The unused
cells are linked together and the location of the first free node is stored in pointer called AVAIL.
Here AVAIL = 7 means that the first free node in the list is location 2.

LINK[7] = 4. The next free node in the list is location 5.

LINK[4] = 10. The next free node in the list is location 10.

LINK[10] = 6. The next free node in the list is location 6.

LINK[6] = 9. The next free node in the list is location 9.

LINK[9] = 0. The location 9 is the last free node in the list.

When a node is inserted in the list, the first node in the AVAIL list is removed and added to the list and the
second node in the AVAIL list becomes the first node. Sometimes a node is deleted from the list or even
the entire list may be deleted. There needs to be a mechanism to reuse the space deleted for future use.
One method is to insert the deleted node into the AVAIL list immediately when it is deleted. Other then
this operating system also provides alternate methods to achieve the same.

The operating system of a computer from time to time collects all the deleted space onto the free pool list.
The technique that does this collection is called garbage collection. Garbage collection is done by
operating system in two steps. Firstly the operating system runs through all lists, tagging cells which are
currently in use, and then the operating system runs through the memory, collecting all untagged spaces
onto the free pool list. Garbage collection by operating system is invisible to the programmer and the
programmer doesn’t need to worry about the same.

Checking underflow and overflow conditions

Before we start with the insert and delete operations on the linked list, it is important to understand the
concept of underflow and overflow conditions. The situation when we want to insert new data and there is
need to dynamically allocate memory into the linked list, but there is no available space as free pool list is
empty; is called overflow. The overflow condition occurs with our linked lists when AVAIL = NULL and we
want to perform insert operation. Overflow condition should be checked right at the beginning of the insert
operation and in case the condition returns TRUE, the algorithm should display overflow message and
terminate. Similarly, underflow refers to the situation where there is a request for delete operation on the
list and list is empty. The underflow condition occurs with our linked list when START = NULL and we
want to perform delete operation. Underflow condition should be checked right at the beginning of the
delete operation and in case the condition returns TRUE, the algorithm should display underflow message
and terminate.

Inserting into a linked list

Before we apply the insert operation on the linked list, one must check for the overflow condition,

if AVAIL = NULL

The last condition is used to check if the overflow condition is true or not. In case the condition returns
true, the algorithm must exit immediately.

If the overflow condition is false, we can proceed to insert a node to the linked list. The first step is to
obtain a free node from the AVAIL list and store the location of the same in NEW pointer. It can be
achieved using the following two statements:

NEW = AVAIL
AVAIL = LINK[AVAIL]

Figure 3.5 Assigning a node to NEW pointer from the AVAIL list

(NEW = AVAIL) assigns the location of first node in the free pool list to NEW.
(AVAIL = LINK[AVAIL]) assigns the location of second node in the free pool list to AVAIL. Now the
second node becomes the first node in the free pool list.

Inserting at the beginning of the list

The following algorithm is used to insert a NEW node at the beginning of the LIST.

INSBEG (INFO, LINK, START, AVAIL, and ITEM)

the algorithm inserts ITEM as the first node of the LIST.
1. if AVAIL = NULL then, Display: OVERFLOW and exit.
2. [Assign node from free pool list to NEW]
Set NEW = AVAIL
3. [Assign second node in the free pool list to AVAIL]
AVAIL = LINK[AVAIL].
4. Set INFO[NEW] = ITEM. [Copy ITEM to NEW]
5. Set LINK[New] = START [New node now points to previous first
node]
6. Set START = NEW. [NEW becomes the first node]
7. Exit.

Figure 3.6 Inserting NEW node to the beginning of the linked list

Inserting after a given node

The following algorithm is used to insert a NEW node at the beginning of the LIST.
 INSLOC(INFO, LINK, START, AVAIL, ITEM, LOC)
The algorithm inserts ITEM after the node being pointed by LOC.

1. if AVAIL = NULL then, Display: OVERFLOW and exit.

2. [Assign node from free pool list to NEW]
Set NEW = AVAIL
3. [Assign second node in the free pool list to AVAIL]
AVAIL = LINK[AVAIL].
4. Set INFO[NEW] = ITEM. [Copy ITEM to NEW]
5. if LOC= NULL, then
[make new the first node of the LIST]
Set LINK[New] = START and START = NEW
else
Set LINK[NEW] = LINK[LOC] and LINK[LOC] = NEW
[end of if]
5. Exit.

Figure 3.7 Inserting NEW node after node X in the list

Deleting from linked list

Before we apply the delete operation on the linked list, one must check for the underflow condition,

if START = NULL

The last condition is used to check if the underflow condition is true or not. In case the condition returns
true, the algorithm must exit immediately.
If the underflow condition is false, we can proceed to delete a node from the linked list. The first step is to
add the node to be deleted to the AVAIL list and change the LNIK of the previous node accordingly. It can
be achieved using the following two statements:

LINK[LOC] = AVAIL and AVAIL = LOC

Figure 3.8 Assigning the location of deleted node to AVAIL

(LINK[LOC] = AVAIL) assigns the location of first node in the free pool list to LOC (node to be
deleted).

(AVAIL = LOC) assigns the node pointed by LOC to AVAIL. So, LOC becomes the first node of the
free pool list. Let us have a look at the algorithm to perform delete operation on linked list.
 DELETE (INFO, LINK, START, AVAIL, LOCP, LOC)
The algorithm deletes the node LOC. LOCP is the location of the node
previous to LOC in the list.

1. if START = NULL, then

Display: underflow and exit.

2. if LOCP = NULL, then

[delete first node]

Set START = LINK[START]

Else

[remove node other than first node]

Set LINK[LOCP] = LINK[LOC]

[end of if statement]

3. Set LINK[LOC] = AVAIL and AVAIL = LOC

4. EXIT

When LOCP = NULL (delete first node)

Figure 3.9 Deleting first node

Otherwise,
 Figure 3.10 Deleting node other than the first node

Header linked list

Header linked list is one that contains a special node at the beginning of the list called header node. The
header node is not part of the actual list, but it is used to contain information about the linked list such as,
number of nodes, name of the list, purpose of creating list, etc.

Basically we have two types of header lists,

1. Grounded header list- It is one in which the LINK part of the last node contains NULL value.

Figure 3.11 Grounded header linked list

START points to the first node in the grounded header list. But header node is not the first node on the
list. LINK[START] is the location of the first node in the list. In case, LINK[START] = NULL means the list
is empty.

2. Circular header list- It is one in which the LINK part of the last node contains location or
address of the first node in the list.

Figure 3.12 Circular header linked list

In case of circular header list, if LINK[START] = START means the list is empty.

ALGORITHM TRAVCIR (TRAVERSING A CIRCULAR LINKED LIST) Apply PROCESS

operation to the circular linked list (LIST). PTR contains the address of the node
being currently processed and LINK[START] contains the address of the first node
in the list.

1. Set PTR = LINK[START] [initialize the pointer the first node]

2. Repeat the steps 3 and 4 while PTR != START [till the end of the list]

3. Apply PROCESS to INFO[PTR] [perform the operation]

4. Set PTR = LINK[PTR] [PTR now points to the next node in the list]
[end of step 2 loop]

5. Exit

Two-way or doubly linked list

Two-way list is a special list which can be traversed in both directions; forward direction from the first
node to the last node and backward direction from the last node to the first node. Using two-way list, we
can access both the next and previous nodes to the current node which makes it possible to delete a
without traversing any part of the list.

A node in a two-way list is divided into three parts:

Information field INFO that contains the data part of the node.
A pointer field FORW that contains the location of the next node to the current node in the list.
A pointer field BACK that contains the location of the preceding node to the current node in the list.

Figure 3.13 Two-way list

The list also requires two list pointer variables: FIRST, which points to the first node in the list, and LAST,
which points to the last node in the list. Observe that the NULL pointer appears in the FORW field of the
last node in the list and also in the BACK field of the first node in the list. Observe that, using the variable
FIRST and the pointer field FORW, we can traverse a two-way list in the forward direction as before. On
the other hand, using the variable LAST and the pointer field BACK, we can also traverse the list in the
backward direction.
Two-way header list

Two-way header list consists of a special header node which has two pointers. One points to the first
node in the list and the second points to the last node in the list. Also the BACK field of the first node in
the list points to the header node and FORW field of the last node in the list points to the header node.

Figure 3.14 Two-way header list

Traversing the two-way list backwards

ALGORITHM TRAVERSEBACK (TRAVERSING A two-way LIST) Apply PROCESS

operation to the linked list (LIST). PTR contains the address of the node being
currently processed and LAST contains the address of the last node in the list.

1. Set PTR = LAST [initialize the pointer to last node]

2. Repeat the steps 3 and 4 while PTR != NULL [till the beginning of the list]

3. Apply PROCESS to INFO[PTR] [perform the operation]

4. Set PTR = BACK[PTR] [PTR now points to the preceding node in the list]
[end of step 2 loop]

5. Exit

We can perform the delete operation on two-way list using the following statements:

FORW [ BACK[LOC] ] = FORW[LOC]

BACK [ FORW[LOC] ] = BACK[LOC]

FORW[LOC] = AVAIL
AVAIL = LOC
We can perform the INSERT operation on two-way list using the following statements:

CONSIDER that we want to insert node NEW between nodes LOCA and LOCB in the list.

NEW = AVAIL
AVAIL = FORW[AVAIL]
INFO[NEW] = ITEM

FORW[LOCA] = NEW
FORW[NEW] = LOCB
BACK[LOCB] = NEW
BACK[NEW] = LOCA