Data structures: Introduction to Doubly Linked List

Hello everyone ! In our lessons in this series so far, we have discussed linked list quite a bit. We.


Hello everyone ! In our lessons in this series
so far, we have discussed linked list quite a bit. We have seen how we can create a linked
list and how we can perform various operations with linked list. Linked lists as we know
are collections of entities that we call Nodes. So far, in all our implementations, we have
created linked list in which each Node would contain two fields – one to store data and
another to store address of the next node. Lets say we have a linked list of integers
here. So, I’ll fill in some values in data field of each Node. Lets assume that these
Nodes are at addresses 200, 250 and 350 respectively. I’ll also fill in the address field in each
Node. The address field in first Node will be the address of second node which is 250.
The address field in second node will be address of third node which is 350 and address part
in third Node will be 0 or Null. The identity of a linked list that we always keep with
us is the address of head Node or reference to head Node. Lets say we have a variable
named head only to store the address of head node. Remember this variable named head is
only a pointer to the head Node. Ideally, we should have named this something like head
pointer. its only pointing to the head Node, its not the head Node itself. head Node is
this guy. The first node in the linked list. Ok, so right now, in the linked list that
we are showing here each node has only one link, a link to the next Node. In a real program,
Node for the linked list that I am showing here will be defined like this. This is how
we have defined Node so far in all our lessons. We have two fields here – one of type integer
to store data and another of type pointer to Node – struct Node asterisk. I am calling
this field next. When we say linked list, by default we mean such a list that we can
also call singly linked list. What we have here is a singly linked list. What we want
to talk about in this lesson is idea of a doubly linked list. The idea of a doubly linked
list is really simple. In a doubly linked list, each Node would have two links – one
to the next Node and another to the previous Node. Programatically, this is how we will
define Node for a doubly linked list in C or C++. I have one more field here which once
again is a pointer to Node. So, I can store address of a Node. i can point to another
Node using this field and this field will be used to store the address of the previous
Node. In a logical representation, I will draw my Node like this now. I have one field
to store data, one to store address of previous Node and one to store address of next Node.
Lets say I want to create a doubly linked list of integers. I have created 3 Nodes here.
Lets say these nodes at addresses 400, 600 and 800 respectively. I’ll fill in some data.
lets say the cell in the middle in each Node is to store data. The rightmost cell is lets
say to store the address of the next Node. So, for first Node this field will be 600
which means we have a link like this. For second Node, this field will be 800. For third
Node, this field will be zero. For first Node, there is no previous Node, so this leftmost
cell which is supposed to contain the address of the previous Node will be zero or NULL.
The previous Node for second Node will be 400 and the previous Node for the third Node
is the Node at address 600. And of course we will have a variable to store the address
of the head Node. Ok, so what we have here is a doubly linked list of integers with 3
Nodes. Ok, so with this much, you already know doubly linked list. If you have ever
implemented a singly linked list then it should not be very difficult implementing a doubly
linked list. One obvious question would be, why would we ever want to create a doubly
linked list. What are the advantages or use cases of doubly linked list. First advantage
is that now if we have pointer to any Node, then we can do a forward as well as reverse
look-up. With just one pointer, we can look at the current Node , the next Node as well
as the previous Node. I am showing a pointer named temp here. If temp is a pointer pointing
to a Node, then temp->next is a pointer pointing to the next Node. Its the address of the next
Node and temp->prev or rather temp arrow previous , this is actually a syntactical sugar for
asterisk temp dot prev. So, this guy temp->prev is previous Node Or in pure words, pointer
to previous Node. The value stored in temp for this example right now is 600. temp->next
is 800 and temp->prev is 400. In a singly linked list, there is no way you can look
at the previous Node with just one pointer. you will have to use an extra pointer to keep
track of the previous Node. In a lot of scenarios, the ability to look at the previous Node makes
our life easier. Even implementation of some of the operations like deletion becomes a
lot easier. In a singly linked list, to delete a Node, you would need two pointer – one to
the Node to be deleted and one to the previous Node. but in a doubly linked list, we can
do so using only one pointer, a pointer to the Node to be deleted. All in all this ability
that we can do a reverse look-up in the linked list is really useful. We can flow through
the linked list in both directions. Disadvantage of doubly linked list is that we are having
to use extra memory for pointer to previous Node. For a linked list of integers, lets
say integer takes 4 bytes in a typical architecture and pointer also takes 4 bytes, pointer variable
also takes 4 bytes, then in a singly linked list, each Node will be 8 bytes – 4 for data
and 4 for link to the next Node. In a doubly linked list, each Node will be 12 bytes. We
will take 4 bytes for data and 8 bytes for link. For a linked list of integers, we will
take twice for links than data. With a doubly linked list, we also need to be more careful
while resetting links, while inserting or deleting, we need to reset couple of more
links than a singly linked list and so we are more prone to errors. We will implement
doubly linked list in a C program in next lesson. We will write basic basic operations
like traversal, insertion and deletion. This is it for this lesson. Thanks for watching
!

53 thoughts on “Data structures: Introduction to Doubly Linked List”

  1. hi, you had mentioned that to delete in single linked list, we need two pointers. I agree that is true. But one pointer is also enough for single linked list something like temp->next = temp->next->next;

  2. These videos are very impressive as it helps in quick brush-up rather than going to the text books. Really appreciate the effort which went in.

  3. Best videos online! I will share it to my Computer Science department as well to let them know about this videos. 🙂

  4. thank you a lot for this awesome tutorials. I had difficulties understanding when reading books but this video has just helped me understand the whole thing

  5. great explanation soo far but how about the people who want to learn Data structure algorithm in java.I am sure the concept would be the same and obviously the implementation would be different.So we wanna videos of data structure for java too.Thanks We need feedback

  6. sir your explanation is very good but your subtitles are hiding the code… please have a look on it

  7. This is by far the best lectures i have been through . I really appreciate the hardwork .Do you also have videos in OOPs concept with C++ /C #.

  8. perfect I really understand clearly the concept ur explanation is perfect
    could you show us how to do implementation on Java please?

  9. YOU ARE AMAZING!!!!!!!!!…. but can u tell me from which book have you studied the data structure and how can we improve it more ?????

  10. I'm trying to implement such a list (Double Linked List) in Java using an Abstract class (where the data value of each node can be any data type). Anyway its so painful and I'm quit disappointed I cant do it

  11. Buddy , u are explaining everything but at the same time u are putting the subtitles ,the page where u are explaining ,so it was very hard to understand because of your subtitles

  12. 5:40 I don't know if you mean it only for C, but I'm learning java atm. Is this the case in java as well? For a singly linked list, can you not just point the node before the one you want to delete to the node after the node you want to delete, then it is garbage collected?

    This is a question btw, if it's not clear xD

  13. jumps to wadsworth constant (presses three)
    "that was the single linked list. What we want to talk about is double linked list."
    WHOAAAA MAGICCC

  14. Get More Data Structure Program by Download this App
    https://play.google.com/store/apps/details?id=com.data_structure.user.datastructureandalgorithmusingc

Leave a Reply

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