LINKED LIST

'Linked List' is another commonly used Data Structure.

And the definition of 'Linked List' is in the name itself. You know what a 'List' is? A 'List' can be a List of students in a class.

Say, John, Pradeep, Andrew, Beck.

Now, when we connect or 'Link' this 'List' (Say the List of students). It becomes a 'Linked List'.

So, the next question would be,

Let us take an example to understand, how a Linked List is linked or connected.

Say, you are a fun loving teacher. And there are around 70 students in your class. Everyone is sitting according according to their roll number that is pasted on their seat.

Now, out of 70 students, you have figured out an interesting way to connect four of your favorite students. i.e. John, Pradeep, Andrew and Beck.

Let us see the way.

So, you would create a List of above four students and Link or Connect them in such a way that John would know where Pradeep is sitting, Pradeep would know where Andrew is sitting, Andrew would know where Beck is sitting and since, Beck is last in the List. She doesn't have to know where anyone else is sitting.

And as we have said,

The first name in the List is 'John' and 'John' knows the seat number of Pradeep i.e. 9. (By the way the seat number of 'John' is 3 that is not needed).

So, we go to seat number 9 and find 'Pradeep' there.

Similarly, 'Pradeep' has the number 12 with him. Which is Andrew's seat number. And we go to seat number 12 and find 'Andrew' there.

And, 'Andrew' has the number 63 with him. Which is Beck's seat number. And we go to seat number 12 and find 'Beck' there.

And 'Beck' is the last in the List. So, she has no number with her.

Now, is it clear, how a 'Linked List' is Linked or Connected.

Even if you consider a 'Linked List' from Computer Science perspective. Just consider the Seat numbers to be the memory locations.

And exactly that is how a 'Linked List' is organised in memory. All the data is scattered all around. i.e. The first item in the 'Linked List' knows about the second item, second item knows about the third and so on.

To understand how Insertion works in a 'Linked List', we will be taking two different scenarios.

And we will take the same example,

So, as we know, we already have the above 'Linked List'.

Now, let's say there is one more student 'Sameer' who sits on seat number 28.

Now, you need to insert 'Sameer' into the above 'Linked List', between 'Andrew' and 'Beck'.

And how would you do that ? You would start from 'John' as he is the first one in the 'Linked List', and 'John' would give you the seat number of 'Pradeep' i.e. 9.

Similarly, 'Pradeep' would give you the seat number of 'Andrew' i.e. 12.

Now, you are in Andrew's seat and all you have to do is, make Andrew point to the seat number of the new guy 'Sameer'. And make 'Sameer' point to the seat number of 'Beck'

And 'Sameer' is a part of the 'Linked List' now.

Now, let us look at the other scenario,

Where you already have the details of 'Andrew'. i.e. Who 'Andrew' is pointing to,

Now, you already know who 'Andrew' is pointing to. And you don't have to start all over from 'John' and traverse the entire 'Linked List'.

Rather just change the number where 'Andrew' is pointing to. Currently 'Andrew' is pointing to 62. Just change it to 28. i.e. The the seat number of 'Sameer'.

And 'Sameer' is a part of the 'Linked List'.

Just think ! In the above case, when you inserted 'Sameer'. You had to go through all the elements in the 'Linked List'. i.e. You Started with 'John' then from 'John' you went to 'Pradeep' until you have reached 'Andrew'.

So, in worst case you have to traverse the entire 'Linked List'. And if the 'Linked List' has n elements then,

Running time for Insertion in a Linked List : O(n)

Now, let us look at the other scenario where you wanted to insert 'Sameer' after Andrew and you already have the details of 'Andrew'. i.e. Who 'Andrew' is pointing to,

So, in this case you don't have to go through the entire 'Linked List'. Instead you can just make 'Andrew' point to 'Sameer' and make 'Sameer' point to 'Beck'.

In this manner you can insert 'Sameer' in O(1) time.

Running time for Insertion in a Linked List when there is a known Node : O(1)

To understand deletion from 'Linked List', let us take the same example.

Let us say we want to remove the new guy 'Sameer' from the 'Linked List'.

And as usual you have to start from 'John' then goto 'Pradeep' from 'John' then to 'Andrew' and finally reach 'Sameer'.

Now, to remove 'Sameer', all you need to do is, check to whose seat 'Sameer' is pointing to?

'Sameer' is pointing to seat number 62. And you need to take the number 62 and make 'Andrew' point to 62.

Now, 'Sameer' is out of the 'Linked List' as 'Andrew' is pointing to 62 now.

Just think ! In the above case, when you removed 'Sameer' from the 'Linked List'. You had to go through all the elements in the 'Linked List'. i.e. You Started with 'John' then from 'John' you went to 'Pradeep' until you have reached 'Sameer'.

So, in worst case you have to traverse the entire 'Linked List'. And if the 'Linked List' has 'n' elements then,

Running time for Deletion in a Linked List is O(n).