Introduction to Data Structures

• A Data Structure is a special format of organizing, processing, retrieving and storing data. They may not be discussed mainly but they are very vital in our systems today.
• Today we will focus on the basic data structures that are our unsung heroes of our systems today. Here is a link to an article that has more general information on What are Data Structures

1. Lists

• Lists contain multiple values in an ordered sequence. Values inside the lists are called items and are comma-separated.. - - The lists are zero-indexed hence the first value in a list is usually at index O. Indices are used for item retrieval.
• When a list is created all the elements are stored contiguously in memory(the memory allocated for a list is within the same location)

>>> pets = ["cats","dogs","rabbit","parrot"]
>>> pets[0]
'cats'
>>> pets[-1]
'parrot'
>>> pets[1:3]
['dogs', 'rabbit']
>>> pets[:3]
['cats', 'dogs', 'rabbit']
>>> pets[2:]
['rabbit', 'parrot']

List Methods

1. Append - this method adds an item to the end of the list
2. Insert - inserts an item at a particular index
3. Delete - deletes an item at a particular index
4. Remove - deletes the item passed

• If there are 2 or more instances of the same item, the first instance is usually deleted

• Sorting - ordering of items in a list

• Lists are sorted according in ascending order

• Alphabetical lists are sorted in "ASCIIbetical Order", that is uppercase letters then lowercase letters later

• Lists with multiple data types cannot be sorted

• The reverse() method orders the items in the list in descending order
  

>>> pets.append("monkey")
>>> pets
['cats', 'dogs', 'rabbit', 'parrot', 'monkey']
>>> pets.insert(1,"hamster")
>>> pets
['cats', 'hamster', 'dogs', 'rabbit', 'parrot', 'monkey']

>>> del pets[0]
>>> pets
['hamster', 'dogs', 'rabbit', 'parrot', 'monkey']
>>> pets.remove("dogs")
>>> pets
['hamster', 'rabbit', 'parrot', 'monkey']

>>> pets.sort()
>>> pets
['hamster', 'monkey', 'parrot', 'rabbit']
>>> pets.reverse()
>>> pets
['rabbit', 'parrot', 'monkey', 'hamster']

2.Tuples

• They are very similar to lists but are immutable(hence we cannot add, remove or change them in any way). This can be advantageous as python is able to run them faster than lists.
• They are formed using ( )
• I higlighted, key differences between lists and tuples in my previous blog post.

pets = ('rabbit', 'parrot', 'monkey', 'hamster')
>>> pets[0]
'rabbit'

>>> pets.add('cats')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'tuple' object has no attribute 'add'

>>> del pets[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object doesn't support item deletion

#it can also be defined with a comma after the last item to explicitly declare them as tuples
>>> pets = ('rabbit', 'parrot', 'monkey', 'hamster',)
>>> type(pets)
<class 'tuple'>

3. Dictionaries

• They are unordered data structures that store items in (Key:Value) pairs. They are defined using { } or using the **dict() **constructor.

>>> pets_colour = {'cat':'white','horse':'dark','dog':'golden'}
>>> pets_colour(cat)
>>> myfriends_age = {'Chao':21,'Too':19,'Rono':40,'Juma':32}
>>> myfriends_age
{'Chao': 21, 'Too': 19, 'Rono': 40, 'Juma': 32}

Dictionary Methods

• These methods can be used in for loops to retrieve the specified elements.
• dictionaryName.keys() - is used to retrieve the keys used in the dictionary
• dictionaryName.values() - is used to retrieve the values used in the dictionary
• dictionaryName.items() - is used to retrieve both the values and keys in the dictionary

myfriends_age = {'Chao':21,'Too':19,'Rono':40,'Juma':32}

>>> for age in myfriends_age.values():
...     print(age)
...
21
19
40
32


>>> for name in myfriends_age.keys():
...     print (name)
...
Chao
Too
Rono
Juma


>>> for name,age in myfriends_age.items():
...     print(f"{name} is {age} years old")
...
Chao is 21 years old
Too is 19 years old
Rono is 40 years old
Juma is 32 years old

4. Sets

• They are unordered(they can be saved and retrieved in whatever order and cannot be referenced by an id or key) collection of items, unchangeable and only allow unique items(hence no repetition of values).
• To create a new set, we use the set() constructor, the curly braces { } are too ambiguous and may create a dictionary instead

#creating a set using curly braces { }
odd_numbers = {1, 3, 5, 7, 9}
#check set membership
9 in odd_numbers
#results in True

#creating a set using a set constructor
>>> odd_numbers = set((1,3,5,7,9))
>>> odd_numbers
{1, 3, 5, 7, 9}

#inserting elements into the set
>>> odd_numbers.add(11)
>>> odd_numbers  
{1, 3, 5, 7, 9, 11}      

#adding a duplicate value does not change the set
odd_numbers.add(3)
odd_numbers
 {1, 3, 5, 7, 9, 11}    

#length of the set
len(odd_numbers)
6

#Removing an item
>>> odd_numbers.remove(5)
>>> odd_numbers
{1, 3, 7, 9}
>>> odd_numbers.discard(7)
>>> odd_numbers
{1, 3, 9}
>>> odd_numbers.remove(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 5
>>> odd_numbers.discard(5)
>>> odd_numbers
{1, 3, 7, 9}

#delete entire set
del odd_numbers

• Frozen Sets are immutable versions of sets. We can not insert or delete from them but rather query them.

>>> odd_numbers = frozenset({1, 3, 5, 7, 9, 11}) 
>>> odd_numbers.add(13)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

• These frozensets are hashable and can be used as dictionary keys.

>>> odd_numbers ={ frozenset({1, 3, 5, 7, 9, 11}):"These are Odd Numbers"}
>>> odd_numbers[frozenset({1, 3, 5, 7, 9, 11})]
'These are Odd Numbers'

5. Queues

• Queues function just like real-life queues observing the FIFO(First In First Out) principle. Items enqueued into the queue first are usually *dequeued * first.
• They are implemented using either lists(they can be quite slow) or inbuilt Queue module(especially used with parallel programming due to the resource locks) or the deque module from collections(for general use)

#Using Lists
>>> my_queue = []
>>> my_queue.append(1)
>>> my_queue.append(2)
>>> my_queue.append(3)
>>> my_queue
[1, 2, 3]
>>> my_queue.pop(0)#pop at index 0
1
>>> my_queue
[2, 3]

#using the queue module
>>> from queue import Queue  
>>> my_queue = Queue()
# We use .put() to insert value and .get() to pop the first one.
>>> my_queue = Queue()
>>> my_queue.put(1)
>>> my_queue.put(2)
>>> my_queue.put(3)
>>> print(list(my_queue.queue))
[1, 2, 3]
>>> my_queue.get()
1
>>> print(list(my_queue.queue))
[2, 3]

#Using collections.deque
>>> from collections import deque
>>> my_queue = deque()
>>> my_queue.append("Me")
>>> my_queue.append("Myself")
>>> my_queue.append("I")
>>> my_queue
deque(['Me', 'Myself', 'I'])
>>> my_queue.popleft()
'Me'
>>> my_queue
deque(['Myself', 'I'])

6. Stacks

• They are data structures that implement the LIFO(Last In First Out) principle of accessing, inserting or deleting items. Items are *push*ed (inserted into the stack) and *pop*ped(removed from the stack) at the top of the stack (hence does not allow random retrieval like arrays and lists)
• They can be implemented using Lists or deque module from collections

>>> my_stack = []
>>> my_stack.append("I")
>>> my_stack.append("love")
>>> my_stack.append("Python")
>>> my_stack
['I', 'love', 'Python']
>>> my_stack.pop()
'Python'
>>> my_stack
['I', 'love']


#using deque
>>> from collections import deque
>>> my_stack = deque()
>>> my_stack.append("I")
>>> my_stack.append("love")
>>> my_stack.append("Python")
>>> my_stack
deque(['I', 'love', 'Python'])
>>> my_stack.pop()
'Python'

7. Linked Lists

** Whew! This is a whole topic but I'll skim over the basics here.

• Linked lists is a data structure that contains a chain of nodes in different parts of memory that are linked to each other.
• There are different types of linked lists(singly and doubly). Singly linked lists can be traversed in only one direction - left to right while doubly linked lists can be traversed left to right and right to left.
• Each node contains its own data value and a memory address that references to the memory location of the next node.

Creating a Node - create a node class with the data and next variables.

>>> class Node:
...   # constructor
...   def __init__(self, data, next=None):
...     self.data = data
...     self.next = next
...
>>> # Create a single node
>>> first = Node(3)
>>> print(first.data)
3

Create a Linked List

• The first element in the Linked List is the head of the list.

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

Linking nodes within the list

new_node = Node(data)
head.next = new_node

There is a lot to cover within Linked Lists, I won't cover majority of it here since this post is getting too long.

• Data structures are very vital and if you want to work in FAANG companies, mastery of this structures will come in handy.
• This is just the tip of the iceberg. Advanced structures like graphs in Dijkstra's Algorithm are used in Google Maps for distance estimations.
• A very important part of data structures is their Memory and Time Complexities. These complexities dictate the advantage of one structure over another for different use cases.

In the meantime, let me know in the comments section where the data structures above can be fundamental.