⌨️ Data Structures Made Easy (Python) ⌨️
RYANTADIPARTHI (6017)

⌨️ Data Structures Made Easy (Python) ⌨️

hi guys, in this tutorial, i will be covering few data structures in python. Here is the table of contents.

Table of contents

  • What are data structures
  • Why are they useful
  • big O notation
  • linked lists
  • lists
  • dictionaries
  • sets
  • ending

So let's get started


What are data structures

Data structures are data organization that can make accessing and organizing something easier, and quicker. They make your algorithms, and the way you write code better.

for example, you have some problem like a coding test. To solve that test, you need to use a data structure. whether it may be a set, or dictionary, or list. So learning these will help you decide which one is used for what.

Why are they useful?

Data structures are useful because they help organize your code properly, and you can know what to use, and when. IT makes your code more efficient.

Now, we will start the real thing

Big O Notation

The big o notation is a very useful data structure. It's used everywhere. in any code you write.

What it is, is basically, it checks what the time complexity of your code is. like how much time you took, and how much it should take. for example, this:

for i in range(5):
    print(i)

now, if you knew the big o notation, you would know the time complexity of it. In this case it is O(n).

For this data structure, to tell what it is, you use O() so it stands for order of n. like that.

like how much time you took, and how much it should take

So you might be wondering based on that statement, how does it tell the time. Well, there are different ways to tell it. In this case, n stands for how many times it loops. it could loop forever, which is why, when looping, it's order of n. O(n).

Some others could be O(1), O(X).

Just so you know, O(1) is really bad. if you have that, you might want to change it.

so let's see another example. how about two for loops?

for i in range(5):
    for k in range(5):
        print(i, k)

that right there is O(n^2). This is order of n squared. Why? Because, there is one for loop: O(n) then, another, which is squared. There resulting: O(n^2).

That's basically it for big O notation

Linked Lists

Linked lists are another useful data structure in python. Mostly when asked about this, it would be probably be like reversing it, or making it right.

To explain linked lists, let's understand the CPU of how python creates memory in lists, and stuff like that.

usually, it has 5 spaces available when you make one. And to append more, it creates another 5 more. Well, that can be bad sometimes, with the big O, and all. So linked lists, make that easier, by making space quicker, and making them available.

Let's make a few methods using the linked lists to make it more understandable.

first, we should make a node. to get next values and all.

class Node:  
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

now, let's go on with the methods. First method is insert at the beginning. So we want to be able to insert at beginning. Usually you would use .append() for this, but we are seeing the code for .append() in action.

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

    def insert_at_beginning(self, data):
        node = Node(data, self.head)
        self.head = node

so what i did there was, made a new class, and get the node data. So we get the node head - to start from, and then the data. Which when we call, we are going to put. a list. that's the insert at beginning. Now, we can do the print. for printing all methods.

def print(self):
        if self.head is None:
            print("Linked list is empty")   # Prints when empty
            return
        
        itr = self.head
        llstr = ''   # to iterate

        while itr:
            llstr += str(itr.data) + ' --> '    # To show the process
            itr = itr.next
        print(llstr)

Now, to call it.

if __name__ == '__main__':
    ll = LinkedList()
    ll.insert_at_beginning(1)
    ll.insert_at_beginning(4)
    ll.insert_at_beginning(6)
    ll.print()

so, this prints out our values. so what does this result for now, if we call it? This:

1 --> 4 --> 6 -->

like that. So it shows you appended to the list. And if shows the --> to point out, how they are working inside. You could do many other methods. Like, maybe an insert_at_end. To insert from the end. like this.

def insert_at_end(self, data):
        if self.head is None:
            self.head = Node(data, None)
            return
        
        itr = self.head
        while itr.next:
            itr = itr.next

        itr.next = Node(data, None)

so what's happening there is, it takes the head value. The toppest value, and return the data of none. Then, it iterates through the head, and gives the next value. And then the next, next value. Which is the last.

Now to call it.

if _name_ == '_main_':
    ll = LinkedList()
    ll.insert_at_end(4)
    ll.insert_at_end(9)
    ll.insert_at_end(10)

like that. you probably know by one, what it will give. Now, just as a practice, i will tell you a method you should make. Try making a len() method using what you learnt.

That's basically it for linked lists. You can make more methods if you want.

Lists

Lists are actually called arrays in most languages. IT could also be an array in python, but is called a list instead.

So lists are basically a type of data type which organizes numbers, or any type of values. it orders them, and can be accessed using indexes, or looping through them.

Here's an example of a list, and getting indexes from it.

some_list = [1, 2, 3, 4, 5]
print(some_list[0])

all list indexes start from 0, then 1, then 2, and so on... They can be any value, like a str or an int like the example above. Lists are kind of an easy topic. nothing much to say.

lists are not a good option mostly to use. Since it's notation is O(1).

Just so you know, O(1) is really bad. if you have that, you might want to change it.

Like i said. Lists are not that good to use. You can use alternatives. But sometimes, they could be really useful. They are also common though.

here are some methods you could use for lists.

s = ["hi", "something", 'wow', 'wah']

s.append("more")
s.remove("more")
s.insert(2, "more")
s[1:3] = ["more somethings"]
s.sort()
print(s)

so you can append, remove, insert. takes two arguments. index, and value. changing with [:3] or indexing, and sorting. There are more though.

That's basically it for lists.

Dictionaries

dictionaries are yet another data structure, or data type, which is mostly useful for accessing values easily, and placing them properly. Let's look at a problem, which explains how it's useful.

So say you have to check stock prices. from separate months, or days, and you have values each specified to them. You have to loop over them to get the values. You could use a list here.

stock_prices = []
with open("stock_prices.txt", 'r') as f:
    for line in f:
        tokens = line.split(', ')
        day = tokens[0]
        price = float(tokens[1])
        stock_prices.append([day, price])

print(stock_prices)

and to acces values, you have to get the index, and loop, and all that junk. But what if we used a dictionary??

stock_prices = {}
with open("stock_prices.csv", 'r') as f:
    for line in f:
        tokens = line.split(', ')
        day = tokens[0]
        price = float(tokens[1])
        stock_prices[day] = price

print(stock_prices['march 9'])

as you see above, stock_prices = [], changed to stock_prices = {}. Now, when we print the dictionary, and we want to acces a specific price, or day, we can use [] to access it. Notice how easier it was made?

so now, like the linked lists, let's use classes to dig deeper into how some of the dictionary methods work.

class HashTable:
    def __init__(self):
        self.MAX = 100
        self.arr = [None for i in range(self.MAX)]

so starting of, we make a hastable class. Btw, hastables are dictionaries. just uses hastables in many languages. Python for some reason uses other names.

and we should make a get_hash method, to get all items, and arrange them in property.

def get_hash(self, key):
        h = 0
        for char in key:
            h += ord(char)
        return h % self.MAX

so that gets the h key, and assigns to what is is given using the ord keyword. And modules the max number of what it assigns.

now, we could make the add method, which adds values to it.

def add(self, key, val):
        h = self.get_hash(key)
        self.arr[h] = val

so what that is doing is, it's getting two parameters, key, and value. It's get's the key, and arranges the key to the value. easy right?

And we should now make a class to get the item. So we added it, now we should get it.

def get(self, key):
        h = self.get_hash(key)
        return self.arr[h]

so we are getting the hash key, and arranging it. same thing

Now, let's call it.

t = HashTable()
t.add('march 9', 130)
t.get('march 9', 130)

so once run, you see that it prints out in the same form as the dict methods we use. they are builtin. That's basically it. easy right?

Now, again, just for practice, make a del item. so if used del to something, it should delete it. try making that method using what you have learnt.

That's basically it on dictionaries.

Sets

Sets are another type of data structure that are used to multiple items in a single variable. Like instead of making a lot of vars like this.

var1 = "apple"
var2 = "banana"
var3 = "peach"

it can be all of them in one set. Which is surrounded by {}. Like this.

a_set = {'apple', 'banana', 'peach'}

like that. Easy right? But there are some rules for sets.

  • unordered

    • sets don't have a definite order. They can be in any randomized order. Nothing specific, like other data types, or structures.
  • unchangeable

    • You cannot change anything in sets. They are unchangeable. If it is printed in one way, no way you can change it. Try it, and a error is thrown at you.
  • duplicates

    • duplicates are ignored in sets. So if you put something apple and apple in the set, it ignores it, and prints out a normal list, removing the duplicates.
a_set = {'apple', 'banana', 'apple', 'peach'}

what does that result? This.

{'apple', 'banana', 'peach'}

Notice how the duplicate was completely ignored. That's one rule of the set data structure. Let's look at a few methods of the set data structure.

some are the add(), clear(), difference(), 'update()', union(), pop(), remove(), and etc. Let's see how they work.

  • add() this method adds a value to the set. If it already exists, it doesn't add it. refer to my duplicates part.

    Notice how the duplicate was completely ignored.

a_list = {'berries', 'banana', 'apple'}
a_list.add('grapes')
print(a_list)

prints them out properly.

  • clear() This method as the name suggests clears the set. Like if you ever want to wipe your set clean, use the clear() method.
a_list = {"apple", "banana", "cherry", "berries"}
a_list.clear()
print(a_list)

just prints an empty set.

  • difference() this method will show the difference between two sets. like say you have one set, and another, add the difference() to it, and it will show the difference in those values.
a = {"apple", "banana", "cherry"}
b = {"google", "microsoft", "apple"}
z = b.difference(a)
print(z)

prints the difference between them. in this case the values. So it prints them out.

  • update() this method basically adds one set's values into another set. so if you use it against one set, that set that had been used values will transfer into there where printed out.
x = {"apple", "banana", "cherry"}
y = {"google", "microsoft", "apple"}
x.update(y)
print(x)

so that prints out all values mashed up into one set. both sets are combined.

  • union() this method is kind of like the same to update(). but one difference is it combines all values from multiple sets to another. not just 2.
x = {"a", "b", "c"}
y = {"f", "d", "a"}
z = {"c", "d", "e"}
result = x.union(y, z)
print(result)

prints out all values in one set. z.

  • pop() this method removes the last value in a set, and prints it out, without that value.
a_list = {"apple", "banana", "cherry", "grapes"}
a_list.pop()
print(a_list)

prints out without grapes.

  • remove() this method removes a specified element from the set. like you just have to tell what method you want removed, and it removes it.
a_list = {"apple", "banana", "cherry", 'berries'}
a_list.remove("banana")     # specified bananas.
print(a_list)

prints out the set without banana.

There are way more methods used in sets than i just listed out. Search them up. But i just wanted to list some out. Try to make methods on your own using classes for a practice.

That's basically it for sets

Ending

Well, this is the end of the data structures made easy tutorial. It's been a lot. There are more data structures that i have explained in this tutorial, but i'm planning on covering more in another tutorial.

Here are some tutorials from where i have gotten some info from.

Practice more on what you have learnt today. Hope you learnt a lot from this tutorial.

You are viewing a single comment. View All
Bookie0 (6260)

@RYANTADIPARTHI yez, pretty nice article! :D