Linked List Part 1
Tags: dsalgo
Published: 2022-03-23 13:49:04

Lists are values that are non separated in memory and you can find them by index. 


In memory :

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4pkgj9gtl0hoz2ytyswu.png)

But Linked List is separated and linked to each other. You can find one find one node by the pointer.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/emabyusjocrb7bzkmfmo.png)

Thus 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/325v8nz71f98v8ayw4w5.png)

**_Big Oh(O)_**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/execnrlazhx1mu80ol3w.png)

**_Under the hood_**

First assume from this list, we will learn about node 4 and then 7:
when we talk about node 4:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/62vkbk6u4f6adcc34u08.png)
In code it is :

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qxsr5r1v8he9342aoc1q.png)

again, for node 7:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/urylae15lgf2hfv0u2gk.png)
Now need to work with the pointer sign. How to point to number 4?
Just have the block for number 4 within 7:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5aq8a8pohwz2c5fngaqa.png)


Thus what really happens is that:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tzg9e6qvvfbycilylzwn.png)

and in code:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/se364rk2gofmlypo937f.png)


**_Constructor_**
See how this code can be:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r03emgdq06t9uq6jzwai.png)

Here you can see that you need to create a node and thus we will create a class to create a node. So, creating class Node with a constructor __init__. This class will create value and next.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f49kbq7l43brmjox0fpb.png)

Now we can work with Linkedlist class:
We will create node by Node(value) and set it as head.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6rwjy13acpf6dc9wmih.png)
Also will set the tail to that node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pbvwag96195mmbn70pto.png)
Then keeping the count of length:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9lwe5k5y5jt7c37wnww1.png)
So, we have created our linked list constructor

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/78st8yq16no6r18f91um.png)
Now, calling a number 4 to creating a linked list:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p2290laucegr1vn0gn15.png)

this will create this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ab1tp7jjcq73myif34b7.png)



**_Print the Linked List_**

You can print the Linked list by this code under any class.
```
#method under a class
def print_list(self):
    temp=self.head
    while temp != None:
        print(temp.value)
        temp=temp.next
```

**_Appending_**
Appending something to the end of the list, we can first assume that we have a blank linked list and thus we need to have a value and make it both head and tail. 

As the list is blank and thus it there is nothing and thus tail and head are pointed to None.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tryj8521ylu6fhw4s0zn.png)
Now, we have to make it :

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1bz15qwh34uafmer9sxo.png)

Thus the code should be 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wj80dm798ypat7w7re7s.png)
If we already had a list that had 11,3,23,7 and need to have 4 to add to the end of the list, 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i5gf3h0r6c0v143mj39t.png)
We would have done this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/308s4wik0dcyykx0qn9y.png)

```
#Code for appending 
    def append(self,value):
         new_node=Node(value) #Node is a class
         if self.head is None: #case for empty linked List
             self.head=new_node #making the node head
             self.tail=new_node #making the node tail
         else: #case for already having a value
             self.tail.next=new_node 
             self.tail=new_node
         self.length+=1 
         return True #created for later use 

```
**_Pop a value_**
Now we are going to make a list from this

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ewcj6p8hwegv5wnw8za.png)
to this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r802eg2jy0ls4pwv3bea.png)

In code it will be something from this :

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rhf965qk393axoij133z.png)
to this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hk6cacr6ep9lifcd725j.png)
To solve this code, we are going to have pre and temp and point it to the first node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zmi0zn076gxjhla6g9ab.png)
now , we are going to iterate through the list and temp.next is not None then we are going to set pre=temp ;
Firstly,
temp=temp.next 


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/taymbmwmwor941near6d.png)

and then if temp.next is not None we will set temp=temp.next, then pre=temp 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6kaneeisiitnmiy6beyk.png)

we will just keep doing that till the point temp.next==None:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pqc84z1d1sp7o1byoew6.png)

Now we are going to set tail to pre:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8jc8hueqcew8bwzyjlaw.png)
and we will set tail.next to None to break the last node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oydv5ece6ccgsfiz2tkh.png)
Again, temp was set to the last node and thus we will return that node and we are done!
We have successfully popped the node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/co1g7a65bhwyebharlkh.png)

Let's code it:
Case_1:
assume that we have a empty list

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aeu1ie4s6ggqjw6xmqy2.png)

```
def pop(self):
    if self.length==0: #if the list is empty
        return None
```
Case_2:
For more or equal 2 contents, we will code:

```
while(temp.next): #this will pass if temp.next returns True or 
                  there is a node
     pre=temp
     temp=temp.next
```
This will turn this :

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/06eyeaap7mbiqczld5ow.png)
to this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uyxeaqiqx80y745ifjml.png)

This will work till this situation:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/68kzl27enhh46wjqbjpd.png)
Now we are going to set tail to pre:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mcvlxkl0aj69g3em1s3c.png)

Now we are going to remove the last node and thus set tail.next to None .

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ayvwf1wno94l4ntjips7.png)

Case_3:
When we have 1 node in the list:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/37w4xd9panqgc2i4annc.png)
Now after decrementing 1, we will set head and tail to None:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uesydr2wonwabhv1je3v.png)
Which turn things to:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oy8wtgnnw32ssy2ngc6w.png)

All Cases are solved, now we are going to return the temp. Thus the node will be popped.

```
#Code for popping
def pop(self):
    if self.length==0: #if the list is empty
        return None
    temp=self.head
    pre=self.head
    #for case having more than 2 nodes
    while(temp.next):
        pre=temp
        temp=temp.next
    self.tail=pre
    self.tail.next=None
    self.length=-1
    if self.length==0: #if the list had just one value , we will decrement the length and then set head and tail to None
        self.head=None
        self.tail=None  
    return temp

```