CS计算机代考程序代写 data structure chain algorithm INN701 Lecture 3

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