Overview

• This section provides fundamental knowledge in the

application of different data structures and algorithms.

1 : Introduction to Data Structures

IT3206 – Data Structures and Algorithms

Level II - Semester 3

© e-Learning Centre, UCSC © e-Learning Centre, UCSC 2

Intended Learning Outcomes

List of subtopics

• At the end of this lesson, you will be able to; 1. Introduction to data structures
• Explain the use of data structures 1.1. Introduction to data structures
• Demonstrate different implementation techniques of 1.2. Use of Data Structures
data structures 1.2.1. Real- world data storage
• Compare different applications of data structures 1.2.2. Programmer’s Tools
1.2.3. Real-world Modeling
1.3. Classification of Data Structures

© e-Learning Centre, UCSC 3 © e-Learning Centre, UCSC 4

1.1 Introduction to data structures

1.1 Introduction to data structures cont.
• Data structures are containers that are capable of storing
data in a computer (or memory/ persistent storage)
• Algorithms manipulate the data in the data structure such as
searching for a particular data item, sorting the data etc.
• Data structures include arrays, linked lists, queues, stacks, Queue
binary trees, and hash tables etc.

Examples

Array

Stack

Linked list

© e-Learning Centre, UCSC 5 © e-Learning Centre, UCSC 6

1.2 Use of Data Structures 1.2.1 Real-world data storage

The use of data structures can be studied mainly in • Many of the structures and techniques considered here
these three categories: are about how to handle real-world data storage.
• Real-world data mean that the data that describes
• Real-world data storage physical entities external to the computer.
• Programmer’s tools
• Real-world modeling Examples

• A personnel record describes an actual human being.

• An inventory record describes an existing car part or
grocery items.
• Financial transaction record describes an actual check
written to pay the electric bill.

© e-Learning Centre, UCSC 7 © e-Learning Centre, UCSC 8

 1.2.1 Real-world data storage cont. 1.2.1 Real-world data storage cont.

• A stack of index cards can be considered as a non- • Most programs are complex than index cards.
computer related example of real-world data storage. • Imagine the database the Department of Motor
Vehicles uses to keep track of drivers’ licenses, or an
• These cards can be used for a variety of purposes. airline reservations system that stores passenger and
• If each card holds a person's name, address, and flight information.
phone number, the result is an address book. • Such systems may include many data structures.
• If each card holds the name location, and value of
a household possession, the result is a home
inventory.

© e-Learning Centre, UCSC 9 © e-Learning Centre, UCSC 10

1.2.2 Programmer’s Tools 1.2.3 Real-world modeling

• Not all data storage structures are used to store real-world

data. • Some data structures directly model real-world
• Typically, real-world data is accessed more or less directly situations.
by the users of some programs.
• Some data storage structures, however, are not meant to Examples
be accessed by the user, but by the program itself.
• Evaluation of mathematical expressions
• A programmer uses such data structures as tools to carry
• Queue of print jobs to the printer
out a particular task during the execution of a program.
• Queue of programs/process to be run
Example : A stack can be used to check whether
• Queue of network data packets to be send
parentheses, braces, and brackets are balanced in a
• Graphs to represent airline routes between cities or
program.
connections in an electric circuit or tasks in a project.
Examples: Queues, Trees, and priority queues are often • Queues to model customers waiting in line at a bank
used in this way. or cars waiting at a toll booth.
© e-Learning Centre, UCSC 11 © e-Learning Centre, UCSC 12

1.3 Classification of Data Structures 1.3 Classification of Data Structures

• A data structure is a special format for organizing and 2. Non – linear data structures: Elements of this data
storing data. structure are stored/accessed in a hierarchical manner.
• Depending on the organization of the elements, data
structures are classified into two types: Examples: Trees and graphs.

1. Linear data structures:

• A Linear data structure has data elements arranged
sequentially, and each member element is connected to its
previous and next element.
• This connection helps to traverse a linear data structure in
a single level and a single run. Such data structures are
easy to implement as computer memory is also sequential.
• Examples of linear data structures are List, Queue, Stack,
Array etc.

© e-Learning Centre, UCSC 13 © e-Learning Centre, UCSC 14

Summary

Real-world data mean that the data that

1.2.1 describes physical entities external to the
computer.

A programmer uses data structures as tools

1.2.2 to facilitate the required operations.

Some data structures directly model real-

1.2.3 world situations.

© e-Learning Centre, UCSC 15