Python Data Structures. Endgame.

Farida Aliyeva
4 min readDec 7, 2020

--

Grüß Gott, my loyal Python fans. In this blog post, I am going to finalize our long and spectacular journey on Python Data Structures. Are you excited? I am sure you are! Let us get it started! As promised we will cover Lists.

Linear Lists

Stacks

Stacks are linear Data Structures that are based on the principle of Last-In-First-Out (LIFO) where data that is entered last will be the first to get accessed. It is built using the array structure. The main operations of stacks are: pushing (adding) elements, popping (deleting) elements, and accessing elements only from one point in the stack called the TOP. TOP is the pointer to the current position of the stack.

Stack.

There are numerous ways to implement a stack in Python. These are:

  • list
  • collections.deque
  • queue.LifoQueue

In Python list can be used as a stack. Some minor distinctions are that 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. It can run into speed issues as it grows. This happens because items in the list are stored next to each other, and if the stack expands more than the block of memory that currently holds it, then Python needs to do some memory allocations which indeed can lead to some append() calls taking much longer than other ones.

Stack Implementation.

Queues

A queue is another linear data structure that 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 that can be performed from both ends of the Queue, that is, head-tail or front-back. These are adding called En-Queue and deleting elements called De-Queue and accessing the elements. Queues are used as Network Buffers for traffic congestion management, used in Operating Systems for Job Scheduling.

There are numerous ways to implement a queue in Python.
These are:

  • list
  • collections.deque
  • queue.Queue

Some minor implementation distinctions are that instead of enqueue() and dequeue(), append() and pop() functions are used. 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 complexity.

Queue implementation

Non-Linear Lists

Graphs

Graphs are used to store data collection of points called vertices (nodes) and edges (edges). Graphs can be called the most accurate representation of a real-world map. They are used to find the various cost-to-distance between the various data points called the nodes and hence find the least path. Many applications such as Google Maps, Uber, and many more use Graphs to find the least distance and increase profits in the best ways. A graph can be 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.

Graph implementation.

Trees

Trees are non-linear Data Structures which have root and nodes. The root is the node from where the data originates and the nodes are the other data available points. The node that precedes is the parent and the node that comes after is called the child. There are levels a tree has to show the depth of information. The last nodes are called the leaves. Trees are efficient in searching purposes and many more.

Tree implementation

That is all my dear fans, we have covered everything from the graph provided in the first part of this blog. Thank you for your precious time :)

--

--

Farida Aliyeva

Data Scientist at SDH | MS Graduate in Computer Science and Data Analytics