This article is a continuation of Python 101: Introduction to Modern Python where we introduced, set up and gave some basic understanding of the python. In this article we will discuss about the various data structures in Python such as lists, dictionaries, tuples, sets, queues, stack, linked list etc.
What is a data Structure?
This is a particular way of organizing data in computer so that it can be accessed/used/processed effectively.
What is a data Algorithm?
This is a finite sequence of steps/instructions on how to perform a task, run an obligation or solve a problem.
Its Important in that it can enable one to estimate the amount of resources that will be needed during implementation.
Types of Data Structures in Python
Data structures in python are divided into 2:
-
Inbuilt data structure:
These types of data structures include
lists,dictionaries,tuples,sets. -
User-defined Data structures:
These types of data structures includes
queues,stack,linked list,tree,linked-list,graphandHashMap.
They can also be categorized into linear or non-linear data structures where in Linear data structures the arrangements of data is in sequence manner e.g List, Linked-list, Queue, Stack etc while in Non-linear structures one element or node is connected to 'n' number of elements e.g tree and graphs.
List
Python Lists are just like the arrays, declared in other languages which is an ordered collection of data. It is very flexible as the items in a list do not need to be of the same type.
The implementation of Python List is similar ArrayList in JAVA. The costly operation is inserting or deleting the element from the beginning of the List as all the elements are needed to be shifted.These two operation usually takes order on n, i.e O(n) meaning the larger the size the longer the time taken.
Example of a list in Python is as shown below.
Python 3.9.9 (main, Dec 16 2021, 23:13:29)
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> mylist = ["Jeff", 44, 2.3, "Ous"]
>>> print(mylist)
Output
['Jeff', 44, 2.3, 'Ous']
List elements are accessed by the assigned index.Starting index of the list is 0 and the ending index is n-1 where n is the number of elements.
E.g to access Jeff in the above example we use 0
print(mylist[0]) this will output Jeff and print(mylist[2]) will output 2.3.
Adding Elements
Adding the elements in the list can be achieved using the append(), extend() and insert() functions.
The append() function adds all the elements passed to it as a single element.
The extend() function adds the elements one-by-one into the list.
The insert() function adds the element passed to the index value and increase the size of the list too.
mylist.append(12)
mylist.extend("Smart")
mylist.insert(1, "Lux")
print(mylist)
Output:
['Jeff', 'Lux', 44, 2.3, 'Ous', 12, 'S', 'm', 'a', 'r', 't']
Other methods associated with List are del() for deletion, len() function returns the length of the list,index() function that finds the index value of value passed where it has been encountered, count() function finds the count of the value passed to it, sorted() and sort() functions sort the values of the list and sorted() has a return type whereas the sort() modifies the original list.
Dictionaries
Dictionaries are used to store key-value pairs. It is an unordered collection of data values, used to store data values like a map. Key-value is provided in the dictionary to make it more optimized.
Indexing of Python Dictionary is done with the help of keys. These are of any hashable type. We can create a dictionary by using curly braces ({}) or dictionary.
Sample Code:
Python 3.9.9 (main, Dec 16 2021, 23:13:29)
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> dictionary = {1: "Jeff Odhiambo",2:"Lux Academy",3:"Laurent Ous"}
>>> print(dictionary)
Output:
{1: 'Jeff Odhiambo', 2: 'Lux Academy', 3: 'Laurent Ous'}
Accessing individual elements in a dictionary we can use the key e.g we can use 1 to access Jeff Odhiambo e.g run print(dictionary.get(<key>)) i.e print(dictionary.get(1)) will print Jeff Odhiambo,print(dictionary.get(2)) will print Lux Academy.
>>> print(dictionary.get(1))
Jeff Odhiambo
>>> print(dictionary.get(2))
Lux Academy
>>> print(dictionary.get(3))
Laurent Ous
>>>
Tuples
A tuple is an immutable data type in python, almost similar to a list in python in terms of indexing and having duplicate members. It stores python objects separated by commas.
Following is an example of how we can create or declare a tuple in python.
>>> tuple1=("Jeff","LUX")
>>> tuple2=(23,78)
>>> print(tuple1+tuple2)
Output
('Jeff', 'LUX', 23, 78)
>>>
Accessing items in a tuple is similar to a list, we can access elements in a tuple using indexes. We can specify the index value and it will return the item stored at that particular index value. e.g print(tuple1[0]) will output Jeff.
Other operations such as slicing using the slicing operator :, changing, concatenating two tuples, deletion can be performed on a tuple.
Sets
A set is a data type consisting of a collection of unordered elements. These elements can be on any data types as sets, i.e they are not type specific. Sets are mutable(changeable) and do not have repeated copies of elements. The values of a set are unindexed, therefore, indexing operations cannot be performed on sets.
Sample Code:
>>> set1={1.2,56,"Jeff",'G'}
>>> print(set1)
{56, 1.2, 'Jeff', 'G'}
When you try to access an object using index in a set you get 'set' object is not subscriptable, this confirms the point that indexing operation cant be performed on set.
>>> print(set1[1])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'set' object is not subscriptable
>>>
Since value in set can't be accessed using index, we can loop through it to access elements and display them as shown below.
>>> for setvalues in set1:
... print(setvalues)
...
56
1.2
Jeff
G
>>>
We can also add values to set using the update() method, remove items in the set using remove(), discard() and the pop() functions, etc.
Queues
A queue is also a linear data structure that stores items in First In First Out (FIFO) manner. With a queue the least recently added item is removed first. A good example of queue is in one of the Operating system algorithm known as FIFO where the First process in the queue is the first to be executed. Or in real world, Queuing for service at a bank, you'll be served on the basis of first come first server.
Operations Associated with Queue
Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Implementation using List
┌──(jeff㉿kali)-[~]
└─$ python3
Python 3.9.9 (main, Dec 16 2021, 23:13:29)
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> queue = []
>>> queue.append("Jeff")
>>> queue.append("12")
>>> queue.append("LUX")
>>> queue.append(45.7)
>>> print(f"Initial Queue is {queue}")
Initial Queue is ['Jeff', '12', 'LUX', 45.7]
>>> queue.pop(0)
'Jeff'
>>> queue.pop(0)
'12'
>>> queue.pop(0)
'LUX'
>>> queue.pop(0)
45.7
>>> print(f"Queue after removing element: {queue}")
Queue after removing element: []
>>>
Stack
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added ontop of the other e.g 1 is added ontop of 2 and while removing you have to start with the top most element e.g 1 is removed first followed by 2. The insert and delete operations are often called push and pop.
Associated Operations with Stack:
empty() – Returns whether the stack is empty.
size() – Returns the size of the stack.
top() – Returns a reference to the topmost element of the stack.
push(a) – Inserts the element ‘a’ at the top of the stack.
pop() – Deletes the topmost element of the stack.
Implementation using List
>>> stack = []
>>> stack.append("Jeff")
>>> stack.append("12")
>>> stack.append("LUX")
>>> stack.append(45.7)
>>> print(f"Initial stack : {stack}")
Initial stack : ['Jeff', '12', 'LUX', 45.7]
>>> stack.pop()
45.7
>>> stack.pop()
'LUX'
>>> stack.pop()
'12'
>>> stack.pop()
'Jeff'
>>> print(f"Stack after elements are removed : {stack}")
Stack after elements are removed : []
>>>
Linked list
A linked list is a sequence of data elements, which are connected together via links. Each data element contains a connection to another data element in form of a pointer as shown below.
There are 4 types of linked list:
- Singly linked lists.
- Doubly linked lists.
- Circular linked lists.
- Circular doubly linked lists.
Implementation of Linked List
class Node:
def __init__(self, data):
self.data = data # Assign data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def printList(self):
temp = self.head
while (temp):
print (temp.data)
temp = temp.next
if __name__=='__main__':
linked_list = LinkedList()
linked_list.head = Node("Jeff")
second = Node(27)
third = Node("LUX")
linked_list.head.next = second;
second.next = third;
linked_list.printList()
Output
Jeff
27
LUX
Top comments (22)
I'm kind of confused; why do you list linked lists as non-linear, but then you have trees and graphs as examples for non-linear structures? Also, by your definitions, maps wouldn't fall into either category.
In the ages of CPU cache, this needs lots of asterisks and disclaimers
linked list is linear and I listed it as linear, and explained that in linear data structures are data structures structures where data are accessed siquentially. kindly check again.
About insertion and deletion operation, they are expensive in the sence that much time can be taken as it may involve shifting of elements where a certain order is to be maintained
yes but linked lists are trees though (and, by extension, graphs)
That's... factually incorrect. Have you even looked up the definition of trees before writing an article on them?
hope this will help in understanding why one is linear and why the other is non linear
dev-to-uploads.s3.amazonaws.com/up...
But... linked lists are literally trees though; they can't be linear and non-linear at the same time 😂
EDIT: That image is nice, but wrong. Trees are just (connected) graphs without loops, so every linked list is also a tree.
I'll just quote wikipedia here:
Which perfectly applies to a linked list:
There's even a whole programming language that pretty much implements linked lists as a special case of binary trees (That's lisp I'm talking about), and you could easily do the same in any other programming language that implements trees.
I think we are also learning new stuffs in the process, maybe the resources that I was using in my research were not clear 😅. And they have given me a new Friend called DarkWiiPlayer
Yaaay!
By the way it may seem like a technicality but it's actually a really cool thing. So many things can be thought of as special kinds of graphs so learning a thing or two about those can be immensely helpful in so many programming problems 😁
So we agree that linked lists are both linear and non linear. And when using the definition of seuqnetiality would a tree not be linear because there is topological ordering from the root to leaves?
that's more clear, thanks
Linked list and an Array both are Linear, there shouldn't be a confusion about it.
Tree data structure can be constructed by the help of Linked List.
Also A linked list has previous / Next variable while a Tree have left right, the idea is To maintain linked list in linear order(left to right) while for tree it should be in Hirerchial order, (top to down)
I think you are confusing the general concept of a Tree with the more specific concept of a Binary Tree.
Tree nodes don't have left and right, they simply have descendants. Just as a Binary tree is a specific form of tree where every node has exactly two descendants (left and right), you can define a unary tree where every node has exactly one descendant, which happens to be exactly what a linked list is.
Put more simply: Take a linked list and turn it around by 90 degrees. What do you get? A tree.
Great article here 👏👏🥳 Keep the good work up
Thanks Kai 🤝🏻
Great article.
Thanks @owino
FYI python has a built in package called Queue. No need to implement queues and stacks with lists. Queue supports LIFO, FIFO, and priority.
Agreed, but was just showing how to implement a queen with a list, thanks
Also, you should mention Dataclasses and NamedTuples. Both are very useful built-in packages for storing data.
am going to consider them in my next article which will be a continuation of this