Linked Lists

Array : 
 
                                 
This given array is contiguous and Linear or in other ways it is sequential.

                                     
                           
This given Singly linked list is also linear .



                                     
This is non - linear because here element 1 is linked to two elements.

Linked List : It is linear but non - contiguous. In this, each element is actually a separate object while all objects are linked together by referenced field. There are two types of linked lists :
  • Singly Linked List
  • Doubly Linked List
Applications :
  • Image viewer
  • Previous and next page in web browser.
  • Music Player
  • DNA molecules etc...

In linked list we can't randomly access any element. It takes O(n) time on average to visit an element by index where n is length of the list.

Operations in Singly Linked List : 
  • Add Operation
  • Delete Operation
  • Search Operation
You can insert a new node or add a new node into the linked list by O(1) complexity. If we have to add node at beginning the steps performed can be :
  • Initialize new node
  • Link new node to our original head node where head node is the node present at the beginning of the linked list.
  •  Assign new node to head.

To delete a node find previous and next of the node you want to delete.
It is easy to find next node but for previous node we have to traverse from the head node. It takes complexity O(n). Always break the connection with the node first and then the next node otherwise we will lost the reference. If we want to remove head node, first we will change head by head = head.next and the follow the same procedure.

In a given linked list, if we want to determine whether it contains the cycle or not , it can be determined by two ways :
  • Hash table
  • Two - pointer Technique
Two pointer technique is more efficient than Hash.

Two - Pointer in Linked List : 
  • If there is no cycle, the fast pointer will stop at the end of the linked list.
  • If there will be a cycle in the linked list, it will catch up or stop along with the slow pointer.
  • Here, for optimal speed, fast pointer speed is twice the slow speed. 


Comments

Post a Comment

Popular posts from this blog

Model Evaluation and Selection

Image
Model Process :    In decision maker process, we follow f : x  → y and Real world process (RWP) tends to the population. After building a model, we need to know, how accurate the model is expected to be on population. For that, here comes the Confusion Matrix Here we are getting 88 out of 100 as correct, therefore the                        Accuracy = 88/100 = 0.88 we need to check whether the accuracy will be fine for model, for that we check Expected Accuracy.                                E[x] =  Σ x P(x)X                                h(x(vector)) = y (Actual) Goal to be achieved here is    h(x(vector)) = f(x(vector)) for each x belongs to population.   h(x(vector)) = y , E [ h(x(vector)) = f (x(vector)) ] for each x belongs...
Read more

Convolutional Neural Networks(Part-4)

Image
  AlexNet AlexNet is considered to be the first paper/ model which rose the interest in CNNs when it won the ImageNet challenge in 2012. AlexNet is a deep CNN trained on ImageNet and outperformed all the entries that year. It was a  major improvement  with the next best entry getting only 26.2% top 5 test error rate. Compared to modern architectures, a relatively simple layout was used in this paper. ZFNet ZFNet is a modified version of AlexNet which gives a better accuracy.  One major difference in the approaches was that ZFNet used 7x7 sized filters whereas AlexNet used 11x11 filters. The intuition behind this is that by using bigger filters we were losing a lot of pixel information, which we can retain by having smaller filter sizes in the earlier conv layers. The number of filters increase as we go deeper. This network also used ReLUs for their activation and trained using batch stochastic gradient descent. GoogLeNet The GoogLeNet architecture is very different f...
Read more

Introduction to Machine Learning(Part-4)

Image
Training Data is the subset of population, where population can be of n variables x 1 ,x 2 ,........,x n . Let us discuss it by example , assume we are taking to factors to differentiate individuals that is Eye color and Hair color. Eye color can be Blue,Green  and Brown. Hair color can be Black, red, blond and grey. So the total combinations we will be working be 3*4 = 12 Here, we can make prediction of function by Joint Probability Distribution.We assume that eye color and hair color does not tell us much about the individuals.Let us add an attribute Milk allergy which has binary values Yes(y) or No(N), now the combinations on which we can work will be 3*4*2 = 24. If we add an another attribute income which is continuous then the combinations to learn is  3*4*2* ∞ =  ∞. So , there are two ways by which we can learn this problem: Discretize / Bucket : In this we divide the attribute income in interval like: k maps to [1,100k] ,[100k,500k,.......] Probability Density Func...
Read more