D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

Part I
Data Structures
8

---

Chapter 2
Linked Lists
Linked lists can be thought of from a high level perspective as being a series
of nodes. Each node has at least a single pointer to the next node, and in the
last node’s case a null pointer representing that there are no more nodes in the
linked list.
In DSA our implementations of linked lists always maintain head and tail
pointers so that insertion at either the head or tail of the list is a constant
time operation. Random insertion is excluded from this and will be a linear
operation. As such, linked lists in DSA have the following characteristics:
1.
Insertion is O(1)
2.
Deletion is O(n)
3.
Searching is O(n)
Out of the three operations the one that stands out is that of insertion. In
DSA we chose to always maintain pointers (or more aptly references) to the
node(s) at the head and tail of the linked list and so performing a traditional
insertion to either the front or back of the linked list is an O(1) operation. An
exception to this rule is performing an insertion before a node that is neither
the head nor tail in a singly linked list. When the node we are inserting before
is somewhere in the middle of the linked list (known as random insertion) the
complexity is O(n). In order to add before the designated node we need to
traverse the linked list to find that node’s current predecessor. This traversal
yields an O(n) run time.
This data structure is trivial, but linked lists have a few key points which at
times make them very attractive:
1.
the list is dynamically resized, thus it incurs no copy penalty like an array
or vector would eventually incur; and
2.
insertion is O(1).
2.1
Singly Linked List
Singly linked lists are one of the most primitive data structures you will find in
this book. Each node that makes up a singly linked list consists of a value, and
a reference to the next node (if any) in the list.
9

---

CHAPTER 2. LINKED LISTS
10
Figure 2.1: Singly linked list node
Figure 2.2: A singly linked list populated with integers
2.1.1
Insertion
In general when people talk about insertion with respect to linked lists of any
form they implicitly refer to the adding of a node to the tail of the list. When
you use an API like that of DSA and you see a general purpose method that
adds a node to the list, you can assume that you are adding the node to the tail
of the list not the head.
Adding a node to a singly linked list has only two cases:
1.
head = ∅ in which case the node we are adding is now both the head and
tail of the list; or
2.
we simply need to append our node onto the end of the list updating the
tail reference appropriately.
1) algorithm Add(value)
2)
Pre: value is the value to add to the list
3)
Post: value has been placed at the tail of the list
4)
n ← node(value)
5)
if head = ∅
6)
head ← n
7)
tail ← n
8)
else
9)
tail.Next ← n
10)
tail ← n
11)
end if
12) end Add
As an example of the previous algorithm consider adding the following se-
quence of integers to the list: 1, 45, 60, and 12, the resulting list is that of
Figure 2.2.
2.1.2
Searching
Searching a linked list is straightforward: we simply traverse the list checking
the value we are looking for with the value of each node in the linked list. The
algorithm listed in this section is very similar to that used for traversal in §2.1.4.

---