Data-structures and Algorithms using Python: Programming Series 101
Last Updated on December 7, 2020 by Editorial Team
For folks who have started learning to program or willing to learn and pursue their career in fields that require programming knowledge, this post will help you guys understand the fundamentals of data structures and algorithms.
Data-structures and algorithms are one of the most fundamental aspects of programming taught in any computer science lecture. You can learn any programming language, but to be a good programmer, you have to develop a grip over data-structures and algorithms. So what is a data structure, what is an algorithm, why should we learn it?
A data structure, as the name suggests, is the building block of any programming /coding you do to design any approach to solve any problem using a programming language. That approach is also known as an algorithm in computer science terminology.
For e.g., If you are given a list of students in sorted order and asked to find whether a given student name is present in that class using programming within the least amount of time and computational resources.
To solve this programming problem, you will start thinking about the approach, which is referred to as an algorithm. Once you have an approach to solve the problem(whether or not in the least amount of time and computational resources), you will also start thinking about how to store the input in an optimal way, which is referred to as data structure.
To our problem, we can use a searching algorithm (say binary search as the input is sorted) and any suitable data structure like a list in python.
Different programming languages have different ways to implement data structures for use.
The broad categories of data structures are as follows:
Types of data-structure:
- Primitive :
These are the most fundamental data-structures present at the machine level.
E.g., integer, float, character, pointer, etc.
These are data-structures that are derived from primitive data-structures.
An array consists of a collection of homogenous elements in the continuous allocation of memory.
This is a collection of records primarily used to manage a large number of records.
This data-structure consists of dynamic memory allocation of primitive data-structure.
2.3.1. Linear lists:
The elements are stored in sequential order.
Stack: This data-structure stores and retrieves the elements in the last in first out( LIFO) format.
Queue: This data-structure stored and retrieves the elements in the first in, first out format (FIFO).
2.3.2. Non-linear lists:
The elements are not stored in sequential order.
Trees: Data-structure is stored in tree-based format with nodes and vertices connected in tree-based structure. It is a special case of a graph.
Graph: Data-structure is stored with nodes and vertices where nodes with data are connected to vertices.
To design a stack data-structure, we will use a fundamental python data-structure list.
The different functions in the stack are:
- push(): To store elements in the stack.
- pop(): To retrieve elements from the stack.
- is_empty(): To check if the stack is empty.
- size(): To get the size of the stack.
- top (): To return the top element of the stack.
Time and Space Complexity:
The time and space complexity of the algorithm is an important aspect to be calculated while coding any algorithm.
Big Oh notation (denoted by O): It measures the longest time/case taken by the algorithm to complete execution. While calculating the time/ space complexity of the algorithm, we look at the worst-case possible or the worst time/case required by the algorithm to complete any execution.
To learn more, you can visit this link.
While analyzing any algorithm, we try to calculate both time and space complexity in the worst possible scenarios.
Deletion/ Retrieval: O(1)
Space Complexity: O(n)
Pros and Cons:
The LIFO pattern of storage of elements is useful in certain applications—Eg. Calculators where operators take certain precedence.
Cons is that the data storage and access cannot be random, hence not suitable for the applications where memory management cannot be continuous.
I hope you enjoyed this post. Let me know your thoughts if you have any queries or suggestions, would love to hear more from you.
Data-structures and Algorithms using Python: Programming Series 101 was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.
Published via Towards AI