Tip:
Highlight text to annotate it
X
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 !