In this article we are going to define data structures and look at the different types of data structures ,then we look at algorithms and their relation to data structures.
What is a data structure ?
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
Data structures make it easy for users to access and work with the data they need in appropriate ways. Most importantly, data structures frame the organization of information so that machines and humans can better understand it.
A data structure may be selected or designed to store data for the purpose of using it with various algorithms.
**
Types of data structures
**
Below is a general representation of the types of data structures we have
**
1.Built-in Data-structures:
**
1. Lists:
Stores indexed elements that are changeable and can contain duplicate items.
The list is changeable, meaning that we can apply the following methods on a list
-Append - this method adds an item to the end of the list
-Insert - inserts an item at a particular index
-Delete - deletes an item at a particular index
-Remove - deletes the item passed
Lists are one of 4 built-in data types in Python used to store collections of data, the other 3 are Tuple, Set, and Dictionary, all with different qualities and usage.
Lists are created using square brackets:
>>> fruits= ["apples","berries","mangoes","grapes"]
>>> pets[0]
'apples'
>>> pets[-1]
'mangoes'
>>> pets[1:3]
['apples', 'berries']
>>> pets[:3]
['apples', 'berries', 'mangoes']
>>> pets[2:]
['mangoes', 'grapes']
2.Tuples:
Stores indexed, unchangeable elements that can have duplicate copies
A tuple is a collection which is ordered and unchangeable.
Tuples are written with round brackets.
Note: Creation of Python tuple without the use of parentheses is known as Tuple Packing.
-Tuple items are ordered, unchangeable, and allow duplicate values.
-Tuple items are indexed, the first item has index [0], the second item has index [1] etc.
-Tuples are Ordered : When we say that tuples are ordered, it means that the items have a defined order, and that order will not change.
-Tuples are Unchangeable : Tuples are unchangeable, meaning that we cannot change, add or remove items after the tuple has been created.
-Tuples Allow Duplicates
Since tuples are indexed, they can have items with the same value.
Different types of tuples
#EmptyTuple
tuple = ()
print(tuple)
>>()
#Tuple having integers
tuple = (1, 2, 3)
print(tuple)
>> (1, 2, 3)
# tuple with mixed datatypes
tuple = (1, "Hello", 3.4)
print(tuple)
>>(1, 'Hello', 3.4)
# nested tuple
tuple = ("mouse", [8, 4, 6], (1, 2, 3))
print(tuple)
>>('mouse', [8, 4, 6], (1, 2, 3))
3.Dictionaries:
Python dictionary is an unordered collection of items. Each item of a dictionary has a key/value pair.
Dictionaries are optimized to retrieve values when the key is known. Store key-value pairs that are changeable . Dictionaries are written with curly brackets.
Methods & Description :
clear() - Removes all items from the dictionary.
copy() - Returns a shallow copy of the dictionary.
fromkeys(seq[, v]) - Returns a new dictionary with keys from seq and value equal to v (defaults to None).
get(key[,d]) - Returns the value of the key. If the key does not exist, returns d (defaults to None).
items() - Return a new object of the dictionary's items in (key, value) format.
keys()- Returns a new object of the dictionary's keys.
pop(key[,d])- Removes the item with the key and returns its value or d if key is not found. If d is not provided and the key is not found, it raises KeyError.
popitem() - Removes and returns an arbitrary item (key, value). Raises KeyError if the dictionary is empty.
setdefault(key[,d]) - Returns the corresponding value if the key is in the dictionary. If not, inserts the key with a value of d and returns d (defaults to None).
update([other]) - Updates the dictionary with the key/value pairs from other, overwriting existing keys.
values() - Returns a new object of the dictionary's values
Example of a dictionary :
thisdict = {
"brand": "Ford",
"model": "Mustang",
"year": 1964
}
print(thisdict)
>> {'brand': 'Ford', 'model': 'Mustang', 'year': 1964}
4.Sets:
A Set is an unordered collection data type that is iterable, mutable and has no duplicate elements. Python's set class represents the mathematical notion of a set.
A set is a collection which is unordered, unchangeable*, and unindexed
# Python program to
# demonstrate sets
# Same as {"a", "b", "c"}
myset = set(["a", "b", "c"])
print(myset)
>> {'c', 'b', 'a'}
# Adding element to the set
myset.add("d")
print(myset)
>> {'d', 'c', 'b', 'a'}
**
2. User-defined Data-structures:
**
1. Arrays:
Similar to Lists, but store single type of elements
An array is basically a data structure which can hold more than one value at a time. It is a collection or ordered series of elements of the same type.
We can loop through the array items easily and fetch the required values by just specifying the index number. Arrays are mutable(changeable) as well, therefore, you can perform various manipulations as required.
Python Arrays and lists are store values in a similar way. But there is a key difference between the two i.e. the values that they store. A list can store any type of values such as integers, strings, etc. An arrays, on the other hand, stores single data type values. Therefore, you can have an array of integers, an array of strings, etc.
from array import *
array1 = array('i', [10,20,30,40,50])
for x in array1:
print(x)
>>
10
20
30
40
50
2. Stack:
Linear LIFO (Last-In-First-Out) Data structure
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop
The functions associated with stack are:
empty() – Returns whether the stack is empty
size() – Returns the size of the stack
top() – Returns a reference to the topmost element of the stack
push(a) – Inserts the element ‘a’ at the top of the stack
pop() – Deletes the topmost element of the stack
Stack in Python can be implemented using the following ways:
-list
-Collections.deque
-queue.LifoQueue
PUSH into a Stack
Let us understand, how to use PUSH in Stack. Refer the program mentioned program below −
Example ::
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return self.stack[-1]
AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.peek()
print(AStack.peek())
AStack.add("Wed")
AStack.add("Thu")
print(AStack.peek())
>>Tue
>>Thu
3. Queues:
Linear FIFO (First-In-First-Out) data structure
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
class Queue:
def __init__(self):
self.queue = list()
def addtoq(self,dataval):
# Insert method to add element
if dataval not in self.queue:
self.queue.insert(0,dataval)
return True
return False
def size(self):
return len(self.queue)
TheQueue = Queue()
TheQueue.addtoq("Mon")
TheQueue.addtoq("Tue")
TheQueue.addtoq("Wed")
print(TheQueue.size())
>> 3
4. Trees:
Non-Linear data structures having a root and nodes
A Tree is a Data structure in which data items are connected using references in a hierarchical manner. Each Tree consists of a root node from which we can access each element of the tree
5. Linked Lists:
Linear data structures that are linked with pointers
Linked lists are an ordered collection of objects. What makes them different from normal lists is that Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block to store references to their data, linked lists store references as part of their own elements.
example : A linked list is created by using the node class . We create a Node object and create another class to use this node object. We pass the appropriate values through the node object to point the to the next data elements. The below program creates the linked list with three data elements.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
**
6. Graphs:
Store a collection of points or nodes along with edges
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges. The various terms and functionalities associated with a graph is described in great detail in our tutorial here.
In this chapter we are going to see how to create a graph and add various data elements to it using a python program. Following are the basic operations we perform on graphs.
Display graph vertices
Display graph edges
Add a vertex
Add an edge
Creating a graph
A graph can be easily presented using the python dictionary data types. We represent the vertices as the keys of the dictionary and the connection between the vertices also called edges as the values in the dictionary.
Example:
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
# Create the dictionary with graph elements
graph = {
"a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
# Print the graph
print(graph)
>>>{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}
7.Hash Maps:
In Python, Hash Maps are the same as Dictionaries
maps keys to its value pairs (implement abstract array data types). It basically makes use of a function that computes an index value that in turn holds the elements to be searched, inserted, removed, etc. This makes it easy and fast to access data. In general, hash tables store key-value pairs and the key is generated using a hash function.
Hash tables or has maps in Python are implemented through the built-in dictionary data type. The keys of a dictionary in Python are generated by a hashing function. The elements of a dictionary are not ordered and they can be changed.
An example of a dictionary can be a mapping of employee names and their employee IDs or the names of students along with their student IDs.
example :
# Declare a dictionary
dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
# Accessing the dictionary with its key
print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']
>>dict['Name']: Zara
>>dict['Age']: 7
What are Algorithms?
Algorithms are rules or instructions that are formulated in a finite, sequential order to solve problems and get the required results. They give the pseudocode for problems and can be implemented in several languages as they are not language-specific.
How do you Write Algorithms?
Algorithms are generally written as a combination of user-understandable language and some common programming languages. They are commonly written down in steps however, it is not always necessary to do so. There are no distinct rules to formulate algorithms but you will need to keep the following points in mind:
1.Figure out what is the exact problem
2.Determine where you need to start
3.Determine where you need to stop
4.Formulate the intermediate steps
5.Review your steps
For example, an algorithm to check if a student has passed in an exam or not, we follow the given steps:
Step 1: START
Step 2: Declare two variables x, y
Step 3: Store the marks obtained by the student in x
Step 4: Store the minimum passing score in y
Step 5: Check if x is greater than or equal to y. If yes, then return “Pass” else return “Fail”
Step 6: STOP
However, you can manipulate the steps according to your preference. For instance, you can assign the values to the variables in step 2 itself rather than taking steps 3 and 4. This way, a single problem can have multiple solutions and it depends on the problem and the programmer to choose the most feasible and reliable solution.
**
Elements of a Good Algorithm:**
1.The steps need to be finite, clear and understandable
2.There should be a clear and precise description of inputs and outputs
3.Each step need to have a defined output that depends only on 4.inputs in that step or the preceding steps
5.The algorithm should be flexible enough to mold it in order to allow a number of solutions
6.The steps should make use of general programming fundamentals and should not be language-specific
Conclusion
Basically, an algorithm will use data structures to store/structure data. Both are intertwined . Data structures on the other hand improve the performance of an algorithm
Top comments (0)