Double Linked List in Data Structures and Algorithms | Part-1 | by Mr. Srinivas

hi everyone welcome to nourish technologies this is famous so in this session we are going to discuss about a double linkedlist operations in a data structures and algorithms right in our previous sessions so already we discussed how to perform all the operations on a single linkedlist so now so this is about a double linkedlist double linkedlist right so what are the advantages read our single linkedlist in a double linkedlist the main advantage of a double linkedlist right over a single linkedlist is here suppose in a single linkedlist single linkedlist always we can send the control in a forward direction only in a forward direction right we cannot traverse or we cannot travel in a backward direction we cannot display the elements from last to first that is a problem we cannot reverse and we cannot move right but here it is in a double linkedlist either you can move in a forward direction or you can move in a backward direction that is double linkedlist right two way direction in a forward direction you can move and in a backward direction also you can process the information so that is the difference between the main difference between single linkedlist and double linkedlist so how the node structure will be suppose write in a single linkedlist so node is nothing but write a structure data type in double linkedlist also if you want to create a node here it is struct data type only we need to take struct node so but how many fields are present how many fields write in a double linkedlist the node is having three fields the node is having three fields is a data feed the is left link field left link and this is right link field now two pointers to pointers this one is pointing to the previous node and this one is pointing to the next node so this is a node structure this is node structure so here it is in the struct node definition we have to define three variables so first one is a data type in teaser it is a data second one is a pointer pointer of type word just like in a single linkedlist only is a struct node type because so one node is pointing to another node and next one more pointer struct node star right struct node star right so this is a simple structure right node structure and next how the completely the single linkedlist data structure will be right just a format how all the nodes are connected and how root node is connected to I mean root pointer is connected to first node and all okay so first of all we need to declare a global variable pointer type so that is a root variable and initially what is its value null value first we have to declare a variable we have to declare a variable it is a pointer variable and the default value is a null nothing but initially it is not pointing to any node that is nothing but list is empty completely list is empty okay and how the node structure will be right nothing but the format of a double linked list will be see see just a node construction so initially so root variable is pointing to null pointing to null because known words in the list so if you create a node first node here it is node will be created node any data you can place suppose this is data and there is no left link why there is an left side no more nodes because it is the first node so here it is first node left link will be null first node first node left link left link is a null value null value and next so what is it right side link that is that will be connected to another node and here it is that node will be created at a particular memory location for example 2 0 4 6 that we are storing into root so it start pointing to the first node it start pointing to first node next 1 second node we are creating 20 suppose here it is a Phi 0 4 8 Phi 0 4 8 and this is the first node next node next link is pointing to this one right side this is Phi 0 4 a so this is the connection one way connection but serveware is a two way connection simple this 2 0 4 6 previous node address we are storing here 2 0 4 6 so that it is connecting to the previous node and next if you take one more node one more node suppose 30 at some location 7 double 0 2 so that will be stored here 7 double 0 2 and next to previous node address Phi 0 4 it will be stored here so 3 nodes are there in the list and there is no fourth node so last node right link also null last node right length is also null first node left link is a null last node right link is a null because first node is not connected to any preview is node and last node is not having and the next node so that is so this is simply how the data will be stored in a double linked list okay now first we will see how to append right a node to the double linked list so how to append a node to the double linked list so that is the first operation we are performing on a double linked list here it is so function name we are writing void append wide append so global variable to the structure node structure already that we have created globally so root get memory allocation at some location at some location and what is the initial value is a null value initial value is a null value so inside we need to declare one temporary variable struct node star temp variable because we know all the operations on the linkedlist right so we need to perform with the help of a temp variable only temp variable so first we are allocating the memory using malloc function we know this using ml up and what we have to pass the sizeof struct node we need to pass sizeof struct node we need to pass then what ml of function will do means it will create a node it will create a node at a particular location location a temporarily that we are collecting into temp variable only local variable and typecasting is required so that is struct node star struct node star malloc sizeof a struct node so that value we are collecting in to temper so temporarily the value we are collecting into variable temp variable temp variable so temporarily it is pointing to the newly created node next we need to read the data into the node now sir which is the data field sir that we do not know right so because maybe first one is the data field second one is the link field and third one is also link field so that is why in this node every field address is important every field address is important just consider this is a data field so data field address you should provide temp to data address so this location right for reading so here it is we are asking printf enter node data enter node data so that we are scanning scanf percent is d temp is pointing to that node location is a data location and that location address we need to provide address suppose if you give the value 10 the 10 will be stored here 10 next in this link we have to place null and in this link we have to press null left and right pointer variables we have given so here here it is temp to temp 2 left equals to null and next one temp to write equals to null so now node is ready here it is left side is a null value and right side is also null value left side is null and writes additional now node created completely now sir where we have to connect so first we have to check list is already having some ones are not if list is already having some of the nodes then we should add the created node at the end of that existing list or else so we need to connect to the first node that is nothing but a root element only if it is the first node how can we check sir very simple suppose if root equals to null that is nothing but root variable is not pointing root variable is not pointing to any other node what a node you have created that is the first node so by the time simply a temp variable we are assigning to root M variable we are assigning to root that is nothing but thousand then it start pointing to the first node newly created no that is so if block so else block will not execute so when else block will execute means for remaining node operations if you connect the second node third node fourth node for remaining nodes this else block will execute how it will execute see for example after execution of this append function temp variable will be deleted suppose if you want to add one more node second node third node fifth node so then else block execute so to explain this very clearly I write some nodes first suppose here second node is the second node and next third node is there just consider I am writing here mm and this node address is a 3000 3000 here 2000 will be stored here connection thousand is here this connection is 23 thousand is here so connection and x1 2000 here so connection and 30 now this node address is a null a decisional this consider as of not three nodes are there in the list now I want to create the fourth node so then you will understand clearly okay so first of all as usual append function you are calling the control come inside so temporary variable will be created initially next we are allocating the memory that is nothing but nothing but a node will be created node will be created at some location so that will be collected into temp variable so temp is a 4000 temporarily it is pointing to that node temporarily and next one here it is we are asking to enter the node data and we are saying that temp 2 left is equals to null and temp 2 write equals to null so in that node suppose data is a 40 left equals to null right equals to null node is ready now where we have to connect self suppose here we are checking if root equals to null value is root equals to null value no because root is already pointing to the node which is in the list so list is not empty so if block will not execute then continuation part else block execute in the else blocks are what we have to do we need to connect the fourth node here it is at the third node but we need to travel from first location to third location how to travel how to travel means with the help of one more variable struct node star P P is a pointer variable so initially so P in the value P holding the value root value because we should start from the root only in a root so root value initially thousand root value we are collecting in P so that is the thousand next we should travel how many nodes are there how many links are there from first node to that particular node we have to move how to move here it is just while if P 2 right not equals to null if P 2 right not equals to another right means what the next node link right link if right node link is a null means what we already know that last node a right link will be null so with the help of that location only so we can travel p2 right p-value is a thousand so here it is thousand to right is a 2000 yes it is not equals to null so what is that meaning what what that describes second node is there so that p2 right value p2 right value will be stored into P so what is that p2 right value is a 2000 so 2000 will be stored here 2000 and next again it will repeat 2002 right yes 2002 right 3000 is then so here it is 3000 will be stored 3000 will be stored so next again 3000 to write a journal s condition true I mean right null not equals to null sir condition false then it will fail see P is pointing to the node where we have to create the new node simple thing now sir how to establish the connection very simple here here you have to store 4000 so that this link will be created and here you have to store 3000 then it will be created sir house are very simple 4000 means is a temple una so what is the temple you 4000 so 4000 nothing but M value will be stored into this look who is pointing to this node 3000 is a P and this is what right P to right location M value will be stored into p2 right next one so this one is over connection now 3,000 we need to store into this location the 3000 means what is a P P we need to store into this location who is pointing to this node temp variable is pointing to this node temper and what is this location left location or right location left location so temp to left p value will be stored into m to left this is this is right if you want to connect a node at the end of all the nodes first we have to travel from first location to that particular location nothing but to the last node location and then only two connections because a double linked list okay here it is a right side connection is required and here it is a left side connection is required so this is how to append a node in a double linked list okay and some more operations on a double linkedlist so we will see in the next session okay hope you enjoy this video for more videos please subscribe to nourish 80 channel thank you you

Channel: Naresh i Technologies

Views: 225,539

Keywords: Naresh IT, Srinivas, Balu C, Data Structures Overview, Hands on Data Structures Training, Online Data Structures Training, Data Structures Demo, Learn Data Structures, Data Structures

Id: aTVSEEQXs-Y

Length: 19min 29sec (1169 seconds)

Published: Thu Oct 06 2016