A Complete Guide to Data Structures in Python


Author :: Kevin Vecmanis


This is a post I’ve always wanted to put together - it’s a monster, comprehensive guide to implementing data structures in Python, complete with code, explanations, and use cases.

In this article you will learn about:
  • Lists
  • Numpy Arrays
  • Matrix
  • Dictionaries
  • Heaps
  • Linked Lists
  • Queues and Double-ended Queues
  • Stacks
  • Binary Trees
  • Tuples
  • Hash Tables



Table of Contents



Lists

A list is a collection which is ordered and changeable.

>>> my_list = [1,2,3,4,5,6,7,8,4,2]

# Add to a list 
>>> my_list.append(40)
>>> my_list
[1, 2, 3, 4, 5, 6, 7, 8, 4, 2, 40]

# Extend a list with another list

>>> my_list.extend(['a','b','c'])
>>> my_list
[1, 2, 3, 4, 5, 6, 7, 8, 4, 2, 40, 'a', 'b', 'c']

# Insert into specific location
>>> my_list.insert(2,'Kevin')
>>> my_list
[1, 2, 'Kevin', 3, 4, 5, 6, 7, 8, 4, 2, 40, 'a', 'b', 'c']

# Get index of entry (lowest index if duplicate exist)
>>> my_list.index(2)
1
>>> my_list.index('Kevin')
2

# Reverse the order of a list in place
>>> my_list.reverse()
>>> my_list
['c', 'b', 'a', 40, 2, 4, 8, 7, 6, 5, 4, 3, 'Kevin', 2, 1]

# Remove and return the last object from a list
>>> my_list.pop()
1
>>> my_list
['c', 'b', 'a', 40, 2, 4, 8, 7, 6, 5, 4, 3, 'Kevin', 2]

# Return the length of a list
>>> len(my_list)
14

# Count the occurrences of an object in a list
>>> my_list.count(2)
2

Numpy Arrays

While Python lists offer an efficient solution for the storage of array-based data, a numpy ndarray offers an efficient to perform operations on array-based data.

Matrix

Dicionaries

Binary Trees

Heaps

There are two types of heaps:

  • Min Heap : Each parent node is less than or equal to its child node.
  • Max Heap : Each parent node is greater than or equal to its child node.

Heaps are especially useful for implementing priority queues, or any situations where quick access is needed to the maximum or minimum value in a collection.

In python, you can implement a heap using the built in library heapq. As of this writing, the standard Python implementation of heap is a MinHeap. To get a MaxHeap, you can multiple all the values in the list by -1 and it will perform as a MaxHeap.

Creating the heap

heapify()

import heapq 
>>> h = [14,6,12,56,1,14,29,44,88]
>>> heapq.heapify(h)
>>> print(h)
[1, 6, 12, 44, 14, 14, 29, 56, 88]

Note that althought the smallest element will always be at index 0, the rest of the list isn’t necessarily sorted. That being said, the heapq.heappop() method will always pop the smallest element (removed the element from the list)

Removing from the heap

heappop()

>>> heapq.heappop(h)
1
>>> heapq.heappop(h)
6
>>> heapq.heappop(h)
12
>>> heapq.heappop(h)
14
>>> heapq.heappop(h)
14
>>> heapq.heappop(h)
29
>>> h
[44, 56, 88]
Adding to the heap

heappush()

>>> heapq.heappush(h,16)
>>> h
[16, 44, 88, 56]

Kevin Vecmanis