Some data structures in Python

All this content is based on the SoloLearn Python Data Structures course.

Working with strings

count(str) returns how many times the str substring appears in the given string.
upper() converts the string to uppercase.
lower() converts the string to lowercase.
replace(old, new) replaces all occurrences of old with new. len(str) returns the length of the string (number of characters).
f-String

name = "Rami"
print(f"Hello {name}") # output: Hello Rami

join method

list_of_strings = ["Hello", "my", "friend"]
my_string_joined = " ".join(list_of_strings) # output: Hello my friend

Working with lists

Use lists if you have a collection of data that does not need random access. Try to choose lists when you need a simple, iterable collection that is modified frequently.

List manipulations

append(item) adds an item to the end of the list.
insert(index, item) adds an item at the given index in the list.
remove(item) removes an item from the list.
pop(index) removes the item at the given index.
count(item) returns a count of how many times an item occurs in the list.

List operations

reverse() reverses items in the list.
sort() sorts the list. By default, the list is sorted ascending. You can specify reverse=True as the parameter, to sort descending.
max(list) returns the maximum value.
min(list) returns the minimum value.

List comprehensions

Example. Create cubes of these numbers: 0, 1, 2, 3, 4

cubes = [i**3 for i in range(5)]
print(cubes) # output: [0, 1, 8, 27, 64]

A list comprehension can also contain an if statement to enforce a condition on values in the list.

evens = [i**2 for i in range(10) if i**2 % 2 == 0]
print(evens) # output: [0, 4, 16, 36, 64]

Useful functions

enumerate(lista_data): Getting the index and the number of a list

data = [1, 2, 5, 6, 7]
for idx, num in enumerate(data):
    do_something(idx, num)

sorted(list_data): Getting list sorted

data = [1, 2, 5, 6, 7]
sorted_list = sorted(data, reverse=True) # reverse is by default False.

set(data): making our list data unique. the results will be a set data type

data = [1, 1, 2, 2, 5, 6, 7, 7]
unique_set = set(data) # <class 'set'>

counter numbers in a list

from collections import Counter
data = [1, 1, 2, 2, 5, 6, 7, 7, 7]
counts = Counter(data) # output: {1:2, 2:2, 5:1, 6:1, 7:3}
# check most_common instance function

Working with dictionaries

Use a dictionary, when you need a logical association between a key:value

get function

pairs = {
      1: "apple",
      "orange": [2, 3, 4],
      True: False,
      12: "True",
    }
print(pairs.get("orange"))  # output: [2, 3, 4]
print(pairs.get(7, 42))  # output: 42
print(pairs.get(12345, "not found"))  # output: not found
print(pairs["this-key-does-not-exist"])  # KeyError exception

set a default key in a dictionary if it does not exist

my_dict={'name': 'John', 'age': 23}
count=my_dict.setdefault("count", 0)
print(my_dict) # output: {'name': 'John', 'age': 23, 'count': 0}

sorted(dict_data): Getting a dictionary sorted by a key using lambda function as well

my_dict = [
    {"name": "John", "age": 24},
    {"name": "Pepe", "age": 26},
]
sorted_dict = sorted(my_dict, key = lambda x: x["age"])

merge dicts

d1 = {"name": "Pepe", "age": 23}
d2 = {"name": "Pepe", "city": "Madrid"}
d = {**d1, **d2} # d -> {"name": "Pepe", "age": 23, "city": "Madrid"}

Working with tupples

Use tuples when your data cannot/should not change.

Tuples are very similar to lists, except that they are immutable (they cannot be changed).

TypeError

words = ("spam", "eggs", "sausages",)
words[1] = "cheese" # TypeError: 'tuple' object does not support item assignment

An advantage of tuples over lists is that they can be used as keys for dictionaries (because they are immutable):

dict = {
    ("David", 42): "red",
    ("Bob", 24): "green"
}
print(dict[("Bob", 24)]) # output: green

Unpacking

numbers = (1, 2, 3)
a, b, c = numbers
print(a) # output: 1
print(b) # output: 2
print(c) # output: 3

Asterisk (*)

a, b, *c, d = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a) # output: 1
print(b) # output: 2
print(c) # output: [3, 4, 5, 6, 7, 8]
print(d) # output: 9

For generating numbers it is better to use tupples than lists -> memory savings

my_numbers = (i for i in range(100))

Working with sets

Use a set if you need uniqueness for the elements.

Sets are collections of unordered items that are unique.

Sets cannot contain duplicate elements

num_set = {1, 2, 3, 3, 4, 4, 5}
print(num_set) # output: {1, 2, 3, 4, 5}

add function: add new items to the set
remove function: delete a specific element

Sets can be combined using mathematical operations.

The union operator | combines two sets to form a new one containing items in either.
The intersection operator & gets items only in both.
The difference operator - gets items in the first set but not in the second.
The symmetric difference operator ^ gets items in either set, but not both.

first = {1, 2, 3, 4, 5, 6}
second = {4, 5, 6, 7, 8, 9}
print(first | second) # output: {1, 2, 3, 4, 5, 6, 7, 8, 9}
print(first & second) # output: {4, 5, 6}
print(first - second) # output: {1, 2, 3}
print(second - first) # output: {8, 9, 7}
print(first ^ second) # output: {1, 2, 3, 7, 8, 9}

Stacks

A stack can be implemented using a list in Python.

A stack is a simple data structure that adds and removes elements in a particular order.

Every time an element is added, it goes on the "top" of the stack. Only an element at the top of the stack can be removed, just like a stack of plates. This behavior is called LIFO (Last In, First Out).

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop(0)

    def print_stack(self):
        print(self.items)

s = Stack()
s.push('a')
s.push('b')
s.push('c')
s.print_stack() # output: ['c', 'b', 'a']

s.pop()
s.print_stack() # output: ['b', 'a']

Queue

Python lists are the easiest way to implement a queue functionality.

A queue is similar to a stack, but defines a different way to add and remover elements. The elements are inserted from one end, called the rear, and deleted from the other end, called the front. This behavior is called FIFO (First in First Out).

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def print_queue(self):
        print(self.items)

q = Queue()
q.enqueue('a')
q.enqueue('b')
q.enqueue('42')
q.print_queue() # output: ['42', 'b', 'a']

q.dequeue()
q.print_queue() # output: ['42', 'b']

Linked List

Linked lists can also be used to create other data structures, such as stack, queues and graphs.

A linked list is a sequence of nodes where each node stores its own data and a link to the next node.

Applications: Linked lists are useful when your data is linked. For example when you need undo/redo functionality, the nodes can represent the state with links to the previous and next states. Another example would be a playlist of music, where each clip is linked with the next one.

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def add_at_front(self, data):
        self.head = Node(data, self.head)

    def add_at_end(self, data):
        if not self.head:
            self.head = Node(data, None)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(data, None)

    def get_last_node(self):
        n = self.head
        while(n.next != None):
            n = n.next
        return n.data

    def is_empty(self):
        return self.head == None

    def print_list(self):
        n = self.head
        while n != None:
            print(n.data, end = " => ")
            n = n.next
        print()


s = LinkedList()
s.add_at_front(5)
s.add_at_end(8)
s.add_at_front(9)

s.print_list() # output: 9 => 5 => 8 =>
print(s.get_last_node())  # output: 8

Graph

Graphs are used to represent many real-life applications like networks, transportation paths of a city, and social network connections.

A graph is a set of connected nodes where each node is called a Vertex and the connection between two of them is called an Edge.

class Graph():
    def __init__(self, size):
        self.adj = [ [0] * size for i in range(size)]
        self.size = size

    def add_edge(self, orig, dest):
        if orig > self.size or dest > self.size or orig < 0 or dest < 0:
            print("Invalid Edge")
        else:
            self.adj[orig-1][dest-1] = 1
            self.adj[dest-1][orig-1] = 1

    def remove_edge(self, orig, dest):
        if orig > self.size or dest > self.size or orig < 0 or dest < 0:
            print("Invalid Edge")
        else:
            self.adj[orig-1][dest-1] = 0
            self.adj[dest-1][orig-1] = 0

    def display(self):
        for row in self.adj:
            print()
            for val in row:
                print('{:4}'.format(val),end="")

#a sample Graph
G = Graph(4)
G.add_edge(1, 3)
G.add_edge(3, 4)
G.add_edge(2, 4)
G.display()
# output:
# 0   0   1   0
# 0   0   0   1
# 1   0   0   1
# 0   1   1   0