Tutorial: Python Lists for Linear Data Structures

Introduction

Python lists are dynamic data structures that can be used in various ways while programming for an application-based project. The use of lists makes the code conceptually easy to understand and the readability of the code also increases significantly. Python lists can also be easily typecasted to many data structures according to the requirements, so the conversion is possible in just one line of code. This tutorial focuses on implementing various linear data structures using Python Lists.

Linear Data Structures

Arrays

• Array is a data structure consisting of a collection of elements, each identified by at least one array index or key.
• Implementation using Python lists:
  1. Define the size of the array as N
  2. Create a list of N elements where every element is zero
  3. Now you can access each element of the list using its index ranging from [0, N-1]

N=5
arr = [0]*N
print(arr)
>> [0, 0, 0, 0, 0]

arr[0] = 1
arr[1] = 2
print(arr)
>> [1, 2, 0, 0, 0]

Matrices

• Matrices are the data structures with m horizontal rows and the n vertical columns. Each element of a matrix is often denoted by a variable with two subscripts. For example, a21 represents the element at the second row and first column of the matrix.
• Implementation using Python Lists:
  1. Define the number of columns of the matrix as M.
  2. Define the number of rows of the matrix as N.
  3. Create a list named 'cols' of M elements where every element is zero
  4. Create a nested list of N elements of the list 'cols' and name it as 'mat'
  5. Now you can access each element of the matrix by accessing the elements in the nested list format mat[1][0]

M=3
N=2
cols = [0]*M
mat = [cols]*N
print(mat)
>> [[0, 0, 0], [0, 0, 0]]
mat[0][1] = 24
mat[1][2] = 15
print(mat)
>> [[0, 24, 0], [0, 0, 15]]
print(mat[1][2])
>> 15

M=4
N=4
cols = [0]*M
mat = [cols]*N
print(mat)
>> [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Strings

• String is a sequence of characters, either as a literal constant or as some kind of variable.
• Implementation using Python lists:
  1. Define the string using inverted commas.
  2. Store the string value in a variable, let's say S.
  3. The object of string created can be typecast to a list, which will store each character as a separate element of the list
  4. If the string is in the form of a sentence, then the .split() method can be used to store each word as a separate element in the list.

S = "Saumitra"
lst = list(S)
print(lst)
>> ['S', 'a', 'u', 'm', 'i', 't', 'r', 'a']

S= "Saumitra Jagdale knows python language"
lst = S.split()
print(lst)
>> ['Saumitra', 'Jagdale', 'knows', 'python', 'language']

Dictionaries

• Dictionaries are data structures that are more generally known as an associative array. A dictionary consists of a collection of key-value pairs. Each key-value pair maps the key to its associated value.

• Implementation using Python Lists:

  1. Define a nested list in the form of a matrix of order N x 2 where N is the number of key-value pairs you require in your dictionary.
  2. Let there be a variable 'i' which represents the number of a row of the matrix, hence 0 <= i < N.
  3. Create a variable 'a' for the nested list, and define the a[i][0] as the key and a[i][1] as the value elements of the matrix.
  4. Now typecast this nest list 'a' to the dictionary using dict() function.

a = [['Tendulkar', 10], ['Kohli', 18], ['Dhoni', 7]]
d = dict(a)
print(d)
>> {'Tendulkar': 10, 'Kohli': 18, 'Dhoni': 7}

a=[[1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 49]]
d = dict(a)
print(d)
>> {1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49}

• While typecasting a dictionary into the list, only the 'key' elements from the dictionary are converted to the list whereas, the 'value' elements from the dictionary are lost in this typecasting process.

d = {1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49}
a = list(d)
print(a)
>> [1, 2, 3, 4, 5, 6, 7]

d = {'Tendulkar': 10, 'Kohli': 18, 'Dhoni': 7}
a = list(d)
print(a)
>> ['Tendulkar', 'Kohli', 'Dhoni']

Queues

• Queue is a collection of entities that are kept in a sequence and can be modified by the addition of elements at one end of the sequence and the removal of elements from the other end of the sequence.
• Implementation using Python lists:
  1. Define the sequence of elements of the queue.
  2. Create an empty list object as variable Q and append the elements in a sequence using Q.append(val) method, this operation is also called enqueuing.
  3. For removing the elements use the Q.pop(0) method of the created object of the list which will remove the element of the zeroth index, this operation is also called dequeuing.

# Lets say sequence is: 1 4 9 16  

# Enqueuing
Q = []
Q.append(1)
Q.append(4)
Q.append(9)
print(Q)
>> [1, 4, 9]

Q.append(16)
print(Q)
>> [1, 4, 9, 16]

# Dequeuing
Q.pop(0)
print(Q)
>> [4, 9, 16]

Q.pop(0)
Q.pop(0)
>> [16]

Stacks

• Stack is a data structure that serves as a collection of elements, with two main features: push, which adds an element to the collection, and pops, which removes the most recently added element that was not yet removed
• Implementation using Python lists:
  1. Define the sequence of elements of the stack.
  2. Create an empty list object as variable S and append the elements in a sequence using S.append(val) method, this operation is also called pushing.
  3. For poping the elements use the S.pop() method of the created object of the list which will remove the element of the last index.

# Lets say sequence is: 1 4 9 16  

# Pushing
S = []
S.append(1)
S.append(4)
S.append(9)
print(S)
>> [1, 4, 9]

S.append(16)
print(Q)
>> [1, 4, 9, 16]

# Poping
S.pop()
print(S)
>> [1, 4, 9]

S.pop()
S.pop()
>> [1]

NOTE

• The method implemented above is not an optimized way to implement data structures with respect to time and space complexity.
• Linked List (Singly, Doubly and Circular) needs to address allocation which is not possible by only using lists, so a proper structure of class and methods are needed to be designed for that.