Introduction to Data Structures and Algorithms With Modern Python

Introduction

Data is a common word we all hear from day to day. What is data 🤔. Data are facts and statistics that are collected together for reference or analysis to obtain trends and information.
What about structure?
Structure is the arrangement of and relations between the parts or elements of something complex.

Now we have an insight of data and structure what about data structure?
Data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.The data structure organization,management and storage data format enables efficient access, store collections of data, relate them, perform operations on them accordingly and modification.

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer a bit string, representing a memory address, that can be itself stored in memory and manipulated by the program.

What you need for this article

• Introduction to modern python in order to get the syntax on how to code in Python.
• Have a positive mind that coding is manageable.
• Keep moving on 💪

Let's get to know more about data structures.

Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type.

Different data structures are better suited to different applications, and some are highly specialized to certain tasks. For example, B-tree indexes are extensively used in relational databases for data retrieval, while hash tables are commonly used in compiler implementations to seek up identifiers.
For applications such as big databases and internet indexing services, data structures provide a way to efficiently manage massive amounts of data. In most cases, building efficient algorithms necessitates the use of efficient data structures.
Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Data structures can be used to organize the storage and retrieval of information stored in both main memory and secondary memory.

Types of Data Structures in Python

Python has implicit(built-in) support for Data Structures which enable you to store and access data. These structures are called List, Dictionary, Tuple and Set.
There are user-defined data structures that allow user to full control on their functionality.These structures are called queues,stack and linked lists.

Built-in Data Structures

1. List
Python Lists are just like the arrays, declared in other languages which is an ordered collection of data. They are very flexible as the items in a list they aren't supposed to be of the same type.
To create a list, you use the square brackets and add elements into it accordingly. If you do not pass any elements inside the square brackets, you get an empty list as the output.

Adding Elements

Adding the elements in the list can be achieved using the append(), extend() and insert() functions.

• The append() function adds all the elements passed to it as a single element.
• The extend() function adds the elements one-by-one into the list.
• The insert() function adds the element passed to the index value and increase the size of the list too.

Deleting Elements

• To delete elements, use the del keyword which is built-in into Python but this does not return anything back to us.
• If you want the element back, you use the pop() function which takes the index value.
• To remove an element by its value, you use the remove() function.

Accessing Elements

Accessing elements is the same as accessing Strings in Python. You pass the index values and hence can obtain the values as needed.

Other Functions
You have several other functions that can be used when working with lists.

• The len() function returns to us the length of the list.
• The index() function finds the index value of value passed where it has been encountered the first time.
• The count() function finds the count of the value passed to it.
• The sorted() and sort() functions do the same thing, that is to sort the values of the list. The sorted() has a return type whereas the sort() modifies the original list.

2. Dictionaries

Dictionaries are used to store data values in key:value pairs.They can be ordered, means that the items have a defined order, and that order will not change.They can also be unordered where the items does not have a defined order, you cannot refer to an item by using an index.Dictionaries are changeable, meaning that we can change, add or remove items after the dictionary has been created.Dictionaries cannot have two items with the same key

Creating a Dictionary

Dictionaries can be created using the flower braces or using the dict() function. You need to add the key-value pairs whenever you work with dictionaries.

Changing and Adding key, value pairs

To change the values of the dictionary, you need to do that using the keys. So, you firstly access the key and then change the value accordingly. To add values, you simply just add another key-value pair as shown below.

Accessing Elements
You can access elements using the keys only. You can use either the get() function or just pass the key values and you will be retrieving the values.

Other Functions
You have different functions which return to us the keys or the values of the key-value pair accordingly to the keys(), values(), items() functions accordingly.

3. Tuple

Tuples are used to store multiple items in a single variable and is a collection which is ordered, unchangeable, and allow duplicate values.They are written with round brackets.

Creating a Tuple

You create a tuple using parenthesis or using the tuple() function.

Accessing Elements

Accessing elements is the same as it is for accessing values in lists.

Appending Elements

To append the values, you use the + operator which will take another tuple to be appended to it.

Other Functions
These functions are the same as they are for lists.

4. Sets

A set is a collection which is unordered, unchangeable, unindexed and do not allow duplicate values.

Creating a set
Sets are created using the flower braces but instead of adding key-value pairs, you just pass values to it.

Adding elements

To add elements, you use the add() function and pass the value to it.

Remove element

To remove an item in a set, use the remove(), or the discard() method.

Other functions

• The clear() method empties the set.
• The del keyword will delete the set completely.
• You can loop through the set items by using a for loop:

my_set = {"apple", "banana", "cherry"}

for x in my_set:
  print(x)

Now that you have understood the built-in Data Structures, let’s get started with the user-defined Data Structures.

User-Defined Data Structures

User-defined Data Structures, the name itself suggests that users define how the Data Structure would work and define functions in it. This gives the user whole control over how the data needs to be saved, manipulated and so forth.

1. Queue

A queue is a linear data structure which is based on the principle of First-In-First-Out (FIFO) where the data entered first will be accessed first. It is built using the array structure and has operations which can be performed from both ends of the Queue, that is, head-tail or front-back. Operations such as adding and deleting elements are called En-Queue and De-Queue and accessing the elements can be performed. Queues are used as Network Buffers for traffic congestion management, used in Operating Systems for Job Scheduling and many more.

Operations associated with queue are:

1. Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity : O(1)
2. Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity : O(1)
3. Front: Get the front item from queue – Time Complexity : O(1)
4. Rear: Get the last item from queue – Time Complexity : O(1)

Implementation

1. list
List is a Python’s built-in data structure that can be used as a queue.However, lists are quite slow for this purpose because inserting or deleting an element at the beginning requires shifting all of the other elements by one, requiring O(n) time as compare to queue(),deque().Instead of enqueue() and dequeue(), append() and pop() function is used.

2. collections.deque

Queue in Python can be implemented using deque class from the collections module. Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. Instead of enqueue() and deque(), append() and popleft() functions are used.

3. queue.Queue

Queue is built-in module of Python which is used to implement a queue. queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A maxsize of zero ‘0’ means a infinite queue. This Queue follows FIFO rule.

There are various functions available in this module:

• maxsize – Number of items allowed in the queue.
• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
• get() – Remove and return an item from the queue. If queue is empty, wait until an item is available.
• get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
• put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
• qsize() – Return the number of items in the queue.

output

2. Stack

Stacks are linear Data Structures which are based on the principle of Last-In-First-Out (LIFO) where data which is entered last will be the first to get accessed. It is built using the array structure and has operations namely, pushing (adding) elements, popping (deleting) elements and accessing elements only from one point in the stack called as the TOP. This TOP is the pointer to the current position of the stack. Stacks are prominently used in applications such as Recursive Programming, reversing words, undo mechanisms in word editors and so forth.

The functions associated with stack are:

• empty() – Returns whether the stack is empty – Time Complexity: O(1)
• size() – Returns the size of the stack – Time Complexity: O(1)
• top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)
• push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
• pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

Implementation

Python’s built-in data structure list can be used as a stack. Instead of push(), append() is used to add elements to the top of the stack while pop() removes the element in LIFO order.
Unfortunately, the list has a few shortcomings. The biggest issue is that it can run into speed issues as it grows. The items in the list are stored next to each other in memory, if the stack grows bigger than the block of memory that currently holds it, then Python needs to do some memory allocations. This can lead to some append() calls taking much longer than other ones.

3. Linked list

Linked lists are linear Data Structures which are not stored consequently but are linked with each other using pointers. The node of a linked list is composed of data and a pointer called next. These structures are most widely used in image viewing applications, music player applications and so forth.

When to use deque() as a linked list?

• Inserting and deleting elements at front and back respectively is the only need. Inserting and removing elements from the middle becomes time-consuming.
• In-place reversal since Python now allows elements to be reversed in the place itself.
• Storage is preferred over performance and not all elements get a separate node of their own.

Below is the implementation of the linked list:

output:

Conclusion

That was a great moment getting to know more about data structures in modern python. Hope you had a great time through the article. Thank you for taking the time to read this.

KEEP ON MOVING