DEV Community

Cover image for Data Structures with Python
Paul Nasdaq
Paul Nasdaq

Posted on

Data Structures with Python

Python is a high level programming language. This is a good thing if you are new to data structures, as some of the most common data structures in computer science are in built, or can be imported from a module from the Python standard library. You won't have to implement them on your own, unless you are looking for special functionality
Let us first describe what a data structure is. In layman terms, all a data structure is a collection of values. Usually these values have a relations, and you can access, use and manipulate these values from a single location, that is, a data structure.
Data structures in come in different forms, with different rules as to how you can add, remove or change the values in the data structure.

1. Lists

Lists probably the most popular and the simplest to understand data structure in Python. Values stored in a list are called the elements of a list. A list can be visualized as a sequence of elements. Elements in a list have a position, called an index. Elements can only be accessed by their position in the list i.e their index
Indexes are numerical, and start from 0 to n-1, where n is the number of elements in the list. So, for example, if we have a list that has 10 elements, the elements will have an index of 0 to 9, (not 1 to 10).
In Python, there is no restriction as to what type of elements can be stored in a particular list. There is also no restriction as to how many elements a list can contain. They can be as small or as large as you may wish.

# Creating an empty list
myList = []

# Creating a list with items
myOtherList = ['one', 2, ['three']]

# Accessing items in a list
print(myOtherList[0])         #'one'
print(myOtherList[1])         #2

# Modifying a list item
myOtherList[2] = 3
print(myOtherList)            #['one', 2, 3]

# Adding items to a list
print(myList)                 #['aValue']
Enter fullscreen mode Exit fullscreen mode

2. Dictionaries

Ptyhon dictionaries are quite a neat data structure. Items in a dictionary are accessed by a name (more specifically called a key). The key is set when you insert the item into the dictionary. Just like lists, there is no restriction as to the type or number of items a dictionary can store. As for the keys, any 'immutable type' can be used. These include strings, numbers and tuples.
Python dictionaries are synonymous to Maps or Associative Arrays from other programming languages. They are implemented using hash tables

# Creating an empty dictionary
myDict = {}

# Creating a dictionary with initial values
personDict = {name: 'Paul Nasdaq', age: 23}

# Accessing items in a dictionary
print(personDict['name'])  # 'Paul Nasdaq'
personDict['age'] = 24
print(personDict)          # {name: 'Paul Nasdaq', age: 24}
Enter fullscreen mode Exit fullscreen mode

3. Tuples

A tuple is a data structure that once created, cannot be changed (modified). That is, you cannot add, remove or change items in a tuple once it has been created. Tuples are useful for defining compound values. A compound values is a value that is made up of two or more other values. For example, a geographical location is usually made up of a longitude and a latitude. A tuple would be an excellent choice to store geographical locations in your program. It wouldn't make sense to be able to modify the longitude or latitude of a location once created, because a different value is a totally different location. Just like lists, items in a tuple can be accessed by index.

# Creating tuples
myTuple = ('one', two')
myOtherTuple = 'three', 4

# Accessing items in a tuple
print(myTuple[0])        #'one'
Enter fullscreen mode Exit fullscreen mode

4. Sets

A set allows you to store only unique values in the collection. Python sets are unordered. Therefore, elements in a set cannot

# Creating an empty set
mySet = set()

# Creating a set with values
myOtherSet = {'one', 2, 'three'}
Enter fullscreen mode Exit fullscreen mode

Computer science provides definition for more data structures than the built into python

1. Stacks

Visual representation of a stack
A stack is a data structures that allows you to access the last and only the last item that was inserted into the data structure. You can envision a stack as a bucket. You insert items into a bucket from the top one by one, but when it comes to removing items from the bucket, you remove them starting by the one that was last inserted all the way to the first. This is also known LIFO (Last In First Out) principle. Inserting an item into a stack is known as pushing the stack, and removing an item from the stack is known as popping the stack. Accessing the last inserted item in a stack without necessarily removing it from the stack is known as peeking the stack.
Since the stack data structure is not built into Python, a popular implementation involves a class wrapper around the list data structure, with methods to such as pop(), push() and peek()

class Stack:
    ”””LIFO Stack implementation using a Python list as underlying storage.”””
    def __init__(self):
        ”””Create an empty stack.”””
        # nonpublic list instance
        self. data = []
    def len(self):
        ”””Return the number of elements in the stack.””” 
        return len(
    def is_empty(self):
        ”””Return True if the stack is empty.”””
        return len(self. data) == 0
    def push(self, e):
        ”””Add element e to the top of the stack.”””
        # new item stored at end of list
    def peek(self):
        ”””Return (but do not remove) the element at the top of the stack.
        Raise Empty exception if the stack is empty.
        if self.is_empty( ):
            raise Empty( Stack is empty )
        # the last item in the list
    def pop(self):  
        ”””Remove and return the element from the top of the stack (i.e., LIFO).
        Raise Empty exception if the stack is empty.
        if empty( ):
            raise Empty( Stack is empty )
        # remove last item from list
Enter fullscreen mode Exit fullscreen mode

2. Queues

visual representation of a queue
A queue is a data structure that kind of works like a line or people waiting to be served. You are free to insert as many items into a queue as you want, but you can only remove them starting from the the first item that was inserted, one by one, all the way to the last item that was inserted. Note that this the complete opposite of the workings of the stack data structure. Such a principle is known as FIFO (First In First Out). Inserting items into a queue is known as enqueuing, and removing items from a queue is known as dequeuing.
Although one can implement a queue as a wrapper class around the list data structure with enqueue() and dequeue() methods, this approach is generally advised against. The dynamic nature of Python's lists makes them inefficient for this task.
Instead, use the deque (pronounced as deck) class from Python's collections module to create queues in your programs.

Note that deques are double-ended queues, allowing you to access items from both ends of the queue. If this is not the kind of behavior you want from your queue, you can use the Queue class from the queue module

from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           # Terry arrives
queue.append("Graham")          # Graham arrives
queue.popleft()                 # The first to arrive now leaves (Eric)
queue.popleft()                 # The second to arrive now leaves(John)
print(queue)                    # Remaining queue in order of arrival
#(['Michael', 'Terry', 'Graham'])
Enter fullscreen mode Exit fullscreen mode

Top comments (0)