Arrays, Linked
Lists, and
Selection Sort
Data Structures and Algorithms
Objectives:
• Describe how computer
memory works.
• Differentiate arrays from linked
lists.
• Explain selection sorting
algorithm.
Memory
Memory is used to
store information,
such as data and
programs, for
immediate use in a
computer.
Memory
Memory can be
compared to a set of
drawers. Each
drawer can hold one
item. If you need to
store 2 items, you’ll
need 2 drawers.
Memory
To find an item, a drawer
must have an address.
When you ask the
computer for some
space in memory, it gives
you an address where
you can store the item.
Memory
If you are trying to
store multiple
items, there are 2
basic ways to do so;
by using arrays and
lists.
Arrays and
Linked Lists
Arrays
An array is a linear data
structure that stores a
collection of elements
of the same data type.
The items are stored
contiguously (right next
to each other) in
memory.
Arrays
Each element has a
unique index number
which is used to
identify the element.
Index numbers begin
at index zero (0).
Arrays
An array’s length is
the number of
elements stored in
that array.
Types of Arrays
An array can be
single dimensional
or multi-
dimensional
(sometimes called a
matrix)
Arrays in Memory
Suppose you have a
to-do list containing
3 items, the array in
the memory might
look something like
this…
Arrays in Memory
If you need to add a
fourth item to the
list, you cannot do
so easily because
the next space is
already occupied.
Arrays in Memory
In such a case, you
need to ask the
computer for a larger
chunk of memory
where your items will
fit. The array must be
transferred to a
different location.
Arrays in Memory
Similarly, adding
new items to the
array can be difficult
if the space in the
memory is limited.
Arrays in Memory
A workaround for this problem is to reserve extra space
in case your list will have additional items. However…
• This extra space cannot be used for other items or
arrays, even if the extra space is empty.
• If you add more items so that the extra space is not
enough, you’ll need to find another region in the
memory big enough for all the additional items.
Operations on Arrays
• Traverse – iterating (going over) through the elements
of an array.
• Insert – adding an element to the array at a specific
index.
• Delete – removing an element from the array at a
specific index.
Operations on Arrays
• Update – change an element at a specific index.
• Display – show the contents of the array.
• Search – search an element using a specific
index or value.
Array Data Structure
(tutorialspoint.com)
• Array – Insertion
Operation
• Array – Deletion
Operation
• Array – Search
Operation Hands-On Demo
Linked Lists
A linked list is a linear
data structure that
stores data in nodes,
which are connected by
pointers. Unlike arrays,
linked lists are not The head node points to the first node. Every node
holds data and a next pointer (which holds the
stored in contiguous memory address of the next node in the linked list).
memory locations. The last node or tail node points to null, indicating
the end of the list.
Linked Lists in Memory
With linked lists, your
items can be
anywhere in the
memory.
Linked Lists in Memory
Because the elements
in a linked list are not
next to each other, you
cannot quickly find a
specific element. You
have to find the first
element, the second,
and so on.
Types of Linked Lists
Singly Linked List – each
node contains 2 buckets;
one for the data and the
other for the address of
the next node on the list.
Traversal can be done in
only one direction.
Types of Linked Lists
Doubly Linked List – each
node contains 3 buckets;
one for data, and two for
the previous and next
nodes.
The list is traversed twice
as the nodes in the list are
connected to each other
from both sides.
Types of Linked Lists
Circular Linked List –
can exist in both singly
and doubly linked list.
The first and last nodes
are connected.
Traversal in this list will
go on forever until it is
broken.
Run Times for Common Operations
O(n) = linear time
O(1) = constant time
Inserting Elements in the
Middle of a List
Inserting an element in the middle of a list is as easy as changing
what the previous element points to.
Inserting Elements in the
Middle of an Array
When inserting an element in the middle of an array, the rest of the
elements must be shifted down. If there is no space, everything must
be copied to a new location.
Operations on Linked Lists
• Insert – add an element at the beginning of
the list.
• Display – display the complete list.
• Search – search an element using the given
key.
Operations on Linked Lists
• Deletion – deletes an element at the beginning
of the list.
• Delete – deletes an element using the given
key.
• Traverse – iterate through the elements by
accessing each node.
Linked List Data
Structure
(tutorialspoint.com)
• Insertion at
Beginning, Ending,
and at Given Position
• Linked List Deletion
Hands-On Demo
Suppose you are making an app
for taking customer orders in a
restaurant. The app needs to
store a list of orders. Servers
keep adding orders to this list,
and chefs take orders off the list
and make them. Would you use
an array or linked list to
implement this order queue?
Practice Time
Selection Sort
Selection Sort
Selection sort is a
simple and efficient
sorting algorithm that
works by repeatedly
selecting the smallest (or
largest) element from the
unsorted portion of the
list and moving it to the
sorted portion of the list.
Selection Sort
Suppose you want
to sort this list from
most played to the
least played, how
can you do it?
Selection Sort
Selection Sort
Selection Sort
Selection Sort
The entire sorting algorithm will take O(n * n) time or O(n2) time.
Selection Sort
Algorithm
(tutorialspoint.com)
• Selection Sort
Implementation
Hands-On Demo
References
Bhargava, A. (2016). Grokking Algorithms – An illustrated guide for
programmers and other curious people.
GeeksforGeeks. (2024). Learn Data Structures and Algorithms DSA
Tutorial. https://www.geeksforgeeks.org/learn-data-structures-and-
algorithms-dsa-tutorial/#dsa-full-form
TutorialsPoint. (nd). Data Structures and Algorithms (DSA) Tutorial.
https://www.tutorialspoint.com/data_structures_algorithms/index.htm
