Linked List Part 1

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

In memory :

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

Thus

Big Oh(O)

Under the hood

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

In code it is :

again, for node 7:

Now need to work with the pointer sign. How to point to number 4?
Just have the block for number 4 within 7:

Thus what really happens is that:

and in code:

Constructor
See how this code can be:

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.

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

Also will set the tail to that node

Then keeping the count of length:

So, we have created our linked list constructor

Now, calling a number 4 to creating a linked list:

this will create this:

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.

Now, we have to make it :

Thus the code should be

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,

We would have done this:

#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

to this:

In code it will be something from this :

to this:

To solve this code, we are going to have pre and temp and point it to the first node

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

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

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

Now we are going to set tail to pre:

and we will set tail.next to None to break the last node

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

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

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 :

to this:

This will work till this situation:

Now we are going to set tail to pre:

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

Case_3:
When we have 1 node in the list:

Now after decrementing 1, we will set head and tail to None:

Which turn things to:

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