CHAPTER 3

LINKED LIST

3.1. INTRODUCTION

“Linked list is an ordered collection of data in which each element contains the
location of the next element” [GILB98]. The elements in a linked list are called nodes. A
node in a linked list is a structure consisting of 2 fields: Data and Link.

“The major advantage of the linked list over other general list structure is that data
are easily inserted and deleted. It is not necessary to shift elements of a linked list to make
room for a new element or to delete an element.”[GILB98]

There are two types of linked list namely: Singly-Linked list and Doubly-Linked list.

3.2. SINGLY-LINKED LIST

Singly-linked list is a simple linked list structure in which each node has a pointer
that identifies the next element in the list. “Singly-linked list contains only one link to a
single successor” [GILB98].
Link field: contains the
address of the next node in
the list (successor)
DATA LINK

Data field: contains the

value of the node or
element
Figure 3.1 Format of a node in a Singly-linked list

Example:

19H 05H 15H

Romel 05H Renbert 15H Maryli NULL

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.2 Singly-linked list containing nodes Romel, Renbert and Maryli
 In the above example, we have illustrated a singly-linked list with three nodes. The
Head, which is the first node in the list contain data “Romel”. The Link field of the Head
points to the address of the next node. So, the successor of “Romel” is “Renbert” and the
successor of “Renbert” is “Maryli”. Since “Maryli" is the last node in the list, called the
TAIL, the value of its link field is set to NULL. This signifies the end of the list.

Both arrays and singly-linked list performs the same operations such as:

1. Reading the list from left to right

2. Retrieving the ith node in the list (where i≤ n)
3. Storing a new value into the ith position (where i≤ n)
4. Inserting a new node at position i (where i≤ n)
5. Deleting the ith element (where i≤ n)
6. Copying a list

3.2.1. Reading The Singly-Linked List From Left To Right

Reading elements in a singly-linked list would mean traversing each node from left to
right or from Head to Tail. In this way, we could determine the size of the linked list.

Read_List(Head)
{
If (Head ≠ NULL) then
{
Print Head -> Node.Data
Node_Count = 1
Next_Node = Head -> Node.Link
While(Next_Node is not NULL)
{
Print Next_Node -> Node.Data
Increment Node_Count
Next_Node = Next_Node -> Node.Link
}
Print “ Total Number of Nodes: “Node_Count
}
else
Print “ The list is Empty “
}

Algorithm 3.1 Reading the singly-linked list from HEAD to TAIL (left to right)
19H 05H 15H
Renbert 05H Maryli 15H Romel NULL

HEAD TAIL
 (BOTTOM) (TOP)

Figure 3.3 Singly-linked list containing nodes Renbert, Maryli and Romel,

Let us make use of the linked list above to illustrate the Algorithm 3-1.

|Head| |Node_Count| |Next_Node| Output: Renbert

19H 1 05H

Next_Node = Head -> Node.Link

= 19H -> 05H

while loop: 1st iteration:

|Head| |Node_Count| |Next_Node| Output: Renbert

19H 1 05H Maryli
2 15H

while loop: 2nd iteration:

|Head| |Node_Count| |Next_Node| Output: Renbert

19H 1 05H Maryli
2 15H Romel
3 NULL

Final Output:

Renbert
Maryli
Romel
Total Number of Nodes: 3
3.2.2. Retrieving The ith Node In A Singly-Inked Lsit

where: Node_Position is the desired position of the node to be retrieved

Retrieve_Node(Head, Node_Position)
{
If (Head ≠ NULL) then
{
Node_Count = 1
Next_Node = Head
While(( Node_Count < Node_Position) and (Next_Node is not NULL)
{
Increment Node_Count
Next_Node = Next_Node -> Node.Link
}
If (Next_Node ≠ NULL) then
Print Next_Node -> Node.Data
Else
Print “Sorry… the Node Position is more than the length of list”
}
else
Print “ The list is Empty “
}
Algorithm 3.2 Retrieving the ith node in a singly-linked list

Retrieving the ith node in a singly-linked list means traversing each node and finding
out which node is in the ith position. A counter should be set as a way of knowing how
many nodes are read and that corresponds to the position of the node.

To illustrate further let us make use of the linked list below in our examples (a and b).

09H 19H 05H 02H

A 19H B 05H C 02H D NULL

(1) (2) (3) (4)

HEAD TAIL

Position denoted by Node_Position variable

Figure 3.4 Singly-linked list containing nodes A,B,C,D

Example:

a)
|Head| |Node_Position| |Node_Count| |Next_Node| 09H
2 1 09H

while loop: 1st iteration |Node_Count| |Next_Node|

1 09H
2 19H
Output:
B

b)
|Head| |Node_Position| |Node_Count| |Next_Node| 09H
5 1 09H

while loop: 1st iteration |Node_Count| |Next_Node|

1 09H
2 19H

while loop: 2nd iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H

while loop: 3rd iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H
4 02H

while loop: 4th iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H
4 02H
5 NULL
Output:
Sorry… the Node Position is more than the length of list
 3.2.3. Storing A New Value Into The ith Node

where: Node_Position is the desired position of the node to be stored.

New_Value is the new value of the node to be stored

Store_Value(Head, Node_Position, New_Value)

{
If (Head ≠ NULL) then
{
Node_Count = 1
Next_Node = Head
While(( Node_Count < Node_Position) and (Next_Node is not NULL)
{
Increment Node_Count
Next_Node = Next_Node -> Node.Link
}
If (Next_Node ≠ NULL) then
Next_Node -> Node.Data = New_Value
Else
Print “Sorry… the Node Position is more than the length of list”
}
else
Print “ The list is Empty “
}

Algorithm 3.3 Storing a new data at ith position in a singly-linked list

09H 19H 05H 02H

M 19H E 05H R 02H L NULL

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.5 Singly-linked list containing nodes M,E,R,L

a)To simulate the Algorithm 3-3 we will use Figure 3-5

|Head| |Node_Position| |New Value| |Node_Count| |Next_Node| 09H

3 A 1 09H

while loop: 1st iteration |Node_Count| |Next_Node|

1 09H
2 19H
while loop: 2nd iteration |Node_Count| |Next_Node|
1 09H
2 19H
3 05H

Final Linked list:

09H 19H 05H 02H

M 19H E 05H A 02H L NULL

b)
|Head| |Node_Position| |New Value| |Node_Count| |Next_Node|
09H 5 S 1 09H

while loop: 1st iteration |Node_Count| |Next_Node|

1 09H
2 19H

while loop: 2nd iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H

while loop: 3rd iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H
4 02H

while loop: 4th iteration |Node_Count| |Next_Node|

1 09H
2 19H
3 05H
4 02H
5 NULL

Output:
Sorry… the Node Position is more than the length of list
 3.2.4. Inserting A Node In A Singly-Linked List

General procedure for inserting a new node at a certain position in a singly-linked

list:
1. Create a new node for the element
2. Set the data field of the new node to the value to be inserted
3. Insert the node

3.2.4.1. Inserting A Node At The Head Of A Singly-Linked List

1. Create a new node for the element

2. Set the data field of the new node to the value to be inserted
3. Set the link field of the new node to the value of HEAD.
4. Set the HEAD to the address of the new node

Example:
07H 03H 19H
Armin 03H Shan 19H Renbert Null

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.6 (a) Singly-linked list containing nodes Armin, Shan, and Renbert

Suppose we want to insert “Isay” at the start of the list. Following the procedure set
above:
1) Create a new node for the element “Isay”
08H

<Data field> <Link field>

2) Set the data field to “Isay”

08H
Isay

3) Set the link field to the value of Head. Since the address of Head is 07H,
it will be assigned to the link field of the new node.

08H 07H 03H 19H

Isay 07H Armin 03H Shan 19H Renbert Null

HEAD TAIL
 4) Set the HEAD to the address of the new node.

08H 07H 03H 19H

Isay 07H Armin 03H Shan 19H Renbert NULL

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.6 (b) Singly-linked list containing nodes Armin, Shan, and Renbert with
inserted new value “Isay”

This will signify that the start of the list is the new created node “Isay”.

Insert_Node_At_Head(Head, New_Value)
{
Where:
Create New Node
New_Value is the
Address of New Node -> Node.Data = New_Value
value of the node
Address of New Node -> Node.Link = Head
to be inserted
Head = Address of New Node
}

Algorithm 3.4 Inserting a new data at the Head of a singly-linked list

3.2.4.2. Inserting A Node At The Tail Of A Singly-Linked List

1. Create a new node for the element

2. Set the data field of the new node to the value to be inserted
3. Set the link field of the current last node to the address of the new node.
4. Set the link field of the new node to NULL
5. Set the TAIL to the address of the new node

Example:

15H 02H 09H

Lita 02H Bobby 09H Che NULL

HEAD TAIL

Figure 3.7 (a) Singly-linked list containing nodes Lita, Bobby and Che
 Suppose we want to insert “Mel” at the end of the list. Following the procedure set
above:
1. Create a new node for the element “Mel”
05H

<Data field> <Link field>

2. Set the data field to “Mel”

05H
Mel

3. Set the link field of the current last node to the address of the new node.

15H 02H 09H

Lita 02H Bobby 09H Che 05H

HEAD TAIL
(BOTTOM) (TOP)

4. Set the link field of the new node to NULL

05H

Mel NULL

5. Set the TAIL to the address of the new node

TAIL = 05H

So, the final list would be:

15H 02H 09H 05H

Lita 02H Bobby 09H Che 05H Mel NULL

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.7 (b) Singly-linked list containing nodes Lita, Bobby, Che with newly inserted
node Mel
 Insert_Node_At_Tail(Tail, New_Value)
{
Create New Node
Address of New Node -> Node.Data = New_Value
Address of New Node -> Node.Link = NULL
Tail -> Node.Link = Address of New Node
Tail = Address of New Node
}

Where: New_Value is the value of the node to be inserted

Algorithm 3.5 Inserting a new data at the Tail of a singly-linked list

3.2.5. Deleting A Node In A Singly-Linked List

3.2.5.1. Deleting The Node At The Head Of The Singly-Linked List

When we delete a node, we simply remove the link of that node to the rest of the
nodes. In this way, we logically deletes the node in the list. To physically delete the node,
we must FREE the node every time it is deleted.

To delete a node at the head of the list, set the variable HEAD to the address stored in
the link field of the node to be deleted.

Example.

12H 20H 31H 16H

Ros 20H Luisa 31H Robert 16H Mina NULL

HEAD TAIL
(BOTTOM) (TOP)

Figure 3.8 (a) Singly-linked list containing nodes Ros, Luisa, Robert and Mina

Since we would like to delete “Ros” we would assign 20H to be the HEAD.

HEAD = HEAD -> Node.Link

HEAD = 12H -.> 20H

 Therefore the value of the HEAD is 20H and the list would be:

12H 20H 31H 16H

Ros 20H Luisa 31H Robert 16H Mina NULL

HEAD TAIL

Figure 3.8 (b) Singly-linked list after deleting the link between “Ros” and “Luisa’

As you have noticed, the linked between “Ros” and “Luisa” was removed but the
node “Ros” is still there. If we want to physically delete “Ros” in the list, we must release
the node through using the function FREE().

After freeing the node, the list would be:

TAIL
20H 31H 16H
Luisa 31H Robert 16H Mina NULL
HEAD

Figure 3.8 (c) Singly-linked list after deleting node “Ros”

Delete_Head(Head)
{
Node_Address = HEAD
HEAD = HEAD -> Node.Link
Node_Address -> Node.Link = NULL /* logical deletion */
FREE(Node_Address) /* physical deletion */
}
Algorithm 3.6 Deleting the node at the Head of a singly-linked list

3.2.5.2. Deleting A Node At Position i

To delete a node at position i (where 1 ≤ i ≤ n ), we must first determine the

preceding node (that is the node i-1) then we set the link field of the preceding node (i-1) to
the value in the link field of the node to be deleted.

12H 20H 31H 16H

Nora 20H Luisa 31H Ellen 16H Sally NULL

HEAD TAIL
Figure 3-9 (a) Singly-linked list containing Nora, Luisa, Ellen and Sally
 Delete_At_Position_i(Head,i)
{
i=i-1
Ctr = 1
Next_Node = HEAD
While (Ctr < i )
{
Next_Node = Next_Node -> Node.Link
Increment ctr
}
Node_Address = Next_Node -> Node.Link
Next_Node -> Node.Link = Node_Address -> Node.Link
FREE(Node_Address)
}

Where: i is the position of the desired element to be deleted.

Node_Address is a temporary variable

Algorithm 3.7 Deleting the node at the Tail of a singly-linked list

12H 20H 31H 16H

Nora 20H Luisa 31H Ellen 16H Sally NULL
(1) (2) (3) (4)

HEAD TAIL

Position denoted by I

Figure 3-9 (b)

If i=2, then after executing the pseudocode (except FREE(Node_Address), the list would be:

12H 20H 31H 16H

Nora 31H Luisa 31H Ellen 16H Sally NULL

HEAD TAIL

As you have noticed, the linked between “Nora” and “Luisa”, was removed but the
node “Luisa” is still there. If we want to physically delete “Luisa” in the list, we must release
the node through using the function FREE().
After freeing the node, the list would be:
TAIL
12H 31H 16H
Nora 31H Ellen 16H Sally NULL
HEAD

So, the node “Luisa’ was removed physically in the memory.

Figure 3.9 (c) Singly-linked list after deleting the ith node.