Lecture Notes Series for

CSC 204: Fundamentals of Data Structures

Unit 4: Lists and Linked Lists

Dr Fatimah Adamu-Fika

Department of Cyber Security

Faculty of Computing

Air Force Institute of Technology

Kaduna, Nigeria

Version of 2020/2021 Academic Session

© 2020-2022
 CSC 204: FUNDAMENTALS OF DATA STRUCTURES

UNIT 4: LISTS AND LINKED LISTS

TABLE OF CONTENTS

Overview and Concepts .............................................................................................................................. 4

The List ADT ............................................................................................................................................... 4

Specifying a List ADT ............................................................................................................................................5
Implementating a List ..........................................................................................................................................5

Types of Linked List .................................................................................................................................... 6

SinglY Linked List ..................................................................................................................................................6
SLL Representation ..........................................................................................................................................8
Summary of SLL Properties .............................................................................................................................9
Doubly Linked List ................................................................................................................................................9
DLL Representation ...................................................................................................................................... 10
Summary of DLL Properties .......................................................................................................................... 11
Cirular linked list ............................................................................................................................................... 11
Circular Linked List Representation .............................................................................................................. 12
Summary of Circular Linked List Properties ................................................................................................. 13

Basic Behaviour of A Linked List ................................................................................................................ 13

Insertion Operation ........................................................................................................................................... 13
Inserting a New Node into a Singly Linked List ............................................................................................ 14
Inserting a New Node into a Doubly Linked List .......................................................................................... 19
Inserting a New Node into a Circular Linked List ......................................................................................... 22
Deletion Operation............................................................................................................................................ 22
Deleting An Element from a Singly Linked List ............................................................................................. 22
Deleting An Element from a Doubly Linked List ........................................................................................... 25
Deleting An Element from a Circular Linked List .......................................................................................... 28
Traversal Operation .......................................................................................................................................... 28
Forward Traversal......................................................................................................................................... 29
Backwards Traversal..................................................................................................................................... 30
Traversal of a Circular Linked List ................................................................................................................. 30
Search Operation .............................................................................................................................................. 32

Trade-offs ................................................................................................................................................ 33
Summary of Complexity of Linked List Operations ........................................................................................... 33
Linked Lists vs Static Arrays .............................................................................................................................. 33
Linked Lists vs Dynamic Arrays ......................................................................................................................... 34
Singly Linked List vs Doubly Linked List ............................................................................................................. 35
Circular Linked List vs Linearly Linked List......................................................................................................... 35

Summary ................................................................................................................................................. 35
Notes and What Comes Later ........................................................................................................................... 36
Exercises.................................................................................................................................................. 36
 OVERVIEW AND CONCEPTS

• A linked list is a sequence of ordered non-contiguous components of similar types, i.e., a linked
list is a linear data structure that does not store elements in contiguous memory locations. A
linked list, when it organises data items in random memory locations, maintains its linearity by
using pointers (or references or links) to connect each data item to its neighbour in the list.
• Items stored in a linked list are called elements. Each element is stored in the form of a node.
A node is a collection of at least two sub-fields or parts: a data field that stores the element
itself (i.e., the value of the element) and a pointer field that stores a reference link to the next
node. Sometimes, a linked list has a second pointer field that stores a reference link to the
previous node.
• A linked list is formed when several such nodes are linked together to form a chain, with each
node pointing to the location (address) of the next node in order. And in some cases, it also
points to the location (address) of the previous node in the sequence.
• A linked list contains a connection to the first node called 𝒉𝒆𝒂𝒅. This serves as a handle to the
to the entire list and is usually used as the starting reference to traverse the list. The last node
of a linked list points to null. When the list is empty, head points to null.
• A linked list may contain a connection to the last node, this is called 𝒕𝒂𝒊𝒍. In a linked list where
nodes are pointing to their predecessors, the list can be traversed in reverse order using the
𝑡𝑎𝑖𝑙 as the starting point.
• In the chain, the next node to a node is called its successor, and the previous node to it is called
its predecessor.
• Linked lists can dynamically increase in size and it is easy to insert or delete from a linked list.
We only need to change the link to the next (and previous) element when inserting or deleting
an element.
• A linked list is assessed sequentially, this means to find an element in a linked list, the search
must always start at a given node, usually the head (or tail).
• A linked list with one connection, i.e., having only a single pointer field that points to its
successor node, is a simple linked list, and is called a singly linked list. While a linked list with
two connections, i.e., having two pointer fields that point to both the successor and
predecessor nodes, is called a doubly linked list.
• A linked list is an implementation of a List ADT.

Example 1: Let’s revisit our student’s score example from Example 1 in Arrays Unit, . The scores in the
five CSC204 assessments, {6, 9, 7, 9, 10}, can be stored in a linked list instead of an array. The 𝑠𝑐𝑜𝑟𝑒
linked list will be physically stored at non-contiguous memory locations. Each score will have an
associated reference variable holding the address of the next score in the sequence. The address of the
first score is stored in the head.

THE LIST ADT

A list is an abstract data type that represents an arbitrary sequence of elements. An element in a list
can occur more than once, i.e., elements in a list must not be unique. However, if the same element
occurs multiple times, each occurrence is considered a distinct item.

The elements of a list are ordered in the sense that each element has a position in the list, and the
elements can be arranged according to their values.

Each element of a list must have a data type. It is commonly assumed that all elements of a list have
the same data type.
A list is empty when it contains no elements. The number of elements currently stored in a list is
referred to as the length of the list. The beginning of the list is called the head of the list and the end of
it is called the tail.

A list can grow and shrink as elements are added to and removed from it. Elements can be added or
removed from any position in the list. Each element of a list must be accessible, and its value editable.
Elements of a list are iterable or traversable, i.e., the next or previous element in the sequence can be
accessed from the current position. A list can be created or cleared.

SPECIFYING A LIST ADT

We can specify the ADT for a sequence of objects in terms of the set of operations on that objects.
From our discussion, we can identify some typical operations of a list as follows:

• a constructor for creating an empty list.

• Clear (or empty): Removes all contents from the list, so it is once again empty
• insert (or add): Inserts an element at the current position.
• append: Inserts an element at the end of the list.
• prepend: Inserts an element at the beginning of a list.
• delete (or remove): Removes an element at the current position. This could be at the
beginning, the end or somewhere in the middle of the list.
• previous: Moves the current position one place to the left, that is move to the predecessor
node.
• next: Moves the current position one place to the right, that is move to the successor node.
• length: Return the number of elements currently in the list.
• currentPosition: Returns the position of the current element.
• isEmpty: Check whether or not the list contains any element. Return true if a list has no
elements.
• isAtEnd: Check whether or not the current position is at the end of the list. Return true if the
current position is at the tail.
• getValue: Return the value of the current element.
• moveToStart: Set the current position to head, i.e., move to the beginning of the list.
• moveToEnd: Set the current position to tail, i.e., move to the end of the list.
• moveToPosition: Move the current position to a given element.
• find: Finds an element in a list. Return true if element is found and false otherwise.

IMPLEMENTATING A LIST

Lists are commonly implemented either as a linked list (either singly or doubly linked) or as an array,
usually of variable length, i.e., a dynamic array. The linked list implementation is the most typical
implementation.

In Java, list is implemented by the class library java.util.ArrayList (array-based implementation) and
java.util.LinkedList (linked-list-based implementation). And an Iterator object is used to traverse the
elements of a list.

List has efficient linear time implementations using both arrays and linked lists.

The List ADT is one of the common ADTs, and it is more general than the Stack, Queue and Set ADTs
and it can be used to implement these ADTs.
 TYPES OF LINKED LIST

A linked list can be classified based on the direction it can be navigated, i.e., based on how many
connections exists between adjacent nodes.

1. Simple or Singly Linked List (SLL): Elements navigation is unidirectional going forward only. An
SLL has a single reference link to its successor in the list. And the successor of the last node is
null. The head of an empty SLL points to null.
2. Doubly Linked List (DLL): A doubly linked list is a variation of singly linked list; it has an additional
pointer field that links a node to its predecessor in the list. As such, elements navigation is bi-
directional going either forward or backwards. The predecessor of the first node of a doubly
linked list is null. A DLL has a reference node, tail, that points to the last node of the list. The
predecessor of the tail of an empty DLL points to null

A linked list can also be defined based on its linearity. So far, we have been discussing linear linked lists.
A non-linear linked list is called a circular linked list. A circular linked link can be either singly or doubly
linked. In a circular linked list, the last node points forward to the starting node of the list as its
successor, and if it is doubly linked, the first node points back to the last node of the list as its
predecessor.

SINGLY LINKED LIST

Linked Lists can be declared in various ways in different languages. For example, in Java, one of the
ways you can declare a linked list is by using user-defined classes. The declaration of arrays is simple as
it is a single type. But singly linked lists contain two parts, which are of two different types, i.e., one is a
simple variable, and the second is a “pointer” variable.

Example 2: The following is an example of an implementation of an SLL in Java:

𝒑𝒖𝒃𝒍𝒊𝒄 𝒄𝒍𝒂𝒔𝒔 𝑆𝑖𝑛𝑔𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡 {

// 𝑓𝑖𝑟𝑠𝑡 𝑛𝑜𝑑𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡

𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 ℎ𝑒𝑎𝑑;

// 𝑐𝑜𝑛𝑠𝑡𝑟𝑡𝑢𝑐𝑡𝑜𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑆𝑖𝑛𝑔𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡

𝒑𝒖𝒃𝒍𝒊𝒄 𝑆𝑖𝑛𝑔𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡(){
𝒕𝒉𝒊𝒔. ℎ𝑒𝑎𝑑 = 𝒏𝒖𝒍𝒍;
}

// 𝑖𝑛𝑛𝑒𝑟 𝑐𝑙𝑎𝑠𝑠 𝑓𝑜𝑟 𝑎 𝑐𝑟𝑒𝑎𝑡𝑖𝑛𝑔 𝑎𝑛 𝑆𝐿𝐿 𝑛𝑜𝑑𝑒

𝒑𝒖𝒃𝒍𝒊𝒄 𝒄𝒍𝒂𝒔𝒔 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 {
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝑂𝑏𝑗𝑒𝑐𝑡 𝑣𝑎𝑙𝑢𝑒;
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑛𝑒𝑥𝑡;

𝒑𝒖𝒃𝒍𝒊𝒄 𝑆𝐿𝐿𝑁𝑜𝑑𝑒( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑎𝑡𝑎 ) {

𝑡ℎ𝑖𝑠. 𝑣𝑎𝑙𝑢𝑒 = 𝑑𝑎𝑡𝑎;
𝑡ℎ𝑖𝑠. 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙;
}
}
}

In the code snippet in Example 2, the node of the SLL is implemented as an inner class within the
implementation of the SLL Class. This SLLNode class can be implemented as an external class. The code
only shows the implementation of the constructor of the 𝑆𝑖𝑛𝑔𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡 and not the other class
methods that implements other operations of the list. We will see snippet codes of these class methods
when we discuss operations of a linked list.

We can go ahead and declare a linked list using our 𝑆𝑖𝑛𝑔𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡 class as shown in Figure 1.

Name of SinglyLinkedList
variable

SinglyLinkedList score = new SinglyLinkedList()

Empty Singly Linked List

FIGURE 1. DECLARING AN SLL USING A USER-DEFINED CLASS

Figure 1 will create an empty linked list, later on we will use linked list operations to populate the list.

Similarly, we can use Java in built Linked List collection to declare linked lists as shown in Figure 2.

Name of Linked List

LinkedList<Type> score = new LinkedList<Type>()

Type here indicates the data Empty Singly Linked List

type of linked list, i.e., the type
of elements it will hold. In our
score examples Type will be
Integer.

FIGURE 2. DECLARING AN SLL USING JAVA'S LINKEDLIST CLASS LIBRARY.

The code in Figure 2 will create an empty list. And you will add elements using the “𝑎𝑑𝑑” method. To
create a populated LinkedList, you will need to pass another list as arguments when declaring it. For
example, let’s assume we have an Integer 𝐴𝑟𝑟𝑎𝑦𝐿𝑖𝑠𝑡 called 𝑠𝑐𝑜𝑟𝑒𝐴𝑟𝑟𝐿𝑖𝑠𝑡 that holds our scores
{6, 9, 7, 9, 10}. To create a LinkedList object from this we will declare it as in Figure 3.

For the purpose of this course, we will be using our own user-defined classes to explain the behaviour
of linked lists.
 Linked List with elements from scoreArrList will
be created.

LinkedList<Integer> score = new LinkedList<Integer>( scoreArrList)

Name of Linked List scoreArrList is an Integer ArrayList

holding our scores [6, 8, 7, 9, 10]

FIGURE 3. DECLARING AND INITIALISING AN SLL USING ARRAYLIST.

SLL REPRESENTATION

An element in a singly linked list can be visualised as a node, where a node holds the value of the
element and the address of the node that follows it in the list.

Data Pointer

23 next

FIGURE 4. SINGLY LINKED

LIST NODE

Our scores data in Example 1 can be visualised in a singly linked list as shown in Figure 5.

HEAD

6 8 7 9 10 NULL

FIGURE 5. LOGICALLY REPRESENTATION OF SCORE AS AN SLL .

The memory snapshot in Figure 6 displays how our 𝑠𝑐𝑜𝑟𝑒 linked list in Figure 5 is stored in a memory
that needs 2 bytes to store integer values. The value -1 means that is the end of the list, i.e., it does not
point to any other address location.

HEAD Memory allocation of 𝑠𝑐𝑜𝑟𝑒 singly linked list

1001 Addresses of memory blocks

1001

1006

1014
1000

1002

1003

1004

1005

1007

1008

1009

1010

1011

1012

1013

1015

1016

1017
6 8 7 9 10
Data

1005 1008 1013 1016 -1

Next

FIGURE 6. PHYSICAL REPRESENTATION OF SCORE SLL FROM FIGURE 5. LOGICALLY REPRESENTATION OF SCORE AS
AN SLL.

SUMMARY OF SLL PROPERTIES

• A singly linked list contains a link element called 𝒉𝒆𝒂𝒅 that points to its first node.
• Each node of an SLL carries a data field that holds the value of the element, and a link
(reference) field called 𝒏𝒆𝒙𝒕.
• Each node is linked with its successor node using the reference stored in the next field.
• The last node carries a link to null to indicate the end of the list.

DOUBLY LINKED LIST

Doubly linked lists are declared exactly the same way as singly linked lists. However, the implementation
of a doubly linked class slightly differs from that of an SLL class (Example 2). A DLL class has an additional
node variable for its tail, and its corresponding DLL Node will have an additional node attribute for the
previous pointer field.

Example 3: The following is an example of an implementation of an DLL in Java:

𝒑𝒖𝒃𝒍𝒊𝒄 𝒄𝒍𝒂𝒔𝒔 𝐷𝑜𝑢𝑏𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡 {

// 𝑓𝑖𝑟𝑠𝑡 𝑛𝑜𝑑𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡

𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝐷𝐿𝐿𝑁𝑜𝑑𝑒 ℎ𝑒𝑎𝑑;
// 𝑙𝑎𝑠𝑡 𝑛𝑜𝑑𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑡𝑎𝑖𝑙;

// 𝑐𝑜𝑛𝑠𝑡𝑟𝑡𝑢𝑐𝑡𝑜𝑟 𝑜𝑓 𝑡ℎ𝑒 𝐷𝑜𝑢𝑏𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡

𝒑𝒖𝒃𝒍𝒊𝒄 𝐷𝑜𝑢𝑏𝑙𝑦𝐿𝑖𝑛𝑘𝑒𝑑𝐿𝑖𝑠𝑡(){
𝒕𝒉𝒊𝒔. ℎ𝑒𝑎𝑑 = 𝒏𝒖𝒍𝒍;
𝒕𝒉𝒊𝒔. 𝑡𝑎𝑖𝑙 = 𝒏𝒖𝒍𝒍;
}
 // 𝑖𝑛𝑛𝑒𝑟 𝑐𝑙𝑎𝑠𝑠 𝑓𝑜𝑟 𝑎 𝑐𝑟𝑒𝑎𝑡𝑖𝑛𝑔 𝑎𝑛 𝐷𝐿𝐿 𝑛𝑜𝑑𝑒
𝒑𝒖𝒃𝒍𝒊𝒄 𝒄𝒍𝒂𝒔𝒔 𝐷𝐿𝐿𝑁𝑜𝑑𝑒 {
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝑂𝑏𝑗𝑒𝑐𝑡 𝑣𝑎𝑙𝑢𝑒;
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑛𝑒𝑥𝑡;
𝒑𝒓𝒐𝒕𝒆𝒄𝒕𝒆𝒅 𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑝𝑟𝑒𝑣;

𝒑𝒖𝒃𝒍𝒊𝒄 𝐷𝐿𝐿𝑁𝑜𝑑𝑒( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑎𝑡𝑎 ) {

𝑡ℎ𝑖𝑠. 𝑣𝑎𝑙𝑢𝑒 = 𝑑𝑎𝑡𝑎;
𝑡ℎ𝑖𝑠. 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙;
𝑡ℎ𝑖𝑠. 𝑝𝑟𝑒𝑣 = 𝑛𝑢𝑙𝑙;
}
}
}

Again, our code snippet in Example 3 only shows the constructor operator for the DLL. We will see some
snippet of code for the class methods later when we discuss operations of linked lists.

DLL REPRESENTATION

An element in a doubly linked list can be visualised as a node, where a node holds the value of the
element and the addresses of the previous and next nodes to it in the list.

Pointer Data Pointer

prev 71 next

FIGURE 7. A DOUBLY LINKED LIST NODE

Our scores data in Example 1 can be represented in a doubly linked list as shown in Figure 8.

HEAD

NULL
6 8 7 9 10
NULL

TAIL

FIGURE 8. LOGICAL REPRESENTATION OF SCORE AS A DLL.

The memory snapshot in Figure 9 shows how our 𝑠𝑐𝑜𝑟𝑒 doubly linked list (from Figure 8) may be
organised in a memory that needs 2 bytes to store integer values. The value -1 means that is the start
or end of the list, depending on whether we are going backwards or forward, and points to no other
address location.

HEAD Memory allocation of 𝑠𝑐𝑜𝑟𝑒 doubly linked list TAIL

1001 1016
Addresses of memory blocks
1001

1014
1000

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1012

1013

1015

1016

1017
6 8 7 9 10
Data

-1 1001 1015 1008 1013

Prev

1005 1008 1013 1016 -1

Next

FIGURE 9. PHYSICAL REPRESENTATION OF SCORE DLL FROM FIGURE 8.

SUMMARY OF DLL PROPERTIES

• A doubly linked list contains a link element called 𝒉𝒆𝒂𝒅 that points to its first node.
• A doubly linked list contains a link element called 𝒕𝒂𝒊𝒍 that points to its last node.
• Each node carries a data field and two link fields called 𝒏𝒆𝒙𝒕 and 𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔, 𝒑𝒓𝒆𝒗 for short.
• Each node is linked to its successor node with its 𝒏𝒆𝒙𝒕 pointer.
• Each node is linked to its predecessor node with its 𝒑𝒓𝒆𝒗 pointer.
• The 𝒏𝒆𝒙𝒕 pointer of the last node refers to 𝒏𝒖𝒍𝒍.
• The 𝒑𝒓𝒆𝒗 pointer of the first node refers to 𝒏𝒖𝒍𝒍.

CIRULAR LINKED LIST

Circular linked list can either be a singly or doubly linked list. To turn a singly linked list into a circular
linked list, the next link of the last node is made to point to the first node. Similar, a doubly linked list
can be made into circular linked list, when the next pointer of the last node points forward to the first
node and the previous pointer of the first node points back to the last node, making the list circular in
both directions. Thus, a circular linked has either a singly linked list or a doubly linked list as its base
type.

A circular linked list is declared the same way as a linear linked list. Circular linked list class will be almost
same as the linear linked list class that we saw in Example 2 and Example 3, with a few differences in
the implementation of class methods.
 CIRCULAR LINKED LIST REPRESENTATION

Our score singly linked list in Figure 5 can be visualised as a circular linked list as shown in Figure 10.

HEAD

6 8 7 9 10

FIGURE 10. SCORE SLL IN FIGURE 5 AS A CIRCULAR LINKED LIST.

Figure 11 shows how the circular SLL in Figure 10 is stored in memory.

HEAD Memory allocation of 𝑠𝑐𝑜𝑟𝑒 circular SLL

1001 Addresses of memory blocks

1001

1014
1000

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1012

1013

1015

1016

1017
6 8 7 9 10
Data

1005 1008 1013 1016 1001

Next

FIGURE 11. PHYSICAL REPRESENTATION OF SCORE FROM FIGURE 10.

And the doubly linked list in Figure 8 can be visualised as a circular linked list as shown in Figure 12.

HEAD

6 8 7 9 10

TAIL

FIGURE 12. LOGICAL REPRESENTATION OF SCORE DLL IN FIGURE 8 AS A CIRCULAR LINKED LIST.
The memory snapshot in Figure 13 is an example of how the circular (doubly) linked list in Figure 12 is
physically represented.

HEAD Memory allocation of 𝑠𝑐𝑜𝑟𝑒 circular DLL TAIL

1001 1016
Addresses of memory blocks
1001

1014
1000

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1012

1013

1015

1016

1017
6 8 7 9 10
Data

1016 1001 1015 1008 1013

Prev

1005 1008 1013 1016 1001

Next

FIGURE 13. PHYSICAL REPRESENTATION OF THE SCORE CIRCULAR LINKED LIST IN FIGURE 12.

SUMMARY OF CIRCULAR LINKED LIST PROPERTIES

• For both singly and doubly linked list variants, the circular linked list, has the 𝑛𝑒𝑥𝑡 pointer of
the last node referring to the first node.
• For the doubly linked list variant, the 𝑝𝑟𝑒𝑣 pointer of the of the first node is referring back to
the last node.

BASIC BEHAVIOUR OF A LINKED LIST

• Insertion: Adds an element to the linked list at a given position, this could be at the beginning
of the list, at the end of the list or after (or before) a specified node.
• Deletion: Removes from the linked list the element at a given position, similar to insertion, this
could be at the beginning, at the end or after (or before) a specified node in the list.
• Traversal: Goes through (visits) each node of the linked list at least once to perform some
specific operation on it, for example displaying the data part of the node. This could be forward
traversal, or backwards traversal in the case of a doubly linked list.
• Search: Searches the linked list for an element, each element is compared to the element being
searched. If found, the location of the element is returned otherwise null is returned.

INSERTION OPERATION

Insertion operation involves inserting a new element after a given node 𝐽 in the list. The node 𝐽 could
be the beginning of the linked list, the end of the linked list or somewhere along the middle of the list.
 INSERTING A NEW NODE INTO A SINGLY LINKED LIST

To insert a new element, we have to create new node for the element, find the node 𝐽 , create
temporary node to keep track of the next node after 𝐽, adjust the next pointer of 𝐽 refer to the new
node and link the next pointer of the new node to the temporary node.

Example 4: Let’s consider our score list from Example 1.

Assuming we missed recording an assessment in three instances:

1. We missed recording the score of the first assessment, our recorded score list is {8, 7, 9, 10},
so we will need to prepend 6 to the list (i.e., add to the front of the list).
2. We missed recording the score of the third assessment, our recorded score list is {6, 8, 9, 10},
so will need to add 7 somewhere around the middle of the list.
3. We missed recording the score of the fifth assessment, our recorded score list is {6, 8, 7, 9},
so will need to append 10 to the list (i.e., add to the end of the list).

INSERTION AT THE BEGINNING OF THE LIST (PREPENDING)

Insertion at the beginning of a list is easy, we do it in 3 steps:

1. Create the new node.

2. Make its next pointer refer to the node at 𝒉𝒆𝒂𝒅.
3. Modify 𝒉𝒆𝒂𝒅 to point to the recently created new node.

This is the best-case scenario. The process of prepending a new element is shown in Figure 14.

HEAD

Initially

8 7 9 10 NULL

New SLL Node

6 NULL

HEAD

Adjusting links

8 7 9 10 NULL

HEAD
After Insertion

6 8 7 9 10 NULL

FIGURE 14. INSERTATION AT THE BEGINNING OF AN SLL.

 AN ALGORITHM TO PREPEND AN ELEMENT TO A SINGLY LINKED LIST
Algorithm InsertAtFront (𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕)
Description: This algorithm inserts a new node 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕 into a singly linked list 𝑆𝐿𝐿 after the link
element 𝒉𝒆𝒂𝒅.
𝒉𝒆𝒂𝒅 points to the first node of the 𝑆𝐿𝐿.
𝒏𝒆𝒙𝒕 points to the node that comes after the node currently being processed.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Input: 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕, a new 𝑆𝐿𝐿 node.
Output: returns nothing.
Begin
Step 1: [Link 𝑛𝑒𝑥𝑡 of 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 to ℎ𝑒𝑎𝑑]
𝑒𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = ℎ𝑒𝑎𝑑
Step 2: [Make 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 become ℎ𝑒𝑎𝑑]
ℎ𝑒𝑎𝑑 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
End

Example 5: The following code snippet shows the Java Implementation of the class method for the
insertion (at the front of an SLL) operation.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑖𝑛𝑠𝑒𝑟𝑡𝐴𝑡𝐹𝑟𝑜𝑛𝑡( 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = ℎ𝑒𝑎𝑑;
ℎ𝑒𝑎𝑑 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

INSERTION AT THE END OF THE LIST (APPENDING)

In this case, a new node is created, the list is traversed to the last node and the next pointer of the last
node is linked to the newly created node, i.e., the new created node will become the predecessor of
the last node.
This is the worst-case scenario. The process of appending a new element is shown in Figure 15.

HEAD

Initially

6 8 7 9 NULL

New SLL Node

10 NULL

HEAD

Adjusting links

6 8 7 9 NULL

10 NULL

HEAD
After insertion

6 8 7 9 10 NULL

FIGURE 15. INSERTING AN ELEMENT AT THE END OF AN SLL.

AN ALGORITHM TO APPEND AN ELEMENT TO A SINGLY LINKED LIST

Algorithm InsertAtEnd (𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕)
Description: This algorithm traverses a singly linked list 𝑆𝐿𝐿 and inserts a new node 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕 at
the end of 𝑆𝐿𝐿.
Input: 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕, a new 𝑆𝐿𝐿 node.
Output: returns nothing.
𝒉𝒆𝒂𝒅 points to the first node of the 𝑆𝐿𝐿.
𝒏𝒆𝒙𝒕 points to the node that comes after the node currently being accessed; 𝒏𝒆𝒙𝒕 of the last
node is 𝒏𝒖𝒍𝒍, therefore if the 𝒏𝒆𝒙𝒕 of the current node is 𝒏𝒖𝒍𝒍, it means we have
reached the end of 𝑆𝐿𝐿.
If 𝒏𝒆𝒙𝒕 of 𝒉𝒆𝒂𝒅 is 𝒏𝒖𝒍𝒍 then 𝑆𝐿𝐿 is 𝒆𝒎𝒑𝒕𝒚.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Begin
Step 1: [Check to find out if 𝑆𝐿𝐿 is 𝑒𝑚𝑝𝑡𝑦 or not. If not 𝑒𝑚𝑝𝑡𝑦 goto Step 4]
if ℎ𝑒𝑎𝑑 → 𝑛𝑒𝑥𝑡 == 𝑛𝑢𝑙𝑙 then do Step 2 and Step 3 else goto Step 4.
Step 2: [Set 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 to become head]
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
Step 3: [Set 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 as the last node of 𝑆𝐿𝐿]
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙
Step 4: [Create a temporary node 𝑙𝑎𝑠𝑡, a local variable for this algorithm]
𝑙𝑎𝑠𝑡 = ℎ𝑒𝑎𝑑
 Step 5: [Traverse 𝑆𝐿𝐿 to get the last node in the list]
𝒘𝒉𝒊𝒍𝒆 (𝑙𝑎𝑠𝑡 → 𝑛𝑒𝑥𝑡 ! = 𝑛𝑢𝑙𝑙) 𝒓𝒆𝒑𝒆𝒂𝒕 𝑆𝑡𝑒𝑝 6
Step 6: [Move 𝑙𝑎𝑠𝑡 one step forward in the list]
𝑙𝑎𝑠𝑡 = 𝑙𝑎𝑠𝑡 → 𝑛𝑒𝑥𝑡
Step 7: [Link 𝑙𝑎𝑠𝑡 with 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡]
𝑙𝑎𝑠𝑡 → 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡
End

Example 6: The following code snippet shows the Java Implementation of the class method for the
insertion (at the end of an SLL) operation.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑖𝑛𝑠𝑒𝑟𝑡𝐴𝑡𝐸𝑛𝑑( 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

𝒊𝒇 ( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = ℎ𝑒𝑎𝑑;
ℎ𝑒𝑎𝑑 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑙𝑎𝑠𝑡𝑁𝑜𝑑𝑒 = ℎ𝑒𝑎𝑑;

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑢𝑛𝑡𝑖𝑙 𝑦𝑜𝑢 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑙𝑎𝑠𝑡 𝑛𝑜𝑑𝑒.
𝒘𝒉𝒊𝒍𝒆 ( 𝑙𝑎𝑠𝑡𝑁𝑜𝑑𝑒 ! = 𝑛𝑢𝑙𝑙 ) {
𝑙𝑎𝑠𝑡𝑁𝑜𝑑𝑒 = 𝑙𝑎𝑠𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}
𝑙𝑎𝑠𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

INSERTION AFTER A GIVEN NODE, J

Let 𝐽 be any node in the linked list. To add the newly created node after a give node 𝐽, starting from
head, move along the list to node 𝐽. Link the next pointer of the newly node to the node that comes
after 𝐽, and adjust the next pointer of 𝐽 to refer to the newly created node.
This is the average case scenario. The process of prepending a new element is shown in Figure 16.

HEAD

Initially

6 8 9 10 NULL

7 NULL

HEAD

Adjusting links

6 8 9 10 NULL

HEAD
After
insertion

6 8 7 9 10 NULL

FIGURE 16. INSERTING AN ELEMENT INTO AN SLL AFTER A GIVEN NODE J.

AN ALGORITHM TO ADD AN ELEMENT INTO A SINGLY LINKED LIST AFTER A GIVEN NODE J
Algorithm InsertAfter (𝑱, 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕)
Input: 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕, a new 𝑆𝐿𝐿 node, 𝑱, a node somewhere in the middle of 𝑆𝐿𝐿.
Output: returns nothing.
Description: This algorithm traverses a singly linked list 𝑆𝐿𝐿 and inserts a new node 𝒏𝒆𝒘𝑬𝒍𝒆𝒎𝒆𝒏𝒕
after a given node 𝑱 in 𝑆𝐿𝐿.
𝒉𝒆𝒂𝒅 points to the first node of the 𝑆𝐿𝐿.
𝒏𝒆𝒙𝒕 points to the node that comes after the node currently being processed; 𝒏𝒆𝒙𝒕 of the last
node is 𝒏𝒖𝒍𝒍, therefore if the 𝒏𝒆𝒙𝒕 of the current node is 𝒏𝒖𝒍𝒍, it means we have
reached the end of 𝑆𝐿𝐿.
If 𝒏𝒆𝒙𝒕 of 𝒉𝒆𝒂𝒅 is 𝒏𝒖𝒍𝒍 then 𝑆𝐿𝐿 is 𝒆𝒎𝒑𝒕𝒚.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Begin
Step 1: [Check to find out if 𝑆𝐿𝐿 is 𝑒𝑚𝑝𝑡𝑦 or not. If not 𝑒𝑚𝑝𝑡𝑦 goto Step 4]
if ℎ𝑒𝑎𝑑 → 𝑛𝑒𝑥𝑡 == 𝑛𝑢𝑙𝑙 then do Step 2 and Step 3 else goto Step 4.
Step 2: [Set 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 to become head]
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
Step 3: [Set 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 as the last node of 𝑆𝐿𝐿]
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙
Step 4: [Create a temporary node 𝑐𝑢𝑟𝑟𝑒𝑛𝑡, a local variable for this algorithm]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
Step 5: [Traverse 𝑆𝐿𝐿 to get to the given node 𝐽 in the list]
 𝒘𝒉𝒊𝒍𝒆 (𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 ! = 𝐽) 𝒓𝒆𝒑𝒆𝒂𝒕 𝑆𝑡𝑒𝑝 6
Step 6: [Move 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 one step forward in the list]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
Step 7: [Link 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 with 𝑡ℎ𝑒 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 𝑜𝑓 𝐽]
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = 𝐽 → 𝑛𝑒𝑥𝑡
Step 7: [Link 𝐽 with 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡]
𝐽 → 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡
End

Example 7: The following code snippet shows the Java Implementation of the class method for the
insertion (after a given node, 𝐽) operation.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑖𝑛𝑠𝑒𝑟𝑡𝐴𝑓𝑡𝑒𝑟( 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

//𝑖𝑛𝑠𝑒𝑟𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑓𝑡𝑒𝑟 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒

𝒊𝒇 ( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = ℎ𝑒𝑎𝑑;
ℎ𝑒𝑎𝑑 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒;
}

𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = ℎ𝑒𝑎𝑑;

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑢𝑛𝑡𝑖𝑙 𝑦𝑜𝑢 𝑟𝑒𝑎𝑐ℎ 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒.
𝒘𝒉𝒊𝒍𝒆 ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒 ) {
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}

/∗
∗ 𝑖𝑛𝑠𝑒𝑟𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒 𝑎𝑛𝑑 𝑖𝑡𝑠 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟,
∗ 𝑡ℎ𝑎𝑡 𝑖𝑠 𝑡ℎ𝑒 𝑛𝑜𝑑𝑒 𝑡ℎ𝑎𝑡 𝑐𝑜𝑚𝑒𝑠 𝑎𝑓𝑡𝑒𝑟 𝑖𝑡.
/
//𝑙𝑖𝑛𝑘 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑡𝑜 𝑡ℎ𝑒 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 𝑜𝑓 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒.
𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
//𝑙𝑖𝑛𝑘 𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒 𝑡𝑜 𝑒𝑙𝑒𝑚𝑒𝑛𝑡.
𝑝𝑟𝑒𝑣𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

INSERTING A NEW NODE INTO A DOUBLY LINKED LIST

Adding an element into a doubly linked list is very similar to insertion into a singly linked list. The main
differences are, in a doubly linked list:

1. Insertion requires two links to be adjusted to connect to the new node: the next pointer of the
node before, as well as the previous pointer of the node after. Also, the new node will attach
itself to these two nodes via its own links.
2. Insertion at the end of a doubly linked list does not require traversing the list, as a doubly linked
list has a 𝑡𝑎𝑖𝑙 pointer that keeps track of the last element.
3. Inserting after or before a given node 𝐽 in a doubly linked list also requires traversing to get to
the node. The list, however, can be traversed from either 𝒉𝒆𝒂𝒅 or the 𝒕𝒂𝒊𝒍 of the list.
 Figure 17 illustrates the process of prepending an element to a doubly linked list.

HEAD

Initially

8 7 9 10 NULL
NULL

New DLL node

6 NULL
NULL TAIL

HEAD
Adjusting links

8 7 9 10 NULL
NULL

6
NULL TAIL

HEAD
After insertion

NULL
6 8 7 9 10
NULL

TAIL

FIGURE 17. INSERTING AN ELEMENT IN FRONT OF A DOUBLY LINKED LIST.

Figure 18 shows the process of appending an element to a doubly linked list.

 Initially HEAD TAIL

6 8 7 9 NULL
NULL

New DLL node

NULL
10
NULL

Adjusting links HEAD TAIL

6 8 7 9 NULL
NULL

NULL
10

HEAD
After insertion

NULL
6 8 7 9 10
NULL

TAIL

FIGURE 18. INSERTING AN ELEMENT AT THE END OF A DLL.

 Figure shows the process of adding an element into a doubly linked list, after a given node somewhere
along the middle of the list.

Initially HEAD

NULL
6 8 9 10
NULL

New DLL node

7 NULL
NULL TAIL

Adjusting links HEAD

6 8 9 10 NULL
NULL

7
TAIL

HEAD
After Insertion

NULL
6 8 7 9 10
NULL

TAIL

FIGURE 19. INSERTING AN ELEMENT INTO A DLL AT AFTER A GIVEN NODE

INSERTING A NEW NODE INTO A CIRCULAR LINKED LIST

Insertion into a circular linked list does not differ with its base type. That means, if it is a circular SLL,
the insertion operations are the same as done for a regular SLL. Similarly, if it is a circular DLL the
insertion operations are done same way as in regular DLL.

DELETION OPERATION

Deleting a node from a list requires: first, us find the node storing the data that we want to delete and
then removing it. We can delete either from the beginning, end or from a particular position of the list.

Example 8: Continuing with our sample data, {6, 8, 7, 9, 10}. We are going to delete the first element,
the last element and element 9.

DELETING AN ELEMENT FROM A SINGLY LINKED LIST

Deleting a node from a singly linked list involves finding its predecessor and adjusting the 𝑛𝑒𝑥𝑡 link of
the predecessor to point to the node that follows the node to be deleted.
 DELETING AT THE BEGINNING OF A LIST
If the node to be deleted is the first node, we simply set ℎ𝑒𝑎𝑑 point to the successor of the node to be
deleted. Figure 20 shows the process of removing an element from the front of an SLL.

HEAD Initially

6 8 7 9 10 NULL

HEAD Adjusting links

8 7 9 10 NULL

After deletion HEAD

Deleted SLL node

8 7 9 10 NULL

FIGURE 20. DELETING AN ELEMENT FROM THE BEGINNING OF AN SLL.

DELETING AT THE END OF A LIST

In this case, we find the second to last node and set its 𝑛𝑒𝑥𝑡 pointer to 𝑛𝑢𝑙𝑙. Figure 21 shows the
process of removing an element from the end of an SLL.

HEAD Initially

6 8 7 9 10 NULL

HEAD Adjusting links

6 8 7 9 NULL

HEAD After deletion

Deleted SLL node

6 8 7 9 NULL

FIGURE 21. DELETING AN ELEMENT FROM THE END OF AN SLL.

 DELETING AN ELEMENT AT THE J TH NODE OF A LIST
If the node to be deleted is somewhere in the middle, we find the node before it, and make the 𝑛𝑒𝑥𝑡
pointer of that node point to the node that follows the node to be deleted. Figure 22 shows the process
of removing an element from somewhere along the middle of an SLL.

HEAD Initially

6 8 7 9 10 NULL

HEAD Adjusting links

6 8 7 9 10 NULL

After deletion HEAD Deleted SLL node

6 8 7 10 NULL

FIGURE 22. DELETING AN ELEMENT SOMEWHERE ALONG THE MIDDLE OF AN SLL .

AN ALGORITHM TO REMOVE AN ELEMENT FROM A SINGLY LINKED LIST

Algorithm Delete (𝒅𝒂𝒕𝒂)
Input: 𝒅𝒂𝒕𝒂, data value of the node element.
Output: 𝑒𝑙𝑒𝑚𝑒𝑛𝑡, the deleted node.
Description: This algorithm deletes an element with the value 𝒅𝒂𝒕𝒂 before a node.
𝒉𝒆𝒂𝒅 is a pointer that points to the head of the linked list.
𝒅𝒂𝒕𝒂 the data value of the node to be deleted.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Begin
Step 1: [Initialise a local node variable 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
Call class method search to retrieve the node using its data value]
𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒()
𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑠𝑒𝑎𝑟𝑐ℎ(𝑑𝑎𝑡𝑎)
Step 2: [Initialise a local node variable 𝑐𝑢𝑟𝑟𝑒𝑛𝑡]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
Step 3: 𝒊𝒇 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 == 𝑡𝑒𝑚𝑝
[If 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 is found at the beginning of the list do Step 4]
Step 4: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
Step 5: else
[else 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 is not found at the beginning of the list do Steps 6-8]
Step 6: while 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 repeat Step 7
[Move forward along the list]
Step 7: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
Step 8: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
 Step 9: return 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
End

Example 9: The following code snippet shows Java implementation of deleting an SLL node.

𝒑𝒖𝒃𝒍𝒊𝒄 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑑𝑒𝑙𝑒𝑡𝑒 (𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑎𝑡𝑎) {

//𝑠𝑒𝑎𝑟𝑐ℎ 𝑓𝑜𝑟 𝑡ℎ𝑒 𝑛𝑜𝑑𝑒 𝑤𝑖𝑡ℎ 𝑑𝑎𝑡𝑎 = 𝑑𝑎𝑡𝑎

𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑠𝑒𝑎𝑟𝑐ℎ( 𝑑𝑎𝑡𝑎 );
//𝑐𝑟𝑒𝑎𝑡𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 𝑎𝑛𝑑 𝑠𝑒𝑡 𝑖𝑡 𝑡𝑜 ℎ𝑒𝑎𝑑
𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝒕𝒉𝒊𝒔. ℎ𝑒𝑎𝑑;

//𝑡ℎ𝑒 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑑𝑒𝑙𝑒𝑡𝑒 𝑖𝑠 𝑓𝑜𝑢𝑛𝑑 𝑎𝑡 𝑡ℎ𝑒 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡

𝒊𝒇( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 == 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {
𝒕𝒉𝒊𝒔. ℎ𝑒𝑎𝑑 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡;
}
𝒆𝒍𝒔𝒆 {
//𝑣𝑖𝑠𝑖𝑡𝑠 𝑡ℎ𝑒 𝑛𝑜𝑑𝑒𝑠 𝑢𝑛𝑡𝑖𝑙 𝑡ℎ𝑒 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑏𝑒 𝑑𝑒𝑙𝑒𝑡𝑒𝑑 𝑖𝑠 𝑓𝑜𝑢𝑛𝑑
//𝑜𝑟 𝑡ℎ𝑒 𝑒𝑛𝑑 𝑜𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑟𝑒𝑎𝑐ℎ𝑒𝑑
𝒘𝒉𝒊𝒍𝒆(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡 ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡;
}

𝒓𝒆𝒕𝒖𝒓𝒏 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

DELETING AN ELEMENT FROM A DOUBLY LINKED LIST

Removing an element from a doubly linked list is similar to removing an element from a singly linked
list. The main difference is, in a doubly linked list, two links will be adjusted to connect to the nodes
before and after the deleted node. Removal at the end of a doubly linked list does not require traversing
the list because of the 𝑡𝑎𝑖𝑙 pointer that points to the last element in the list. To remove from
somewhere in the middle, the list can be traversed either from the front or the back to get to either its
predecessor or successor nodes.
Figure 23 illustrates the process of removing the element at the beginning of a DLL.

HEAD
Initially

6 8 7 9 10 NULL
NULL

TAIL

HEAD
Adjusting links

NULL
8 7 9 10
NULL

TAIL

HEAD
After deletion

Deleted DLL node

NULL
8 7 9 10
NULL

TAIL

FIGURE 23. DELETING AN ELEMENT FROM A THE FROM OF A DLL.

 Figure 24 shows the process of removing the element at the end of a DLL.

HEAD
Initially

6 8 7 9 10 NULL
NULL

TAIL

HEAD
Adjusting links

8 7 9 NULL
NULL

TAIL

HEAD
After deletion

Deleted DLL node

8 7 9 NULL
NULL

TAIL

FIGURE 24. DELETING AN ELEMENT FROM THE END OF A DLL.

Figure 25 illustrates the process of removing an element from somewhere along the middle of a DLL.

HEAD
Initially

NULL
6 8 7 9 10
NULL

TAIL

HEAD
Adjusting links

6 8 7 10 NULL
NULL

TAIL

HEAD Deleted DLL node

After deletion

NULL
6 8 7 10
NULL

TAIL

FIGURE 25. DELETING AN ELEMENT SOMEWHERE ALONG THE MIDDLE OF A DLL.

DELETING AN ELEMENT FROM A CIRCULAR LINKED LIST

Deletion from a circular linked list does not differ with its base type. That means, if it is a circular SLL,
deleting a node is done the same way as it is done in a regular SLL. Similarly, if it is a circular DLL the
deletion operation is done the same way as in regular DLL.

TRAVERSAL OPERATION

Traversing the elements of a linked list is very simple. We keep moving along the list, starting with the
first node and visiting all the nodes until the last node. A temporary node is used to keep track of the
node being processed. The temporary node is moved along the list using the next pointer. When the
temporary node becomes 𝑛𝑢𝑙𝑙, we know that we have reached the end of the list. Like with arrays, the
traversal operation can be used in counting the elements in a linked list, displaying values stored in a
linked list or summing up all the values of the elements in the list. Also, we will use the traversal
operation if we want to do any other similar calculations or processes on each element of the linked
list. The traversal described above is forward traversal, and it can be used for both singly and doubly
linked list. Since doubly linked list is bi-directional, its elements can be traversed in reverse. This means
that the traversal will start from the last node of the list and moves backwards until the first node is
reached. This is called backwards traversal. Forward traversal, for regular linked lists stop when the
temporary node becomes 𝑛𝑢𝑙𝑙 . Similarly, backwards traversal for a regular linked list stops when
temporary node becomes 𝑛𝑢𝑙𝑙. For circular linked lists, the traversing ends when the temporary node
becomes the starting node, i.e., the node where the traversal started from.
 FORWARD TRAVERSAL

To forward traverse a regular linked list:

1. A temporary node is needed to store the address of the node currently being processed.
2. After processing the element at the current position, the temporary node is moved forward to
the next node and the same process is applied to the corresponding element.
3. This is repeated until the temporary node is assigned to 𝑛𝑢𝑙𝑙. This means we have reached the
end of the linked list.

The following algorithm traverses a linked list, with the link to its first element stored in its 𝒉𝒆𝒂𝒅.

Algorithm TraverseForward ()
Input: nil, it takes nothing.
Output: nil, it returns nothing.
Description: This algorithm traverses a linked list for an element.
𝒉𝒆𝒂𝒅 points to the first node of the list.
𝒏𝒆𝒙𝒕 points to the node that follows the node currently being processed; the successor of the
last node is 𝒏𝒖𝒍𝒍, therefore if next of the current is 𝒏𝒖𝒍𝒍, it means we have reached
the end of the list.
𝒗𝒂𝒍𝒖𝒆 is the data contained in current node.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Begin
Step 1: [Create a temporary node 𝑐𝑢𝑟𝑟𝑒𝑛𝑡, a local variable for this algorithm]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
Step 2: while (𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ! = 𝑛𝑢𝑙𝑙) repeat Steps 3 and 4
Step 3: process 𝑣𝑎𝑙𝑢𝑒 of the current node
[𝑝𝑟𝑜𝑐𝑒𝑠𝑠 is a generic task that can be used to
count the elements,
perform some calculation,
sum all the elements,
display all elements or
assign new values to each element]
Step 4: [Move 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 to the next node]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
End

Example 10: Let’s write a Java implementation of the forward traversal algorithm to display the
elements of a singly linked list.

You can traverse through a linked list using a 𝒘𝒉𝒊𝒍𝒆 𝒍𝒐𝒐𝒑. A temporary node variable, 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒,
is initialised to point to ℎ𝑒𝑎𝑑. The looping condition is checked at the start each iteration, if it holds
true, the instructions within the loop are executed, otherwise control is passed onwards to the
instruction after the loop. During each iteration of the loop, the temporary node is moved along the list
to the next node.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑡𝑠𝐹𝑜𝑟𝑤𝑎𝑟𝑑(){

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑎𝑛𝑑 𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒.
𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
// 𝑠𝑒𝑡 𝑡ℎ𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑓𝑖𝑟𝑠𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = ℎ𝑒𝑎𝑑;
 𝒘𝒉𝒊𝒍𝒆 ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝑛𝑢𝑙𝑙 ) {
//𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
//𝑢𝑛𝑡𝑖𝑙 𝑤𝑒 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑒𝑛𝑑 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
𝑆𝑦𝑠𝑡𝑒𝑚. 𝑜𝑢𝑡. 𝑝𝑟𝑖𝑛𝑡(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}
}
}

Running the algorithm on our score singly linked list, {6, 8, 7, 9, 10}, will produce the following output:

𝑶𝒖𝒕𝒑𝒖𝒕
𝐿𝑖𝑛𝑘𝑒𝑑 𝑙𝑖𝑠𝑡: 6 8 7 9 10

BACKWARDS TRAVERSAL

To perform a backwards traversal, the starting node is the 𝒕𝒂𝒊𝒍 node and the reference link used is the
previous pointer 𝒑𝒓𝒆𝒗. The traversal ends when the first node is reached, that is when the previous
pointer of the current node refers to 𝒏𝒖𝒍𝒍.

Example 11: Let’s write a Java implementation of the backwards traversal algorithm to display the
elements of a doubly linked list.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑡𝑠𝐵𝑎𝑐𝑘𝑤𝑎𝑟𝑑𝑠(){

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑎𝑛𝑑 𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒.
𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
// 𝑠𝑒𝑡 𝑡ℎ𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑙𝑎𝑠𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑡𝑎𝑖𝑙;

𝒘𝒉𝒊𝒍𝒆 ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝑛𝑢𝑙𝑙 ) {

//𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
//𝑢𝑛𝑡𝑖𝑙 𝑤𝑒 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑠𝑡𝑎𝑟𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
𝑆𝑦𝑠𝑡𝑒𝑚. 𝑜𝑢𝑡. 𝑝𝑟𝑖𝑛𝑡(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑝𝑟𝑒𝑣;
}
}
}

Running the algorithm on our score doubly linked list, {6, 8, 7, 9, 10}, will produce the following output:

𝑶𝒖𝒕𝒑𝒖𝒕
𝐿𝑖𝑛𝑘𝑒𝑑 𝑙𝑖𝑠𝑡: 10 9 7 8 6

TRAVERSAL OF A CIRCULAR LINKED LIST

A circular linked list is traversed akin to its base type using reference links either moving forward or
backwards. However, any node, not only the first or last, can be used to traverse a circular linked list.
In this case, the loop breaks when the current node points to the starting node. This means that a
starting node needs to be passed as an input to the algorithm (or procedure).

Example 12: Let’s write a Java implementation of the forward traversal algorithm to display the
elements in a circular (singly) linked list starting from a given node, 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒.
 𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑠𝐹𝑜𝑟𝑤𝑎𝑟𝑑𝐶𝑖𝑟𝑐𝑢𝑙𝑎𝑟(𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒){

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑎𝑛𝑑 𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒.
𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
// 𝑠𝑒𝑡 𝑡ℎ𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡(𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");
𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;

𝒘𝒉𝒊𝒍𝒆 ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒 ) {

//𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
//𝑢𝑛𝑡𝑖𝑙 𝑤𝑒 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑒𝑛𝑑 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡

𝑆𝑦𝑠𝑡𝑒𝑚. 𝑜𝑢𝑡. 𝑝𝑟𝑖𝑛𝑡(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");

𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛();
}
}

Running the algorithm on our score circular linked list, {6, 8, 7, 9, 10}, starting from the third node will
produce the following output:

𝑶𝒖𝒕𝒑𝒖𝒕
𝐿𝑖𝑛𝑘𝑒𝑑 𝑙𝑖𝑠𝑡: 7 9 10 6 8

Example 13: Now let’s implement in Java, the backwards traversal algorithm to display the elements in
a circular linked list starting from a given node, 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑠𝐵𝑎𝑐𝑘𝑤𝑎𝑟𝑑𝑠𝐶𝑖𝑟𝑐𝑢𝑙𝑎𝑟(𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒){

//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑙𝑖𝑠𝑡 𝑎𝑛𝑑 𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒.
𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
// 𝑠𝑒𝑡 𝑡ℎ𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑛𝑜𝑑𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡(𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");
𝐷𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒. 𝑝𝑟𝑒𝑣;

𝒘𝒉𝒊𝒍𝒆 ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝑠𝑡𝑎𝑟𝑡𝑁𝑜𝑑𝑒 ) {

//𝑑𝑖𝑠𝑝𝑙𝑎𝑦 𝑡ℎ𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑒𝑎𝑐ℎ 𝑛𝑜𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
//𝑢𝑛𝑡𝑖𝑙 𝑤𝑒 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑠𝑡𝑎𝑟𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡

𝑆𝑦𝑠𝑡𝑒𝑚. 𝑜𝑢𝑡. 𝑝𝑟𝑖𝑛𝑡(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 + " ");

𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑝𝑟𝑒𝑣;
}
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛();
}
}

Running the algorithm on our score circular linked list, {6, 8, 7, 9, 10}, starting from the third node will
produce the following output:

𝑶𝒖𝒕𝒑𝒖𝒕
𝐿𝑖𝑛𝑘𝑒𝑑 𝑙𝑖𝑠𝑡: 7 8 6 10 9
 SEARCH OPERATION

To find an element in the list, we need to traverse the list starting from head as we compare the search
element with the value of the node at the current position. If we get the node with the same value as
the search element, we will return it. Otherwise, we continue moving along the list until we reach the
end of it. If we get to the end of the list without finding the search element, what we return will indicate
that the element does not exist in the list. Similar to the traverse operation, a doubly linked list can be
searched backwards, and circular linked list follows the same convention as its base type and the search
can start from any node.

The following is an algorithm to search a singly linked list or forward search a doubly linked list.

Algorithm Search (𝒆𝒍𝒆𝒎𝒆𝒏𝒕)

Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the element to be searched for
Output: node having the value of 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 or 𝑛𝑢𝑙𝑙
Description: This algorithm searches for an element by its data value in the linked list SLL and returns it
if found otherwise it returns null.
The start of the list is known from the header pointer 𝒉𝒆𝒂𝒅.
Statements in square brackets “[]” are comments, they do not have any operational cost.
“→” indicates an access handle to a component/attribute of the specified object.
Begin
Step 1: [Check is list is empty]
if 𝑙𝑖𝑠𝑡. 𝑒𝑚𝑝𝑡𝑦()
Step 2: return 𝑛𝑢𝑙𝑙
Step 3: [Initialise node local variable 𝑐𝑢𝑟𝑟𝑒𝑛𝑡]
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = ℎ𝑒𝑎𝑑
[Move forward along the list, while not end of the list]
Step 4: while 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ! = 𝑛𝑢𝑙𝑙 && 𝑐𝑢𝑟𝑟𝑒𝑛 → 𝑑𝑎𝑡𝑎 ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 repeat Step 5
Step 5: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡
Step 6: return 𝑐𝑢𝑟𝑟𝑒𝑛𝑡
End

Example 14: Following it’s the Java implementation of the (forward) search algorithm.

𝒑𝒖𝒃𝒍𝒊𝒄 𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑠𝑒𝑎𝑟𝑐ℎ( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
//𝑖𝑓 𝑙𝑖𝑠𝑡 𝑖𝑠 𝑒𝑚𝑝𝑡𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑛𝑢𝑙𝑙
𝒓𝒆𝒕𝒖𝒓𝒏 𝒏𝒖𝒍𝒍;
}

𝑆𝐿𝐿𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝒕𝒉𝒊𝒔. ℎ𝑒𝑎𝑑;

𝒘𝒉𝒊𝒍𝒆( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 ! = 𝒏𝒖𝒍𝒍 && 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑑𝑎𝑡𝑎 ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){
//𝑢𝑛𝑡𝑖𝑙 𝑤𝑒 𝑟𝑒𝑎𝑐ℎ 𝑡ℎ𝑒 𝑒𝑛𝑑 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑖𝑠𝑡
// 𝑜𝑟 𝑤𝑒 𝑓𝑖𝑛𝑑 𝑎 𝑁𝑜𝑑𝑒 𝑤𝑖𝑡ℎ 𝑑𝑎𝑡𝑎 = 𝑑𝑎𝑡𝑎, 𝑤𝑒 𝑘𝑒𝑒𝑝 𝑚𝑜𝑣𝑖𝑛𝑔
𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}

𝒓𝒆𝒕𝒖𝒓𝒏 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒;
}

Continuing with our sample data, {6, 8, 7, 9, 10}. We are going to search the element for an element by
its value, 9.
 𝑶𝒖𝒕𝒑𝒖𝒕
𝐸𝑙𝑒𝑚𝑒𝑛𝑡: 9

We are now going to search the list for an element with the value 55.

𝑶𝒖𝒕𝒑𝒖𝒕
𝐸𝑙𝑒𝑚𝑒𝑛𝑡: 𝑛𝑢𝑙𝑙

TRADE-OFFS

No data structure is well suited to all situations. In the previous unit, we have seen that arrays have
quick lookup time, constant time. Whereas insertion or deletion into an array is linear time in the worst-
case. Similarly, a linked list data structure might work well in a certain case, but cause problem in
another. In the sections that follow we will highlight some trade-offs of linked list data structures.

SUMMARY OF COMPLEXITY OF LINKED LIST OPERATIONS

Time and space complexity of common linked list operations are summarised in Table 1 that follows.
Note doubly linked list have both ℎ𝑒𝑎𝑑 and 𝑡𝑎𝑖𝑙 pointers. Singly linked list usually only has a ℎ𝑒𝑎𝑑
pointer.
TABLE 1. COMPLEXITY OF COMMON LINKED LIST OPERATIONS

Time Complexity
only head pointer is known head and tail pointers are known
Operation at Beginning at End at Beginning at End
Access 𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏)
Search 𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏)
Insertion 𝑶(𝟏) 𝑶(𝒏) 𝑶(𝟏) 𝑶(𝟏)
Deletion 𝑶(𝟏) 𝑶(𝒏) 𝑶(𝟏) 𝑶(𝟏)
Space Complexity
𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏) 𝑶(𝒏)
Table 2 that follows shows the complexity of some basic operations in linked list compared to in arrays.
TABLE 2. COMPLEXITY OF LINKED LIST OPERATIONS VS. ARRAY OPERATIONS

Mutate (insert or delete) at: Space

Access Beginning End Middle Complexity
Linked list 𝑶(𝒏) 𝑶(𝟏) tail known 𝑶(𝟏) Access time + 𝑶(𝒏)
tail unknown 𝑶(𝒏) 𝑶(𝟏)
Array 𝑶(𝟏) N/A N/A N/A 𝑶(𝒏)
Dynamic array 𝑶(𝟏) 𝑶(𝒏) 𝑶(𝟏) 𝑶(𝒏) 𝑶(𝒏)

LINKED LISTS VS STATIC ARRAYS

Table 3 contrasts linked lists against arrays.

TABLE 3. LINKED LIST VS (STATIC) ARRAY

Array Linked List

Size Static. Size is fixed, cannot change Dynamic. Size is adjustable at

at runtime. runtime.
Memory At compile time. At run time.
allocation
Memory Uses less memory. Uses more memory than arrays for
efficiency the same number of elements
because of the overhead of storing
pointers. This makes linked list
impractical for small data items.
Access Random access. Any element can Sequential access. To get to an
be accessed directly via its index. element, all element before must be
traversed before it can be reached.
This makes linked list poorly suited
for applications where quick look up
by an element’s index is essential,
such as in heapsort.
Operation Faster element lookup and Faster insertions and deletions
efficiency modification

LINKED LISTS VS DYNAMIC ARRAYS

Both linked lists and dynamic arrays are unbounded data structures. However, there are certain
situations where one is better suited for usage than the other. Table 4 summarises the pros and cons
of linked lists against dynamic arrays.
TABLE 4. LINKED LIST VS. DYNAMIC ARRAY

Linked List Dynamic Array

Size Dynamic. Dynamic.
Memory At run time. Arbitrarily many At run time. Eventually, its
allocation elements may be inserted into a underlying array data structure will
linked list, limited only by the total
fill up and will have to reallocate—
memory available an expensive operation, one that
may not even be possible if memory
is fragmented. An array from which
many elements are removed may
also have to be resized in order to
avoid wasting too much space.
Memory Uses more memory than arrays for Uses less memory.
efficiency the same number of elements
because of the overhead of storing
pointers. This makes linked list
impractical for small data items.
 Access Sequential access. To get to an Random access. Any element can be
element, all element before must accessed directly via its index. Thus,
be traversed before it can be it has constant time access.
reached. This makes linked list
poorly suited for applications
where quick look up by an
element’s index is essential, such
as in heapsort.
Operation When the node before the Insertion in a dynamic array at
efficiency insertion or deletion point is random locations will require
known the operation is done in moving half of the elements on
constant time. Otherwise, the average, and all the elements in the
operation is done in linear time. worst case.

SINGLY LINKED LIST VS DOUBLY LINKED LIST

Doubly linked lists, because of the extra reference link they carry, require more space per node than
singly linked lists. Also, there elementary operations are more expensive. However, they are easier to
manipulate because they allow sequential access from both ends of the lists. In a doubly linked list, we
can insert or delete a node in a constant number of operations given only that node's address. To do
the same in a singly linked list, we must have the address of the pointer to that node, which is either
the handle for the whole list (in case of the first node) or the link field in the 𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠 node.

CIRCULAR LINKED LIST VS LINEARLY LINKED LIST

A circular linked list is an instinctive choice to represent arrays or lists that are logically circular, e.g.,
corners of a polygon, a pool of buffers using the FIFO (first in, first out) order to queue and release jobs,
or a set of processes to be time-shared in a round-robin order. In these applications, a pointer to any
node can be used as handle to the entire list.

A pointer to the last node in a circular linked list provides quick access to the first node by following
one link. Hence, a circular structure allows a single pointer, instead of two, to handle data organisation,
storage and access in applications requiring access to both ends of a list (e.g., the implementation of a
queue).

A circular linked list can be split into two lists in constant time. This requires adjusting the links of the
two nodes of the original list that are given as the last nodes for two lists to be created. Similarly, two
separate circular lists can be joined to form a single circular list by adjusting the links of the last nodes
of both lists.

SUMMARY

• A linked list is an implementation of the List ADT.

• A linked list is a linear collection of data elements. Elements in the list are arranged as sequence
within the list, by having each element in the list point to the next one. Thus, their physical
placement in memory does not determine their order in the list.
• A linked list is a data structure represented by nodes joined together via links (references) to
form a sequence.
• A linked list can be singly or doubly linked.
• Singly linked nodes have two fields: a data field to store the value of the element, and a link
field to store the address of the next element in the list.
• The last node of a singly linked list points to null. An SLL also has a reference variable, ℎ𝑒𝑎𝑑,
that points to first node of the list. This reference is 𝑛𝑢𝑙𝑙 when the list is empty.
• Doubly linked nodes are singly linked nodes with an extra connection, they have a third
reference field that stores the address of the preceding node in the list. This link for the first
node of list points 𝑛𝑢𝑙𝑙.
• A doubly linked list, in addition to ℎ𝑒𝑎𝑑, has a second reference variable, 𝑡𝑎𝑖𝑙, that points to
the last node of the list. This reference, also, is 𝑛𝑢𝑙𝑙 when the list is empty.
• A linked list can also be circular, instead of linear. In a circular linked list, nodes are a connected
in a continuous chain, without using 𝑛𝑢𝑙𝑙.
• A singular linked can be traversed in one direction, beginning at ℎ𝑒𝑎𝑑 moving forward.
Whereas a doubly linked list can also be traversed from the 𝑡𝑎𝑖𝑙 moving backwards.
• A circular linked list can either be singly linked or doubly linked. Both types of circularly linked
lists allow us to traverse the full list starting from any given node.
• For lists with a 𝑓𝑟𝑜𝑛𝑡 and a 𝑏𝑎𝑐𝑘 (such as a queue), we store a pointer to the last node in the
list. The 𝑛𝑒𝑥𝑡 node after the last node is the first node. Elements can be added to the 𝑏𝑎𝑐𝑘 of
the list and removed from the 𝑓𝑟𝑜𝑛𝑡 in constant time.

NOTES AND WHAT COMES LATER

• Use the algorithms in this note to practice time efficiency analysis.

• In the next unit, we will look at Stack ADT including how to implement it using linked lists.
• In later weeks, we will also take a look at how we can use linked lists to implement more data
structures.

EXERCISES

1. Using the Interface Class Library in java, create a List ADT in Java using the operations outlined
in Specifying a List ADT. Generalise the ADT by using "Object" for the element type.
2. Assume we implemented the List ADT, defined in Specifying a List ADT, as a data structure
called 𝐿𝑖𝑠𝑡, and we declared 𝑙𝑖𝑠𝑡 as an object of the 𝐿𝑖𝑠𝑡 type. One of the possible ways to
traverse it is as follows:

𝒇𝒐𝒓 (𝑙𝑖𝑠𝑡. 𝑚𝑜𝑣𝑒𝑇𝑜𝑆𝑡𝑎𝑟𝑡(); ! 𝑙𝑖𝑠𝑡. 𝑖𝑠𝐴𝑡𝐸𝑛𝑑(); 𝑙𝑖𝑠𝑡. 𝑛𝑒𝑥𝑡()) {

𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑙𝑖𝑠𝑡. 𝑔𝑒𝑡𝑉𝑎𝑙𝑢𝑒();
𝑑𝑜𝑆𝑜𝑚𝑒𝑡ℎ𝑖𝑛𝑔(𝑒𝑙𝑒𝑚𝑒𝑛𝑡);
}

In this example, each element of the list in turn is stored in 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 and passed to
the 𝑑𝑜𝑆𝑜𝑚𝑒𝑡ℎ𝑖𝑛𝑔 function. The loop terminates when the current position reaches the end
of the list. Now, using the above code as a reference, write the java code for the List class
method 𝒇𝒊𝒏𝒅.
3. Using the algorithms in this note and their respective Java implementation as a guide:
a. Create insertions algorithms for doubly linked list and implement your algorithms.
b. Write deletion algorithm for a doubly linked list and implement it.
c. Write reversal traversal algorithm for backward for doubly linked lists.
d. Modify Algorithm Search and the algorithm you created in 3(c) to traverse a circular
linked list.
e. Write and implement backward search algorithms for both standard doubly linked list
and its circular version.
4. What is the time complexity to sum the number of elements in a linked list?
a. O(1)
b. O(𝑛)
c. O(log 𝑛)
d. O(𝑛2 )
5. Which of the following is false about a doubly linked list?
a. We can navigate in both the directions.
b. It requires more space than a singly linked list.
c. The insertion and deletion of a node takes a bit longer.
d. Implementing a doubly linked list is easier than singly linked list.
6. Consider an implementation of unsorted singly linked list. Suppose it has its representation
with a head pointer only. Given the representation, what are the time complexities of the
following operations?
a. Insertion at the front of the linked list
b. Insertion at the end of the linked list
c. Deletion of the front node of the linked list
d. Deletion of the last node of the linked list
7. Given the following linked list.
HEAD

NULL
CAT FROG COW PIG DOG FISH

If we perform these four operations:

i. Insert “SHEEP” after “COW”.
ii. Delete the last element.
iii. Insert “BULL” at the front of the list.
iv. Insert “SNAKE” at the end of the list.

With the of a diagram, show the state of the list after each operation the above and after the
fourth operation:
a. What does HEAD point to?
b. What does the element with data value “DOG” points to?
c. What is the last element?
d. Which element points to “PIG”?