Today Topic as Data Structures

                        Python - Data Structure

Data structures deal with how the data is organized and held in the memory when a program processes it. It is important to note that the data that is stored in the disk as part of persistent storages (like relational tables) are not referred as data structure here.

An Algorithm is step by step set of instruction to process the data for a specific purpose. So an algorithm utilizes various data structures in a logical way to solve a specific computing problem.

General Data Structures

The various data structures in computer science are divided broadly into two categories shown below. We will discuss about each of the below data structures in detail in subsequent chapters.

Liner Data Structures

These are the data structures which store the data elements in a sequential manner.

• Array: It is a sequential arrangement of data elements paired with the index of the data element.
• Linked List: Each data element contains a link to another element along with the data present in it.
• Stack: It is a data structure which follows only to specific order of operation. LIFO(last in First Out) or FILO(First in Last Out).
• Queue: It is similar to Stack but the order of operation is only FIFO(First In First Out).
• Matrix: It is two dimensional data structure in which the data element is referred by a pair of indices.

Non-Liner Data Structures

These are the data structures in which there is no sequential linking of data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence.

• Binary Tree: It is a data structure where each data element can be connected to maximum two other data elements and it starts with a root node.
• Heap: It is a special case of Tree data structure where the data in the parent node is either strictly greater than/ equal to the child nodes or strictly less than it’s child nodes.
• Hash Table: It is a data structure which is made of arrays associated with each other using a hash function. It retrieves values using keys rather than index from a data element.
• Graph: .It is an arrangement of vertices and nodes where some of the nodes are connected to each other through links.

Python Specific Data Structures

These data structures are specific to python language and they give greater flexibility in storing different types of data and faster processing in python environment.

• List: It is similar to array with the exception that the data elements can be of different data types. You can have both numeric and string data in a python list.
• Tuple: Tuples are similar to lists but they are immutable which means the values in a tuple cannot be modified they can only be read.
• Dictionary: The dictionary contains Key-value pairs as its data elements.

Python - Arrays

Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array.

• Element− Each item stored in an array is called an element.
• Index − Each location of an element in an array has a numerical index, which is used to identify the element.

Array Representation

Arrays can be declared in various ways in different languages. Below is an illustration.

As per the above illustration, following are the important points to be considered.

·         Index starts with 0.

·         Array length is 10 which means it can store 10 elements.

·         Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9.

Basic Operations

Following are the basic operations supported by an array.

·         Traverse − print all the array elements one by one.

·         Insertion − Adds an element at the given index.

·         Deletion − Deletes an element at the given index.

·         Search − Searches an element using the given index or by the value.

·         Update − Updates an element at the given index.

Array is created in Python by importing array module to the python program. Then the array is declared as shown eblow.

from array import *

arrayName = array(typecode, [Initializers])

Typecode are the codes that are used to define the type of value the array will hold. Some common typecodes used are:

Typecode	Value
b	Represents signed integer of size 1 byte/td>
B	Represents unsigned integer of size 1 byte
c	Represents character of size 1 byte
i	Represents signed integer of size 2 bytes
I	Represents unsigned integer of size 2 bytes
f	Represents floating point of size 4 bytes
d	Represents floating point of size 8 bytes

Before lookign at various array operations lets create and print an array using python.
The below code creates an array named array1.

from array import *

array1 = array('i', [10,20,30,40,50])

for x in array1:

 print(x)

When we compile and execute the above program, it produces the following result −

Output

10

20

30

40

50

Python - Lists

The list is a most versatile datatype available in Python which can be written as a list of comma-separated values (items) between square brackets. Important thing about a list is that items in a list need not be of the same type.
Creating a list is as simple as putting different comma-separated values between square brackets. For example −

list1 = ['physics', 'chemistry', 1997, 2000];

list2 = [1, 2, 3, 4, 5 ];

list3 = ["a", "b", "c", "d"]

Similar to string indices, list indices start at 0, and lists can be sliced, concatenated and so on.

Python - Tuples

A tuple is a sequence of immutable Python objects. Tuples are sequences, just like lists. The differences between tuples and lists are, the tuples cannot be changed unlike lists and tuples use parentheses, whereas lists use square brackets.
Creating a tuple is as simple as putting different comma-separated values. Optionally you can put these comma-separated values between parentheses also. For example −

tup1 = ('physics', 'chemistry', 1997, 2000);

tup2 = (1, 2, 3, 4, 5 );

tup3 = "a", "b", "c", "d";

The empty tuple is written as two parentheses containing nothing −

tup1 = ();

To write a tuple containing a single value you have to include a comma, even though there is only one value −

tup1 = (50,);

Like string indices, tuple indices start at 0, and they can be sliced, concatenated, and so on.

Python - Dictionary

In Dictionary each key is separated from its value by a colon (:), the items are separated by commas, and the whole thing is enclosed in curly braces. An empty dictionary without any items is written with just two curly braces, like this: {}.
Keys are unique within a dictionary while values may not be. The values of a dictionary can be of any type, but the keys must be of an immutable data type such as strings, numbers, or tuples.