Linked List in Python (Theory + Code Implementation)

Linked List in Python (Theory + Code Implementation)


In this section, we will learn about the linked
list data structure, which is a basic but very very important data structure and most
of the questions in technical interviews are based on linked lists. So it is very important that you understand
this concept properly and are able to write the code on your own. OK. So now let’s start. We have seen the List abstract data type in
the previous section. It can be easily implemented using arrays,
in Python we have the list data type which is an array based sequence, so we can easily
implement this List Abstract Data Type using the Python list. Another way to implement List ADT is by using
linked list data structure.In a linked list, data is not stored in contiguous memory locations. This is an example of data stored in an array
based sequence and this is an example of the same data stored in a linked list. This data is stored in contiguous memory locations
while this data is scattered here and there in the memory. Here the list items are stored in sequential
locations, so the relative positioning of list items is implicitly maintained. We know that this is the first item, this
is second and so on. In a linked list, the items are not stored
in sequential locations, so the relative positioning of the list items is maintained with the help
of links. A link is a reference to the next item of
the list. so we have these links here, each link refers
to the next item. So with each list item, a reference to the
next item is stored.The list item together with the link is called a node. So these all are nodes, these nodes are the
basic building blocks of a linked list. The nodes are connected together by links
and they collectively represent the linear order of the list. So this first node contains the first list
item and reference to second node, this node contains the second list item
and reference to the third node and so on. We just have to know where the first node
is, all other nodes can be found by successively following the links. From first we can go to second and from second
we can go to third and so on. So while implementing a linked list we maintain
a reference to only first node of the list, and with the help of this reference only we
can access all the elements of the linked list. We will call this reference start. So what is a linked list. It is a dynamic data structure that is made
up of nodes arranged in sequential form. Dynamic data structure means that we can allocate
the required memory while the program is running. A dynamic data structure can expand or shrink
easily during runtime. So a linked list does not have a predetermined
fixed size, it does not reserve any extra space in advance. It allocates memory for the next item as and
when it needs it. In the case of array based sequences, the
size of the array might be more than the actual number of elements that are stored in it,
resulting in wastage of space. For array based sequences we need large chunk
of contiguous memory, if many elements are to be stored, While in the case of linked
list there is a distributed representation of elements, elements are not stored in contiguous
locations, so many items can be easily stored even if contiguous memory is not available. And compared to arrays, insertion and deletion
of elements is easier in linked lists as there is no need to reallocate or reorganize the
whole list structure. In arrays, insertion and deletion is expensive,
since it involves shifting of elements while in linked lists there is no physical movement
of data while inserting or deleting elements. We can use linked lists to implement abstract
data types like lists, stacks or queues. Now let’s see two disadvantages of linked
lists. First one is that efficient random access
is not possible, means we cannot access elements of linked lists by using a numeric index. and the second one is that some extra memory
is required for their implementation. This extra memory is due to the link that
is stored with each item. There are different variants of linked lists. In this course we will study about these five
variants out of which the single linked list is the simplest one, so we will start with
single linked lists. A single linked list is made up of nodes where
each node has two parts, the info part and the link part. The info part contains the list item, the
actual data that has to be stored in the list and this link part is a reference to the next
node of the list. This is an example of a single linked list
with six nodes. The info part contains an integer value, this
can be of any other type also. We maintain a special reference variable that
always refers to the first node of the list, and have named it start. This reference is the identity of the
list and with the help of this reference only we can access all the elements of the list. We have to use the link value from each node
to go to the next node. We start at the first node and we can move
from one node to the other by following each node’s link. So if we just know this reference start we
can go to any node of the list. In python we have a special reference value
called None, so if the link part of a node is None it means there is no next node. No next node means end of the list. In this presentation we will denote a link
that is referring to None by using this shaded box. So we use None to denote the end of the linked
structure. This is the last node so its link part is
None. For an empty linked list, this reference start
will be None. Now let’s see how we can implement a single
linked list in Python. This is the class Node that represents a node
of a single linked list. This attribute info represents the actual
data that has to be stored in the list. This attribute link will refer to the next
node. In this init method, info is initialized with
this argument value and link is initialized to None. So whenever we create a new Node instance,
info will be initialized to the value that will be sent as argument and link will be
None. Now this is our SingleLinkedList class. This attribute start refers to the first node
of the linked list. So each SinglleLinkedList instance will maintain
a single reference to the first node of the list. In this init method, we have initialized start
to this special reference None. We can see that the list class itself does
not contain any node objects, it only contains a single reference to first node of the linked
list.In the next few lectures we will develop all the methods of this SingleLinkedList class. So right now you make a new python file and
write this Node class and SingleLinkedList class. As you proceed through the lectures you can
replace these pass statements with the real code. So first we have the init method, then this
method display_list that will display the elements of the list, then this method count_nodes
that will count the number of nodes in the list. This method will search for a value in the
list, this method will insert a new node in beginning of the list, this will insert a
new node at the end of the list, this one creates a list. This method will insert a new node after a given
node, this method will insert a new node before a given node, and this one will insert a new node
at a given position, this one will delete any given node, this one will
delete the first node of the list and this one will delete the last node of the list. This method will reverse the list. These 2 methods will sort the list using bubble
sort, this one by exchanging data and this one by exchanging links. These methods are for inserting, detecting
and removing cycle from a linked list. These 2 methods are for merging lists, and
these methods are for sorting the list using merge sort. Now this is the end of SingleLinkedList class. Here we have created a new SingleLinkedList
instance object. Currently there are no items in this list
because in the constructor we have initialized start with None. With the help of this method create_list we
will create a single linked list and then inside this while loop we will perform various
operations on the list with the help of all the methods of the SingleLinkedList class. In this while loop, first we are displaying
all the options and then depending on the choice entered, we call a particular method of the SingleLinkedList class If 1 is entered we call display_list(), if
2 is entered we will call count_nodes method .We have options till 18, in 19th option we
break the loop. So this is the code that tests all the methods
of our SingleLinkedList class. In the next few lectures we will develop and
test all these methods of the SingleLinkedList class. So before watching the next video, please
make this python file. After every lecture you will be able to code
2 or 3 methods on your own. In this video, we will see how to traverse
a linked list. Traversal means visiting each node exactly
once, so we will start from the first node and visit each node till the last node. Before studying traversal, let us first see
how we can move a reference forward in a linked list. Suppose we have a reference p that refers
to this node, this is p.link, it refers to this node. Now if we assign p.link to p then p will start
referring to this node. So writing this statement p equal to p.link
makes p refer to the next node of the linked list, or we can say that p has moved one node
forward in the list. This is the statement that we will repeatedly
use to traverse our list. Ok now let’s see how we can traverse our linked
list. We have to start from the first node, so we
will take a reference p that refers to the first node. To make p refer to the first node we will
initialize it with start because start refers to the first node. Now while visiting each node we will print
the contents of the node. p refers to this node, so p.info is 10, so 10 will be printed. Next we write p=p.link, so now p will refer to
this node. Now when we print p.info 20 will be printed because info of this node is 20 now again we write p=p.link, p refers to
this node now and now p.info is 30 so 30 will be printed. Agian we write p=p.link so p now refers to
this node, and when we write this statement 40 will be printed. Again we write p=p.link, p now refers to this
node, now when we print p.info 50 will be printed. Again we write p=p.link, now this time p will become None so we have reached the end of the list and we can stop. So we have traversed the whole list and printed
the list items. We can see that we are repeating the same
statements again and again, so we can write this in a loop and the terminating condition
for that loop would be when p becomes None. So this is the loop for traversing a linked
list. We take a reference p and initialize it with
start and this loop continues till p is not None. When p becomes None, this loop will terminate. In each iteration, we are printing the value
of p.info and we are moving p forward by assigning p.link to p. So this is how we can traverse a list starting
from the first node till the last node. We can use the same loop to count the number
of nodes in the list. Here we have taken a variable n and initialized
it to 0 and whenever we visit a node we increment the value of n. So when this loop terminates the value of
n will give us the number of nodes in the list. Similarly we can use this loop to search
for an element in the list. Now let us go to our program and see the
methods for displaying a list, counting number of nodes and searching for an element in the
list. So we’ll see the code for these 3 methods,
display_list, count_nodes and search. This method display_list displays all the
elements of the list. If start is None, it means that the list is
empty, in that case we will just print this message and return otherwise we will display
all the elements of the list starting from the first element till the last element. We have already seen how this loop works. This method count_nodes displays the number
of nodes in the list. If you want you can return the value of n
from this method. This method search will return true if the
element x is present in the list otherwise it will return false. Let’s see how this method works. We have taken this variable position and initialized
it to 1, we will increment it each time we visit a node. This reference p is initialized with start,
and this is the same loop that we have seen in these 2 methods. So we are actually visiting each node staritng
from the first node. This statement p=p.link makes p move forward. Whenever we visit a node, we check info of
that node and if info of that node is equal to x, then we return True from this method
indicating that x is present in the list, and before returning we print this message
that displays the position of x in the list. If p becomes None, it means that we have reached
the end of the list and x was not found. So in that case control will come here and
we will print this message and return False. Now let’s see the method calls, we have called
these 3 methods in options 1, 2 and 3. So if we select option 1, the list will be
displayed, if we select option 2, the number of nodes in the list will be displayed, and
if we choose option 3 we can search for an element in the list. Now let’s try to run this program. First we choose option 1, it is displaying
that the list is empty, Next we choose option2, it is displaying that the number of nodes in the list is 0. Next we choose option 3, we search for an element, it is saying that the 45 is not found in the list. Since our list is empty, whatever element
we search it will say that it is not found in the list. We choose option 19, and exit. Here we had created a new SingleLinkedList instance
, and in the __init__ method we have initialized start to None, so the linked list that we
have created is actually empty. After that we have called this method create_list,
that will actually insert some nodes in the list. But we have not written the code for it yet. So that’s why when we came here the list empty
only. In the next next few videos we will see how
to insert new nodes in our list, and we will see the code for this create_list method. So right now your task is to write the code
for these 3 methods display_list(), count_nodes() and search(). So see you in the next video. Before studying insertion and deletion operations
in a linked list, let’s see how we can move in a linked list and find references to particular
nodes. In this video, we will see how to find reference
to the last node of the list, reference to second last node of the list, reference to a node with particular info, reference to predecessor of a node with particular info and reference
to a node at a particular position. First let’s see how we can find reference
to the last node of the list. This is the last node so we need a reference
to this node. This is the code that will give us the reference
to the last node of the list. We start at the first node by initializing
this p with reference start, and this statement p=p.link moves the reference p one node forward. While traversing the list we had seen that
the loop condition was p is not None, so there the loop stopped when p became None. Now here the loop condition is p.link is not
None, so here the loop stops when p.link becomes None and p.link becomes None when p refers
to the last node of the list, link part of last node is None. So when this loop stops p will refer to the
last node of the list. So this is how we can find reference to the
last node of the list. Now let’s see how we can find reference to
the second last node of the list. This is the second last node so we need a
reference to this node. This is the code that will give us the reference
to the second last node. Now here the loop condition is p.link.link
is not None, so this loop will terminate when p.link.link becomes equal to None. And p.link.link will become equal to None
when p will refer to the second last node of the list because when p refers to the second
last node of the list, p.link will refer to this last node and p.link.link will be None. So when this loop stops p will refer to the
second last node of the list. Now we will see how we can find reference
to a node with particular info. Suppose we are given this value x and we have
to find reference to a node that contains this value x. If the value of x is 30 then in this list
we have to find reference to this node. This is the code that will give us reference
to the node that contains value x. This loop stops when p refers to the node
that contains x and if x is not present in the list then p will become None. Now we will see how we can find reference
to predecessor of a node with particular info. Suppose we are given this value x and we have
to find reference to predecessor of the node that contains x. If the value is 30, then in this list we have
to find reference to this node because this is the node that contains 30 and this is the
predecessor of this node. This is the code that gives us reference to
predecessor of the node that contains x. Here inside the loop we are checking p.link.info
instead of p.info and the loop condition here is p.link is not None. So this loop stops when p refers to the last
node because when p refers to the last node we do not want these statements to work. Now let’s see how this code works. Initially p refers to the first node of the
list. Now p.link is not equal to None so we check
p.link.info, p.link.info is 20, it is not equal to x, so this break is not executed and p
is moved forward. Now again we check p.link, p.link is not None, now we check p.link.info, p.link.info is 30, it is equal to x, so now this
break statement is executed and this loop terminates. So we can see when this loop terminates, p
refers to the node that is the predecessor of the node that contains value x. Now let’s see how we can find reference to
a node at a particular position. These are the positions of the nodes in this
list. Suppose we are given a value k and we have
to find reference to a node that is at kth position in the list. So if the value of k is 3 then in this list
we have to find reference to this node. This is the code that will give us the reference
to the kth node of the list. Let’s see how this code works. Initially p refers to the first node and i is equal to 1. Now i

17 thoughts to “Linked List in Python (Theory + Code Implementation)”

  1. Iam staying in bangalore I need all fo ur coaching vedeos I can pay for but I need offline vedeos because I cannot attend the course

  2. Hi. Write in comments what more you want to learn. We will be happy to provide more on Data Structures and Algorithms, Advanced Programming, Object
    Oriented Design.

  3. Please let me know how to access the course contents. I have paid Rs 640 now I could not find the contents link on udemy

  4. She was explained fully and detailed
    She explained all operations
    I'll refer this video to my friend
    Finally nice video found

    I hope u will add some topics based on graph algorithms and AVL in Udemy

  5. Want to learn Python from a wonderful python course

    Enroll here – https://www.udemy.com/course/python-programming-in-depth/?couponCode=YOUTUBE10

  6. Love this tutorial , in linked list my all concept clear,โค๐Ÿ˜˜ese hi python ke sorting algorithms ke video bnado please๐Ÿ˜ซ๐Ÿ™๐Ÿ™๐Ÿ’“๐Ÿ˜ซ๐Ÿ™๐Ÿ™๐Ÿ’“

  7. first of all very very thanks for such explaining….
    Am confused in one statement plz clear that to me…………At 26:45
    temp.link = self.start

    self.start = temp
    first you tell that first node is start but when link a new node to start(head) say it's a start instead of first node
    plz reply

Leave a Reply

Your email address will not be published. Required fields are marked *