- 15 hours ago
Transcript
00:00Now, first of all, let's talk about the add operation in the link list
00:03There are two ways of adding in the link list
00:05One can add in the first place and one can add in the last place
00:10First of all, let's see how we can add first
00:12I imagine that I have three nodes in a link list
00:17which is stored in our data
00:19and in each one is stored in our next reference
00:24So, this will be pointing here, this will be pointing here
00:27and this will be pointing null
00:29To add a new node in the first position
00:32It means that if there was a new node head
00:35then there will be a new node
00:37which will point the new head
00:40and this will not be the new node
00:44Let's see the step by step process
00:45If I want to add a new node
00:48then I will create that node
00:51The first step is to create that new node
00:55Step one is to create new node
01:00Second step is to create new node
01:13Second step is to create new node
01:25If I want to change the new node
01:29I want to change the new node
01:30I want to change the new node
01:31So, step 3 will be
01:32My head is equal to my new node
01:37What will I have to change the new node
01:40If I have two nodes in the linked list
01:42Then I will change the new node
01:45And then I will change the new node
01:46That is the new node
01:47Because I have added the first position
01:50If I have four nodes in this way
01:54So, this is my tail and this is my head
01:57The new node is coming here and now it's going to point it
02:00The tail doesn't need to be different
02:02The tail will be different in one case
02:03Which case will be different and it will be my base case
02:07The tail will be different when my link list is empty or null
02:11In that case, my head is null and tail will be null
02:15So, first of all, I will create a new node
02:19And I will assign the head to this
02:21And in this case, I will assign the tail
02:24So, this will be a special case in which my link list is empty
02:27So, a new node will be the head of the link list and the tail of the link list
02:34If you think that I have another case
02:36In which there already exists a node
02:42Where the head and tail are the same
02:44What will happen in that case?
02:47If I first add first
02:48So, I will create a new node here and now I will point my head to the next node
02:55And what will happen in that case?
02:56I will turn the head here and take it here
02:59If there is a single node, then we will follow the same steps
03:03If there is one or more node in a link list, then we will follow these three steps
03:07If there is another node, then we will create a new node
03:11And we will create the head and the tail
03:14At that time, the next node
03:17We don't need to point the head to a different point
03:18Because when we came to the head, it was null
03:20Because my link list was empty
03:22Now, the steps we have written
03:24For this, we will convert it in code
03:27So, this was my link list class
03:29In the link list class, I have made my node class
03:31Now, I am going to define the methods of this node class
03:34I am going to define my operations
03:36First of all, I will write public
03:39Now, I don't need to write static
03:41Why don't I need to write?
03:42Because the main function is a static function
03:44And in the static function, you can call the static functions directly
03:49But now, we don't need to write calls directly
03:51Now, we will write the link list object
03:54Now, we will write calls
03:55So, if the link list object is static or non-static
03:58It will not be different
03:59So, now, we can use the non-static functions and methods
04:03So, first of all, I will create the method
04:05It will be called public void add first
04:10In the add first, I will pass data
04:12The head can be directly access
04:14The tail can be directly access
04:16Because all the information is in a single class
04:19Which is my linked list class
04:21For add first, I have learned three steps
04:24Step 1
04:26Which was created
04:27Create new node
04:29So, the new node will create
04:31The process of creating new node
04:32I will create a node type object
04:34New node
04:37New node
04:38I will pass data
04:40And initialize
04:41So, I am going to write syntax
04:43This is the syntax
04:44Which we define every object
04:46First, I have written my class
04:47I have written my class
04:49Then I have written my object
04:49I have written my object
04:50I have used the new keyword
04:51Then I have used my class
04:53And then I have passed my class
04:53And then I have passed the constructor
04:54And I have passed the data
04:57What was my name in the constructor?
04:58Step 2
04:59Step 2
04:59For my name is
05:02I assign my head's value to next
05:05So, my new node
05:06It will point my previous head
05:09So, how can this be possible?
05:11I will write
05:12New node
05:13Next
05:14Is equal to
05:15My head
05:16So, here
05:17I have actually linked
05:20One node
05:21To the other node
05:22This is my linking step
05:25So, I have created a link list
05:27How did this
05:28How did this
05:28I have done this
05:30I have done this
05:30That the value of head
05:31Is going through
05:32Who is going through
05:33Is going through my new node
05:34Next
05:35I can go through my head
05:36So, next
05:37In this head
05:39It will store
05:39The reference
05:40Or address
05:41Now, if the value of head
05:44The value of head
05:45Is changed
05:45Then there is no problem
05:46In this current address
05:48I have stored
05:50I have stored
05:50In next
05:50I can imagine it
05:53I can imagine it
05:54This is my link list
05:56Which is two nodes
05:57This is pointing
05:59To this side
06:00Here
06:00Your next
06:02Here
06:02Your next
06:03And this will point
06:04To null
06:06Now, my link list
06:07Head
06:07Is this node
06:08So, I have created a new node
06:10Which will be next
06:12Now, next
06:13This value
06:15Is
06:16It means
06:17New node
06:18Next
06:19Is
06:20Head
06:20Address
06:22Head
06:22Not
06:22Head
06:22Is
06:23Head
06:25Point
06:26So, head
06:27Address
06:28This object
06:31Address
06:31123
06:32So, head
06:33Address
06:33123
06:34Next
06:35Next
06:36If I change
06:37Head
06:38Now, head
06:40Not
06:421
06:422
06:433
06:431
06:432
06:435
06:44To
06:44Toamt
06:44To
06:56bring To
07:05Area
07:10To
07:12Smart
07:13To
07:13To
07:142
07:14the address will never change
07:14next the address will always point
07:17so the address in the head
07:18that I have stored in the index
07:20now I will perform my step 3
07:24which is the value of the head
07:25which will become a new node
07:28so head is equal to new node
07:30so my head
07:31is pointing to the new node
07:33or which node
07:35we have created in this step
07:37these are the steps
07:38when I have to do
07:42it is more than a node
07:43assume my link list is empty
07:45when my link list is empty
07:46what will happen in that case
07:48my head will be null
07:49i have no data
07:52i have not initialized
07:55what will happen in that case
07:57i will always make a new node
07:59so what will happen in that case
08:01step 1
08:01i will create a new node
08:06if my head is null
08:08then head
08:10head value is equal to
08:11tail value is equal to
08:13new node value
08:15and here i will do
08:18return
08:18so if my head is null
08:20and my link list is empty
08:21then i will create a new node
08:22first i will create a new node
08:24then the value of the new node
08:27i will add a new node
08:28and here i will do return
08:30otherwise i will perform my two steps
08:32i will create a new node
08:33next to the new node
08:34and then the new node
08:36i will create a new node
08:37so how will i add elements
08:39i can write here
08:42link list dot add first
08:44first i have added 1
08:45i have added 1
08:49then i can add 2
08:51then i will add 2
08:51so my link list will be 1
08:52and then my link list will be 2
08:55so i will create a new node
08:58what was my link list
09:00my link list was empty
09:01just like
09:02i have added 1
09:04i have added 1
09:06i have added 1
09:07and then i have added 2
09:08when i have done this step
09:10first i will create a new node
09:13which will be a new node
09:14which will be a new node
09:17because in the beginning
09:18my link list is empty
09:20so this will be my head
09:22and it will be a new node
09:23then this node will be a tail
09:24what will i perform this step
09:27so i will perform this step
09:28and then i will create another node
09:30which will create itself
09:33and what will i perform next?
09:34first of all we will point this head
09:36and then the head
09:38will be able to move here
09:40and the new node is my head
09:43and now this node will become my head
09:43so when these two steps will be performed
09:45then i will be a final link list
09:47and i will have the data
09:49this value is 1 and this value is 2
09:52so now my head is because I have added 2
09:55so first I have added 2
09:57in my linked list and then
09:59in my linked list tail
10:01one data stored
10:02and if we look at this
10:04then add first
10:05time complexity
10:07that was big of 1
10:09why did we do constant time
10:11because we are running a loop
10:13or recursion
10:16so in every case we perform a single operation
10:17and constant operation
10:19we perform 3 operations
10:20so I have added 1 constant time
10:23in the linked list