Introduction to Data Structures and Algorithms With Python

(source images: google)

This is an introduction to data structures and algorithms in Python a sequel to Introduction to Modern Python

Data Structures and algorithms are fundamental for every programmer when starting out learning a new language.

Data Structures describe how data is arranged to allow operations to be performed on them efficiently. This describes how we organize, process, retrieve and store data. Some of the common data structures are lists, tuples, dictionaries, sets, linked lists, and arrays.

Algorithms define the set of operations and instructions that enables the processing of data.

Understanding Data Structures in Python

We are going to look at data structures in Python; lists, dictionaries, tuples, sets, queues, stacked and linked list.

Python Lists

Lists define a set of values which are ordered in a sequence of elements enclosed in square brackets, [].The elements in a list can be changed otherwise said to be mutable.

Example list

myList = ["Rono", "Python", "Code"]

Output these elements by typing:

print(myList)

['Rono', 'Python', 'Code']

This example list has a set of elements which can be accessed by their position in the list starting from position [0].

myList[0]

'Rono'

Lists may allow you to duplicate values by adding similar elements on the list

myList = ['Python', 'Java', 'Python', 'JavaScript']

Output length of list

print(len(myList))

A list can also contain different data types

myList= ["ABC", 56, False, 78, "female"]

A list can also be created using the list() constructor when square brackets are not used

myList = list(("orange", "banana", "pineapple"))

More to learn about lists
Sorting Lists

Copy lists

Join lists

List methods

Python Dictionaries

Dictionaries in Python store data in key: value pairs contained inside curly braces {}.
Like lists, they are changeable but do not allow duplicates

example dictionary

myDict = 
      {"name": Rono', 
       "Age":7, 
       "gender": 'male'
      }

{'name': 'Rono', 'Age': 7, 'gender': 'male'}

To access an item in a dictionary:

myDict['name']

Outputs:

'Rono'

Change value:

myDict['name'] = "Python"

{'name': 'Python', 'Age': 7, 'gender': 'male'}

Remove item using pop():

myDict= {
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964
}
myDict.pop("model")
print(myDict)

Output:

{'brand': 'Ford', 'year': 1964}

Learning more on dictionaries

Loop dictionaries

     for x in myDict:
       print(x)

Copy dictionaries

  anotherDict = myDict.copy()
  print(anotherDict)
  {'brand': 'Ford', 'year': 1964}

Nested dictionaries

myDict = {"firstPerson":{"name": "Rono", "age":7},
          "secondPerson":
         {"name": "Collins", "age":8}
         }
print(myDict)
{'firstPerson': {'name': 'Rono', 'age': 7}, 'secondPerson': {'name': 'Collins', 'age': 8}}

The dictionary above contains two dictionaries within it. The first one has the title firstPerson and then contains the details of the first person in a dictionary. The second dictionary within our dictionary contains details of the second person secondPerson

Python Tuples

Tuples are used to store several items in a single variable.
Tuples are unchangeable unlike lists and dictionaries. Meaning once you create a tuple you cannot alter its contents.
They are also indexed from item [0] like in lists. Therefore you can access the tuple elements.

fruits = ('orange', 'banana', 'pineapple')

type(fruits)

<class 'tuple'>

The variable fruits creates a tuple containing a list of fruits
type is an in-built method in python returns the class types of objects. In the above code it outputs the class type of variable fruits as <class 'tuple'>

Length of tuple:

print(len(fruits))

3

A tuple can contain different data types:

car1= ("Engine", 444, False, 440, "Toyota")

Using tuple() constructor

fruits= tuple(("apple", "banana", "cherry"))

Sets in Python

Sets are used to store multiples elements in a single variable within curly braces. They are unordered, unindexed and unchangeable

mySet= {"pineapple", "pawpaw", "apple"}

print(mySet)

{'apple', 'pineapple', 'pawpaw'}

Sets does not allow duplication of items, therefore does not recognize two similar items

A set can also contain items of different data types i.e. strings 'name', integers 7, Boolean true, false

It is possible to create a set using set() constructor

Queues in Python

Queues in python are linear data structures in which operations are performed in a First In First Out FIFO. The first element in is the first element out. Just like in a normal customer queue in which the first customer to enter is the first customer to be served.

Some operations performed on queues are:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity : O(1)

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity : O(1)

Front: Get the front item from queue – Time Complexity : O(1)

Rear: Get the last item from queue – Time Complexity : O(1)

Stacks in Python

Stacks is a linear data structure that stores data in a linear manner and an element is connected to the previous and next element. Elements are accessed in a Last In First Out order. The last element to be added is the first one to be retrieved.

Operations carried out in stacks are:
empty() – Returns whether the stack is empty – Time Complexity: O(1)

size() – Returns the size of the stack – Time Complexity: O(1)

top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)

push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)

pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

Linked lists in Python

Linked list is a sequence of data elements which are connected together in form of nodes. Each data element contain connection to the next data element in form of a pointer.

There are different ways in which elements are pointed to the next or previous nodes. The firs node is head node and last node in a linked list known as tail node:

Singly linked lists

Doubly linked lists

Circular linked lists

Circular doubly linked lists

A singly linked list is a one direction linked list. So, you can only traverse it in one direction say from tail node to head node or head node to tail node.

A doubly linked list is a bi-directional linked list. You can transverse it in both directions, next and previous. An element has an extra previous pointer.

A circular linked list is also a unidirectional linked list. However, it has it's last node pointing to head node.

A circular doubly linked list is a mixture of a doubly linked list and a circular linked list. Like the doubly linked list, it has an extra pointer called the previous pointer, and similar to the circular linked list, its last node points at the head node. This type of linked list is the bi-directional list. So, you can traverse it in both directions.

This is an introduction to data structures and algorithms in Python a sequel to Introduction to Modern Python