Data Structures in Python

Data Structures in Python describe how data should organize and stored efficiently to solve a computational problem while making their storage (space) complexity and time complexity as optimized as possible. Let us go through the topics we will cover in Data Structures in Python.

What is a Data Structure?

A data structure is a format that organizes, manages, and stores data in memory for efficient access and modification. The data structure defines the relationship between the data and the functions or operations applied to the data.

Types of Data Structures in Python

Python has implicit support four inbuilt data structures includes List, Dictionary, Tuple and Set.

Python allows its users to create their Data Structures, enabling them to control their functionality fully. The most prominent Data Structures are Stack, Queue, Tree, Linked List, and so on, which are also available to you in other programming languages.

Built-in Data Structures

As the name suggests, these data structures are Inbuilt into Python and enable programming to manage more quickly. Let’s talk in detail about each of them.

Lists in Python

A list is a mutable, or changeable, ordered sequence of elements. Each element or value inside a list is called an item.

In Python, a list is created, where all items (elements) are placed inside square brackets [] and separated by commas. It can store multiple items (integer, float, string etc.) in a single variable sequentially. A list can also have another list as an item. This is called a nested list.

Each element in the list is assigned addresses called index. The index value begins at 0 and continues until the last element is known as the positive index. There is also negative indexing, starting with -1 to access elements from last to first. Let us now better understand the lists using an example program.

Creating a list

A Lists are similar to dynamic sized arrays, you use the square brackets to create a list and add items to it accordingly. If you do not pass elements within the square brackets, the output is an empty list.

Here is simple example to create a list in Python.

List = [] #create empty list
print(List)
List = [10, 15, 30, 'Technology', 3.14] #creating list with data
print(List)

Output:

[]
[10, 15, 30, 'Technology', 3.14]

Adding Elements in List

You can add elements to the list using the functions append(), extend() and insert().

• The built-in append() function allows elements to add to the list. The list can be added by the append () method to only one element at a time; loops use to add multiple elements with the append () method. The append method can also add tuples to the list because the tuples are immutable. In contrast to Sets, lists can also be added to the existing list by the append() method.
• The append () method works only to add elements to the end of the list; the insert () method uses to add elements at the desired position. Unlike append(), the insert() function requires two arguments (position, value).
• Other than the append () and insert () methods, there is another extend() method used at the end of the list to add multiple elements at the same time.

Note: The methods append() and extend() can only add elements at the end.

List = [10, 15, 30]
print(List)
List.append([999, 15]) #add as a single element
print(List)
List.extend([786, 'Technology']) #add as different elements
print(List)
List.insert(5, 'Technology') #add element i
print(List)

Output:

[10, 15, 30] 
[10, 15, 30, [999, 15]] 
[10, 15, 30, [999, 15], 786, 'Technology'] 
[10, 15, 30, [999, 15], 786, 'Technology', 'Technology']

Deleting Elements from List

• Use the del keyword, which is Inbuilt into Python, to remove an element or slice from a list, but it doesn't return anything. 
• The pop() method removes an element from a given index and returns the deleted item. 
• The remove() method removes the first matching element (that passes as an argument). 

Example:

List = [10, 15, 30, 'Technology', 3.14, 1, 3]
del List[2] #delete element at index 5
print(List)
List.remove('Technology') #remove element with value
print(List)
a = List.pop(1) #pop element from list
print('Popped Element: ', a, ' List remaining: ', List)
List.clear() #empty the list
print(List)

Output:

[10, 15, 'Technology', 3.14, 1, 3] 
[10, 15, 3.14, 1, 3] 
Popped Element: 15 List remaining: [10, 3.14, 1, 3] 
[]

Accessing Elements in List

To access elements in lists, use the square brackets for slicing and index or indices to obtain value available at that index.

List = [10, 15, 30, 'Technology', 3.14, 1, 3]
for element in List: #access elements one by one
print(element)
print(List) #access all elements
print(List[3]) #access index 3 element
print(List[0:2]) #access elements from 0 to 1 and exclude 2
print(List[::-1]) #access elements in reverse

Output:

10 
15 
30 
Technology 
3.14 
1 
3 
[10, 15, 30, 'Technology', 3.14, 1, 3] 
Technology 
[10, 15] 
[3, 1, 3.14, 'Technology', 30, 15, 10]

Other Functions in List

You have several other functions to work with lists.

• The function len() returns the list length to us. 
• The index() function finds the index value passed where it was first found. 
• Count() finds the count of the value it receives. 
• The functions sorted() and sort() do the same, that is, to sort the list's values. 
  The sorted() has the type of return, whereas the sort() changes the original list. 

List = [10, 20, 30, 1, 2, 3]
print(len(List)) #find length of list
print(List.index(10)) #find index of element that occurs first
print(List.count(10)) #find count of the element
print(sorted(List)) #print sorted list but not change original
List.sort(reverse=True) #sort original list
print(List)

Output:

6 
0 
1 
[1, 2, 3, 10, 20, 30] 
[30, 20, 10, 3, 2, 1]

Dictionary in Python

A dictionary (also known as an associative array) is an unordered, changeable, and indexed collection used to store key-value pairs. Each pair of key values maps the key to its value.

You can define a dictionary by inserting a comma-separated list of key-value pairs in curly braces ({}). A column (:) separates each key from its value:

Note: Keys in a dictionary don’t allow Polymorphism.

Creating a Dictionary

Dictionaries can be created by curly braces or by dict(). Whenever you work with dictionaries, you need to add the key-value pairs.

dict = {} #empty dictionary
print(dict)
dict = {1: 'Technology', 2: 'Motivation'} #dictionary with elements
print(dict)

Output:

{}
{1: 'Technology', 2: 'Motivation'}

Changing and Adding key, value pairs

To change the dictionary values, you must use the keys. So first, you access the key and then change the value. You add another pair of key values to add values, as shown below.

dict = {'First': 'Technology', 'Second': 'Motivation'}
print(dict)
dict['Second'] = 'Java' #changing element
print(dict)
dict['Third'] = 'Python' #adding key-value pair
print(dict)

Output:

{'First': 'Technology', 'Second': 'Motivation'} 
{'First': 'Technology', 'Second': 'Java'} 
{'First': 'Technology', 'Second': 'Java', 'Third': 'Python'}

Deleting key, value pairs

• You can use the del keyword to remove a key-value pair in a dictionary. 
  One disadvantage is that it gives an exception if trying to delete a key that 
  does not exist. If the key is not found, the key must therefore be handled.
• The pop() method can use to remove a key and its value. The advantage over del() 
  is that it allows the desired value to print if a non-existent dict() pair 
  attempted to delete. Secondly, it returns the value of the deleted key and 
  performs a simple delete operation. 
• You use the item() function to get the key-value pair, which returns a tuple 
  of the key and its value. 
• You use the clear() function to clear the entire dictionary. 

dict = {'First': 'technology', 'Second': 'Motivation', 'Third': 'Language'}
a = dict.pop('Third') #pop element
print('Value:', a)
print('Dictionary:', dict)
b = dict.popitem() #pop the key-value pair
print('Key, value pair:', b)
print('Dictionary', dict)
dict.clear() #empty dictionary
print('n', dict)

Output:

Value: Language 
Dictionary: {'Second': 'Motivation', 'First': 'technology'} 
Key, value pair: ('Second', 'Motivation') 
Dictionary {'First': 'technology'} 
n {}

Accessing Elements from Dictionary

The get() method for accessing the elements in a dictionary is part of the standard python library. Sometimes we may have to search for a key, not in the dictionary. In such a case, the index access method will cause an error and stop the program.

dict = {'First': 'Technology', 'Second': 'Motivation'}
print(dict['First']) #access elements using keys
print(dict.get('Second'))

Output:

Technology
Motivation

Other Functions in Dictionary

You have different functions that give us the keys or key-value pair according to the functions keys(), values(), items().

dict = {'First': 'Alpha', 'Second': 'Beta', 'Third': 'Gama'}
print(dict.keys()) #get keys
print(dict.values()) #get values
print(dict.items()) #get key-value pairs
print(dict.get('First'))

Output:

dict_keys(['First', 'Second', 'Third']) 
dict_values(['Alpha', 'Beta', 'Gama']) 
dict_items([('First', 'Alpha'), ('Second', 'Beta'), ('Third', 'Gama')]) 
Alpha 

Tuple in Python

The tuple is an immutable data type in Python. It uses to store the sequence of immutable Python objects. A tuple is defined in Python by enclosing elements in parenthesis ( ) and separating elements with commas.

Tuples are the same as lists, except that the data entered into the tuple cannot be altered. The only exception is if the data is mutable inside the tuple. Only then tuple data be modified. The example programme helps you to understand better.

Creating a Tuple

You can use parenthesis or the tuple() function to create a tuple.

tuple = (10, 20, 30) #create tuple
print(tuple) 

Output:

(10, 20, 30)

Accessing Elements in Tuple

Access elements are the same as for accessing lists of values.

tupled = (10, 20, 30, 'Technology') #access elements
for x in tupled:
print(x)
print(tupled)
print(tupled[0])
print(tupled[:])
print(tupled[3][4])

Output:

10 
20 
30 
Technology 
(10, 20, 30, 'Technology') 
10 
(10, 20, 30, 'Technology') 
n 

Appending Elements in Tuple

To add values, you use the ‘+’ operator to add a different tuple.

tuple = (10, 20, 300)
tuple = tuple + (40, 50, 60) #add elements
print(tuple)

Output:

(10, 20, 300, 40, 50, 60)

Other Functions in Tuple

These functions are the same as they are for lists.

tuple = (10, 20, 30, ['Technology', 'Motivation'])
tuple[3][0] = 'Notes'
print(tuple)
print(tuple.count(2))
print(tuple.index(['Notes', 'Motivation']))

Output:

(10, 20, 30, ['Notes', 'Motivation']) 
0 
3 

Sets in Python

Sets are a unique, iterable and mutable collection of unordered elements. In other words, even if the data repeat more than once, it would only be entered once. It bases on a data structure known as a hash table. It looks like the sets you learned in arithmetic. The operations are also the same as the arithmetic sets. An example program would help you to understand better.

Creating a set in Python

Sets are created using the curly braces, but instead of adding key-value pairs, you pass them.

set = {2, 3, 4, 5, 6, 7, 7} #create set
print(set)

Output:

{2, 3, 4, 5, 6, 7}

Adding elements in Sets

You use the add() function to add elements and pass the value to it.

set = {100, 200, 300}
set.add(400) #add element to set
print(set)

Output:

{100, 200, 300, 400}

Operations in sets

The various operations on the set() such as union, intersection and so on are illustrated below.

set = {1, 2, 3, 4}
set_b = {3, 4, 5, 6}
print(set.union(set_b), '----------', set | set_b)
print(set.intersection(set_b), '----------', set & set_b)
print(set.difference(set_b), '----------', set - set_b)
print(set.symmetric_difference(set_b), '----------', set ^ set_b)
set.clear()
print(set)

• The union() function combines the two sets of data.

• The intersection() function can only find data in both sets.

• The difference() function deletes the data in both data and outputs in only the set passed.

• The symmetric difference() does the same as the difference() function but outputs that are remaining data in each set.

Output:

{1, 2, 3, 4, 5, 6} ---------- {1, 2, 3, 4, 5, 6} 
{3, 4} ---------- {3, 4} 
{1, 2} ---------- {1, 2} 
{1, 2, 5, 6} ---------- {1, 2, 5, 6} 
set()

User-Defined Data Structures

Arrays vs. Lists

Arrays and lists are the same structure with one difference. Lists are containers for heterogeneous data elements, whereas arrays are used as containers for homogeneous elements.

Stack

Stacks are linear data structures based on the last-in, first-out (LIFO) semantics, where the data that is entered last is accessed first. This array structure is built and has operations, i.e. pushing (adding) elements, popping (deleting) elements and accessing elements from only one point in the TOP stack. This TOP is the pointer of the current stack position. Stacks are used prominently in applications such as recursive programming, reverse wording, and undo mechanisms.

Queue

A queue is also a linear first-in, first-out (FIFO) data structure in which the data entered is accessed first. It is built using the array structure and has operations from both ends of the queue, i.e. head-tail or front-back. Access to the elements can be performed using enqueue and dequeue Operations, like adding and deleting elements. Queues are used as network buffers to manage traffic congestion used for operating systems job scheduling, and much more.

Tree

Trees are non-linear Data structures with roots and nodes. Tree represents the nodes connected by edges. The root is the node from which the data comes, and the nodes are the other available data points. The preceding node is the parent, and then the node is called the child. A tree must show the depth of information at levels. The final nodes are the leaves. In many real-world applications, trees create a hierarchy; for example, the HTML pages use trees to distinguish which tag is under which block. It also searches efficiently and much more.

Linked List

Linked lists are linear data structures that are not stored in consequence but are linked by pointers. The linked list node consists of data and the pointer called next. These structures are most commonly used in applications for image viewing, music player applications etc.

Graph

Graphs are used to store data collection of vertices (nodes) and edges (edges). The most accurate representation of a real-world map can be called the graphs. They are used to find the various cost-to-distance between the different data points called the nodes and find the least path. Many applications like Google Maps, Uber and many others use Graphs to find the lowest distance and improve profits.

HashMaps

HashMaps are the same as Python’s dictionaries. They can use it to implement telephone books, compile data by lists and much more.