Linkedlist is one of the most complex data structure which is difficult to understand for new programmers as well as professionals. So, In this article by a trainer from python institute in Delhi, you will learn about linkedlist in detail
We’ve all heard of data structures in python, and linked lists are among the most important data structures for both interviews and your coding journey. We will go through various operations on the linked list and the Big O complexities as well. Before we get into the liked list, we need to look into array because there are some issues with arrays that linked list try to solve.
Let us say, we have an array of stock prices and have a memory layout of these stock prices as shown.
Array in Python and its disadvantages
Basically, there are like five elements in this array. If you want to insert an element 284 at location number 1 then it will insert 284 at location number 1 and will swap all the other elements. It will copy 305 from location 1 to 2, 320 from 2 to 3 and so on. In this way, the array insertion complexity is order of n.
When you create an empty list in Python, Internally in the memory it will allocate some capacity for that list.
It is allocating a capacity of five elements and when you start inserting elements one by one, it will put those values in. Now at this stage when you have three elements and you want to insert 284 at location number 1, what really happens is, firstly it will swap the value at that place to make a space for 284. Here, you can see that there are 2 copy operations while doing this.
Imagine doing same with million elements in your array. You will have to do million swaps. Once it has a space for 284, it will insert it on the desired location.
There is another scenario where your array is full of capacity. Let’s say we have populated all 5 elements in my list and now we want to insert 284 at location 1.
These are memory locations what are already filled and the one which are grayed out those are allocated to a different program or some different variable in the same program. The location after 292 cannot be used.
Hence, it will go into some different area of memory which is a RAM and it will allocate more capacity and then it will copy all these elements one by one.
The Way dynamic array works in this situation is if the initial capacity is 5 then it will allocate Additional 5 x 2 memory locations and will copy all these elements along with 284 to a new memory location. Here, the overhead is not only swapping the elements but also allocating new memory as well as copying all elements to new memory area.
As we can conclude here that Arrays are not that efficient to use.
What is linked list?
Imagine having a data structure like this.
Here, the individual values are stored in two different areas of memory. Array store the value in contiguous memory location whereas linked list is a type of data structure which stores values at random memory locations, but those are linked by these pointers. First element has a referenced to the address of my next element. What we mean to say is next (second) element 305 is stored at the location 00A1 and the first element stores the reference (address) of second element.
We are creating links here and through these links we can access the next element.
In this type of data structure say linked list, when you want to insert an element (284) at location number one, it becomes very easy for you all. What you all need to do is modifying the links of the nodes. We do not have to copy the values from one place to another place.
All we will do is Change the address of this link to C702 because that’s address of 284. Previously, it was 00A1. So, this insertion operation becomes extremely easy in this data structure.
- When you want to insert element at the beginning, the complexity is order of 1 that is constant.
Because all you are doing is creating a new node and then modify the link.
- Similarly, if you want to delete the element from the beginning, time complexity will be order of 1.
- But, if you want to insert or delete the element at the end or in the middle of the link list, the complexity is order of “n” because you have to iterate through all the elements of the list.
This data structure is called linked list.
Main benefits of linkelist over an array
- First, you don’t need to pre allocate the space. As you saw in the previous example that we have to allocate a Capacity of 5 even before we have populated any element. In linked list, you can allocate whatever is needed.
- Seond biggest benefit is insertion/deletion is easier than arrays.
Time complexities of different operations in linkedlist
- If you want to traverse a linked list, you have to go through element one by one hence the complexity or Big O complexity of traversal is order of n.
- Accessing element by value is also order of n.
- Inserting element in the middle is order of “n” in both array and linked list.
Double linked list
There is another flavor of linked list called doubly linked list. Here, you don’t only have a link to your next element but you have a link to your previous element as well.
Here, you can see that, this particular node through your file has a reference to next element 00C5 but also has address of previous element 00500. If you want to do backward traversing in doubly linked list, it is possible.
For example: let’s say you have 292 and you want to traverse the link in a reverse direction. With doubly linked list, it becomes very easy.
Implementation of linked list in python:
Now, let’s implement linked list in Python. We have opened pycharm and we have created two classes here.
- The first class is a node class which represents an individual element in the linked list. It has two class members. One is data and the second one is next which is known to be a pointer to next element. Data can contain integer’s numbers or complex objects.
- The second class is a linked list class where you need a head variable which points to the head of the linked list.
How to implement a linked list?
Creating a linkedlist requires defining a class for the nodes of the list and another class for the linked list itself.
We’ve simply created a class called “linked list node” and we’ve set up a constructor that takes in a value and automatically assigns the next to none. All we have to do here is set “self.value= value” and “self.nextNode=nextNode” and we’re setting this value to none in our parameters.
Let’s say we want to make a linkedlist that looks something “3 that points to 7 which then points to 10.” Well, we can create your desired nodes by following code.
We just have three different nodes that aren’t connected to each other at this point.
The next thing to do is simply connect them together. For this, we can say “node1.nextnode node2” and this creates the relationship of “node 1 points to node 2.” Repeat the process for next node.
To test it out, we can write very basic code shown below and going to create a while loop.
Inserting a new node at beginning
First we are going to implement a method called insert at beginning. What actually this method is going to do is taking data value and inserting that at the beginning of the linked list. Let’s say now you can create a new node with value data and then the next element for that node. So you can see that the Second argument in this constructor of Node class is a pointer to the next element.
Now, you already have a head and if you’re inserting anything in front of it, what’s going to happen is: you will create a node element and the next value of that node will be your current head and once that node is created you can say that my head now is new node.
Function to insert a node at the beginning:
So we will test this method out but for testing this we need one utility function called print.
This is how we are going to print our linked list.
OUTPUT:
Inserting a new node at the ending of the linked list:
To insert a node at the end of the linked list, we can to insert it directly. We have to traverse the complete linked list to reach at the end of the link list. Time complexity for the insertion at the end operation in linked list is big O of n.
Try to run this code to “insert a new node” at the end of the linked list.
Circular linked list
A circular linked list is a type of linked list in which the end node points back to the initial node, resulting in a circle or loop. In other words, in a circular linked list, the “next” pointer of the last node points back to the first node in the list rather than to none, as it would in a standard linked list.
There are not kind of wide variations in implementation of double linked list and circular linked list. Try doing the over operations on both of these and grab some more understanding of codes.
If you are writing these codes for the very first time, it might feel hard to you. But, don’t give up, you can learn about it and become a pro within few months. Join the python course in Delhi or learn python online now