CHAPTER 1

INTRODUCTION

● Introduction to Data Structures

● Operations
● Characteristics.
● Classification
● Primitive types – primitive data structures, python examples.
● Non primitive types – Non primitive data structures, python examples.
● Linear and nonlinear data structures – with python examples.
● Abstractions
● Abstract Data Types
● An Example of Abstract Data Type (Student, Date, Employee)
● Defining the ADT, Using the ADT, Implementing the ADT.

Introduction

A data structure is basically a group of data elements that are put together under one name,
and which defines a particular way of storing and organizing data in a computer so that it can
be used efficiently.

Data structures are widely applied in the following areas:

• Compiler design
• Statistical analysis package
• Numerical analysis
• Artificial intelligence
• Operating system
• DBMS
• Simulation
• Graphics

Operations

The different operations that can be performed on the various data structures are:

• Traversing It means to access each data item exactly once so that it can be
processed. For example, to print the names of all the students in a class.

• Searching It is used to find the location of one or more data items that satisfy the given
constraint. Such a data item may or may not be present in the given collection of data

GOVERNMENT POLYTECHNIC, KARWAR 1

 items. For example, to find the names of all the students who secured 100 marks in
mathematics.
• Inserting It is used to add new data items to the given list of data items. For example,
to add the details of a new student who has recently joined the course.

• Deleting It means to remove (delete) a particular data item from the given collection of
data items. For example, to delete the name of a student who has left the course.

• Sorting Data items can be arranged in some order like ascending order or descending
order depending on the type of application. For example, arranging the names of
students in a class in an alphabetical order, or calculating the top three winners by
arranging the participants’ scores in descending order and then extracting the top three.

• Merging Lists of two sorted data items can be combined to form a single list of sorted
data items.

Characteristics of a Data Structure

• Correctness − Data structure implementation should implement its interface correctly.

• Time Complexity − Running time or the execution time of operations of data structure
must be as small as possible.

• Space Complexity − Memory usage of a data structure operation should be as little as

possible.

Classification of Data Structures

Fig.1.1 Classification of Data structure in Python

GOVERNMENT POLYTECHNIC, KARWAR 2

Data structures are generally categorized into two classes: primitive and non-primitive data
structures.

Primitive and Non-primitive Data Structures

• Primitive data structures are the fundamental data types which are supported by a
programming language. Some basic data types supported by python are integer, string,
real, and boolean.

• Non-primitive data structures are those data structures which are created using
primitive data structures. Examples of such data structures include list,
arrays,tuple,set,file, dictionary.

• List data structures can further be classified into two categories: linear and non-linear
data structures.

• Linear and Non-linear Structures

• If the elements of a data structure are stored in a linear or sequential order, then it
is a linear data structure. Examples include stacks, and queues.
•
• If the elements of a data structure are not stored in a sequential order, then it is a
non-linear data structure. The relationship of adjacency is not maintained between
elements of a non-linear data structure. Examples include trees and graphs.

The Primitive Data Structures

Four primitive variable types are defined in Python, and these are as follows:
1. Integers
2. Strings
3. Boolean
4. Float

Integers

We can utilize the integer data type to represent the numeric data. for example, 52, 23, 0, or -8

String

GOVERNMENT POLYTECHNIC, KARWAR 3

Strings are collections of alphabets, words or many other characters. We can create the string
data type in Python by including an order of characters within a pair of single or double-quotes.

For example: 'tutorial', "example", etc.

Boolean

The Boolean is a built-in data type used to return the values: True and False, which can often
be interchangeable with the integers, 0 or 1. These are pretty useful in comparison and
conditional expressions.

Float

The Float is also a built-in data type that stands for 'floating point number'. These can be used
for representing rational numbers that usually ends with a decimal figure, for example, 3.14,
2.05 or 12.34

The Non-Primitive Data Structures

Non-Primitive data Structures act as the complex components of the data structures family.
Instead of storing a value, these data structures have a collection of values in different formats.
Non-primitive data structures are further classified into multiple categories:

• Arrays
• Lists
• Files

Array

Array is a collection of elements with similar data type. It holds all elements in a sequential
order.

GOVERNMENT POLYTECHNIC, KARWAR 4

Lists

Lists are the data structures used to store a collection of heterogeneous items in Python. Lists
are mutable, which indicates that their content can be changed by modifying their identity.

The lists can be represented by the square brackets: [ ], which helps hold the elements,
divided by a comma ‘,’.

List data structure can be further classified into two sub-categories: Linear Data Structures
and Non-Linear Data Structures. The Linear data structures consist of Stacks and Queues,
whereas the Non-Linear data structures consist of Graphs and Trees.

Stacks

A container of objects where objects are removed and inserted according to the LIFO (Last-In-
First-Out) principle is known as Stack.

Let’s take an example where there is a stack of plates at a dinner party. These plates are
always removed from or added to the top of the pile. The same concept is opted in computer
science to evaluate expressions and parse syntax, scheduling algorithms or routines and many
more.

Queue

A container of objects where objects are removed and inserted according to the FIFO (First-In-
First-Out) concept is known as Queue.

GOVERNMENT POLYTECHNIC, KARWAR 5

Let’s take an example of a line at a ticket counter for a ride in an amusement park. The people
are treated according to their arrival sequence. And hence the individual who reaches first is
also the first to leave.

Graphs

In Mathematics and Computer Science, the networks consist of vertices (also called nodes) is
known as a graph. These nodes may or may not be connected. The path or the line that helps
in connecting two nodes is known as an edge. The graph is said to be directed if the edge has
a particular flow direction, where the direction edge is known as an arc. At the same time, the
graph is said to be undirected if no directions are specified.

Various sectors depend on the graph and its theory principles such as social networks, maps,
molecular studies in biology and chemistry, recommended system and many more.

It is represented as G={V,E} Where V-> vertices and E -> Edges

GOVERNMENT POLYTECHNIC, KARWAR 6

Tree:
• Tree is a connected acyclic graph.
• Tree is a non-linear structure.
• Tree is a collection of nodes linked together to simulate hierarchyTrees

Tuples

Tuples are one of the standard sequence data structures. However, tuples differ from lists as
tuples are immutable, which implies that they cannot be deleted, added or edited once they are
defined.

Dictionary

Dictionaries are comprised of key-value pairs. The key is used to identify the item, whereas the
value is holding the item's value. Thus, the telephone directory has a key (contact name) and
the value (contact number) assigned to that key.

Sets

The Set data structure is used to represent a collection of diverse (unique) objects. The Sets
play a significant role in creating lists holding unique values only in the datasets. It is an
unordered collection but a mutable one.

Files

GOVERNMENT POLYTECHNIC, KARWAR 7

Files are a part of traditional data structures in Python. In the Data Science industry, where big
data appears to be usual, a programming language without the ability to store and recover
formerly stored data or information would barely be convenient.

Some of the fundamental methods and functions that allows one user to interact with files
using Python are shown below:

•The read() method is used to read entire files;

•The open() method is used to open files in the system where filename is the name of
the file to be opened;
•The write() method is used to write a string to a file and also returns the number of
characters written;
•The readline() method is used to read one line at a time; and
•The close() method is used to close the opened file.

Abstractions
An abstraction is a mechanism for separating the properties of an object and restricting the
focus only on relevant data. There are two types of abstraction procedural abstraction and
Data abstraction.
Procedural abstraction is the use of a function or method knowing what it does but ignoring
how it is accomplished.
Data Abstraction is the separation of the properties of a data type (its values and operations)
from the implementation of that data type.
Likewise in Object-oriented programming, abstraction is a process of hiding the
implementation details from the user, only the functionality will be provided to the user.

Abstract Data Type (ADT)

An abstract data type (ADT) is a programmer defined data type that specifies a set of data
values and a collection of well-defined operations that can be performed on those values.
Abstract Data Type (ADT) are defined independent of their implementation, allowing us to
focus on the use of the new data type instead of how it is implemented.
By hiding the implementation details, we can work with an abstraction and focus on what
functionality the Abstract Data Type (ADT) provides instead of how that functionality is
implemented.

GOVERNMENT POLYTECHNIC, KARWAR 8

The Date Abstract Data Type (ADT):

Defining Date ADT

A date represents a single day in the Gregorian calendar in which the first day starts on
November 24, 4713 BC.
1. Date( month, day, year ): Creates a new Date instance initialized to the given Gregorian
date which must be valid. Year 1 BC and earlier are indicated by negative year components.
2. day(): Returns the Gregorian day number of this date.
3. month(): Returns the Gregorian month number of this date.
4. year(): Returns the Gregorian year of this date.
5. monthName(): Returns the Gregorian month name of this date.
6. isLeapYear(): Determines if this date falls in a leap year and returns the appropriate boolean
value.

Implementing Date ADT

class date:
def __init__(self,a,b,c):
self.d=a

GOVERNMENT POLYTECHNIC, KARWAR 9

 self.m=b
self.y=c
def day(self):
print("Day = ", self.d)
def month(self):
print("Month = ", self.m)
def year(self):
print("year = ", self.y)
def monthName(self):
months = ["Unknown","January","Febuary","March","April","May","June","July",
"August","September","October","November","December"]
print("Month Name:",months[self.m])
def isLeapYear(self):
if (self.y % 400 == 0) and (self.y % 100 == 0):
print("It is a Leap year")
elif (self.y % 4 == 0) and (self.y % 100 != 0):
print("It is a Leap year")
else:
print("It is not a Leap year")
d1 = date(3,8,2000)
d1.day()
d1.month()
d1.year()
d1.monthName()
d1.isLeapYear()

Stack Abstract Data Type:

GOVERNMENT POLYTECHNIC, KARWAR 10

Defining Stack ADT
A stack is structured as an ordered collection of items where items are added to and removed
from the end called the “top”.
Stacks are ordered LIFO.
Stack(): creates a new stack that is empty. It needs no parameters and returns an empty stack.
push(item): adds a new item to the top of the stack. It needs the item and returns nothing.
pop(): removes the top item from the stack. It needs no parameters and returns the item. The
stack is modified.
peek(): returns the top item from the stack but does not remove it. It needs no parameters. The
stack is not modified.
isEmpty(): tests to see whether the stack is empty. It needs no parameters and returns a
boolean value.

STACK ADT
class stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def display(self):

GOVERNMENT POLYTECHNIC, KARWAR 11

 return (self.items)

s=stack()
print(s.isEmpty())
print("push operations")
s.push(11)
s.push(12)
s.push(13)
print("size:",s.size())
print(s.display())
print("peek",s.peek())
print("pop operations")
print(s.pop())
print(s.pop())
print(s.display())
print("size:",s.size())

GOVERNMENT POLYTECHNIC, KARWAR 12