INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 3 – Linear data structures and
searching algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• In this lecture we study:
– Linear data structures
– Two search algorithms
• Sequential search (linear search)
• Binary search
CRICOS No. 00213J
a university for the worldreal R 3
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 1.4, 3.2 and 4.4.
CRICOS No. 00213J
a university for the worldreal R
Linear data structure
• A linear data structure has data elements logically arranged in a
linear manner.
• Each element except for the first and last element in the data
structure has a previous element and a next element.
• Examples of linear data structures:
– Array
– Linked list
– Stack
– Queue
4
CRICOS No. 00213J
a university for the worldreal R
Array
• Array is an elementary linear data structure.
• A (one-dimensional) array is a sequence of n items of the same data
type that are stored contiguously in computer memory.
• An item in an array is accessible by index.
• In the majority of cases, the index is an integer between 0 and n-1.
• Each and every element of an array can be accessed in the same
constant amount of time in a computer regardless of where in the
array the element in question is located.
• Arrays can be used for implementing a variety of other data
structures.
5
CRICOS No. 00213J
a university for the worldreal R
Linked list
• A linked list is sequence of zero or more elements called nodes,
each containing an item and one or two links called pointers to other
nodes of the linked list.
• A special pointer called “null” is to indicate no link.
• In a single linked list, each node except for the last one contains a
single pointer to the next node.
• In a double linked list, each node except for the first and the last,
contains a pointer to its successor and a pointer to its predecessor.
6
CRICOS No. 00213J
a university for the worldreal R
Linked list
• The pointer to a linked list – that is, the pointer to the first node in the
linked list is stored – is stored in a separated location
• A linked list is a dynamic data structure
• The length of a linked list is the number of nodes in the list
7
CRICOS No. 00213J
a university for the worldreal R
Array vs linked list
• Both array and linked list can be used to implement a more abstract
data structure called list, which is a sequence of items.
• The basic operations performed on lists are accessing, searching
for, inserting, and deleting an item.
– To access the kth entry in an array or a linked list
• In an array, we can access it using an index item[k]
• In a linked list, we must step through the first k–1 nodes
8
CRICOS No. 00213J
a university for the worldreal R
Array vs linked list
– To insert an item to the beginning of an array or a linked list
• In an array, we must move all the elements in the array
before we can insert the item, which is not efficient for large
arrays
• In a linked list, we can directly insert the item to the beginning
of the linked list, which is efficient
9
CRICOS No. 00213J
a university for the worldreal R
Array vs linked list
– To delete an item from an array or a linked list
• In an array, we must move all the items after the deleted item
in the array
• In a linked list, we do not need to move any item. But we
need to traverse the pointer chain to find the pointer to the
predecessor, and the pointer to the successor, of the node
containing the item to be deleted.
10
CRICOS No. 00213J
a university for the worldreal R
Array vs linked list
– To search an item in an array or a linked list
• In an array, we can search the array sequentially or use
binary search if the elements in the array are sorted
• In a linked list, we need to traverse the pointer chain to find
the node where the item is stored.
11
CRICOS No. 00213J
a university for the worldreal R 12
Stack
A stack is a linear data structure that stores items sequentially
and allows access to the top only.
Adding an item
– Referred to as pushing it onto the stack
Removing an item
– Referred to as popping it from the stack
Items stored in a stack are kept in a pile.
– When an item is pushed into a stack, it is placed at the top of
the pile.
– When an item is taken from a stack, it is always the top item.
A stack is a LIFO (Last In First Out) data structure.
12
CRICOS No. 00213J
a university for the worldreal R 13
Stack
Basic operations: Push and Pop
empty stack
Push(1)
1
Push(3)
1
3
Push(2)
1
3
2
1
3
Pop() 2
1
Pop() 3
13
CRICOS No. 00213J
a university for the worldreal R
Stack
• Summary
– A stack is a data structure in which the items are added and
deleted from one end only
– A stack is a Last In First Out (LIFO) data structure
– The two basic operations on a stack are:
• Push an item onto the stack
• Pop an item from the stack
– A stack can be implemented as an array or a linked list
– The middle items in a stack cannot be accessed directly
– Stacks are restricted version of arrays and linked list
14
CRICOS No. 00213J
a university for the worldreal R
Applications of stack
• Stacks can be used to check parenthesis matching in an
expression
• Stacks can be used for expression evaluation
• Stacks can be used for conversion from one form of expression to
another
• Stacks can be used for memory management
• Stacks are used in backtracking algorithms
15
CRICOS No. 00213J
a university for the worldreal R 16
Queue
A queue is a linear data structure that allows certain operations
on both ends
It provides one operation, Enqueue, to add an item to the data
structure, and an operation, Dequeue, to remove an item from the
data structure.
Items are added into a queue at one end of the queue (tail) and
items are removed out of a queue at the other end of the queue
(head).
A queue is an FIFO (First-In-First-Out) data structure.
16
CRICOS No. 00213J
a university for the worldreal R 17
Queue
• Basic operations
1 3 2
tailhead
1 3 2
tailhead
Enqueue(5)
5
Enqueue(9)
1 3 2
tailhead
5 9
3 2
tailhead
5 9
Dequeue() 1
2
tailhead
5 9
Dequeue() 3
17
CRICOS No. 00213J
a university for the worldreal R
Queue
• Summary
– A queue is a data structure in which the items are added at one
end and removed from the other end
– A queue is a First In First Out (FIFO) data structure
– The two basic operations on a queue are:
• Enqueue – add an item to the tear of the queue
• Dequeue – remove an item from the head of the queue
– A queue can be implemented as an array or a linked list
– The middle items in a queue cannot be accessed directly
– Queues are restricted versions of arrays and linked lists
18
CRICOS No. 00213J
a university for the worldreal R
Applications of queue
• Queues are used in algorithm design
• Queues are used in CPU scheduling
• Queues are used in disk scheduling
• Queues are used in managing shared resources between
various processes
• Queues can be used in data transferring between IO buffers
(Input and Output buffers)
19
CAB301 Algorithms and Complexity��Lecture 3 – Linear data structures and searching algorithms
Aims of this lecture
References
Linear data structure
Array
Linked list
Linked list
Array vs linked list
Array vs linked list
Array vs linked list
Array vs linked list
Stack
Stack
Stack
Applications of stack
Queue
Queue
Queue
Applications of queue