- 15 hours ago
Transcript
00:00Next we are going to talk about another function which we are going to add in a link list somewhere
00:04I will pass the index where I want to insert the value
00:11and with that I will pass the data which I want to insert
00:15Let's see it a little visually
00:17If I have 3 nodes in the link list
00:20and I want to insert a new node
00:24Where do I want to insert?
00:25I want to insert index is equal to 1
00:28This is my index is equal to 0
00:30This is 1 and this is 2
00:31What can I say?
00:33I want to point this node to the new node
00:36and point this node to the next node
00:39and break this chain
00:41What did I do?
00:43This next point here
00:45Now I have to point this next
00:47and this next point here
00:50So simply my index will automatically change
00:53Now this will come to my first index
00:55This will come to my second index
00:58and this will come to my third index
01:00So what can I say?
01:01The operation of the link list is in constant time
01:05How does it happen?
01:07What do I do?
01:09I want to point this next point here
01:11and point this next point here
01:13This link will automatically break
01:15and this lists will automatically pass
01:16So that will be done
01:17I don't have to copy paste
01:18Where did I do these elements?
01:19I need to copy paste
01:19where would I have to write
01:23In Arrays
01:23How did I have to write
01:25When I have to write what I have to write
01:26If I have put Arrays
01:28I need to write an array
01:35and then I have to insert 1
01:39Now I have to insert 1
01:42and then I will insert 1
01:45I will copy it here
01:48so the copy of the step
01:50we have completely removed
01:53and copy of the operations
01:55are always in the array list
01:56when we try to add
02:00but here
02:02I have to change my pointers
02:06so I have constant operations
02:08to linkage this
02:10but also
02:11the add in the middle operation is linear time
02:14why is it linear time?
02:17because I have time to find the index
02:19I don't have time in the array list
02:23what should I do in the array list
02:24what should I do in the link list?
02:25I have to track
02:26the issue in the link list is that
02:28I have only head information
02:30so I know this is my index 0
02:31I will go to next
02:33then I will know that this is my index 1
02:35then I will know that this is my index 2
02:38then I will know that this is my index 3
02:46that is why
02:48the total time complexity
02:51is big of n
02:52instead of the linkage process
02:54I have only constant time
02:56in the array list
02:58I have already known that
03:00the copy of n
03:02this is my index 2
03:05now let me understand
03:06more detail
03:10level
03:10let me understand
03:11I have a link list
03:12I have 1
03:15here
03:16I have 2
03:17here
03:18this node
03:18I have 3
03:19this node
03:20I have 4
03:21what I want to do?
03:23here
03:24here
03:25here
03:25here
03:26and this is pointing to my null
03:28now I have my head value
03:31what I have to do is I have a index is equal to 2
03:34I have to insert a node
03:37I have to insert a node in which I have a value
03:40so what I will do?
03:42I will take a temporary value
03:44because I have to find the index
03:46now I have the index that is equal to 0
03:50because at the start of the head
03:53so what I will do?
03:55I will make a temporary node
03:56which is pointing to my head
03:59now I will increase this temporary value
04:01at the start of my index
04:03i, its value is 0
04:05I will increase this temporary value
04:07until my index is equal to 1
04:10this index is not equal to 1
04:12why do I need index minus 1
04:14because if I have to insert the index
04:16to 2
04:18imagine how will this scenario
04:20how will this result?
04:20first I had to do this index
04:22so what will I do?
04:23I will go to next index
04:23so my temporary value is here
04:26and my index is 1
04:28if I have to insert a value in index
04:29if I have to insert a value in index
04:31I will insert a value in 2
04:31then I will say that
04:33I will need to have previous index
04:35previous index
04:36not previous index
04:37or previous index
04:38or a previous index
04:39so I have reached a previous index
04:41I will create a new node
04:43there
04:43which is 9
04:47and here
04:48because this value is now
04:50index 2
04:51so I will insert the previous index
04:53that link
04:54and I will connect it
04:56to my new node
04:57and my new node
04:59next
04:59is now pointing it
05:01so this was the previous index
05:03number 2
05:03but now this is the new index
05:06number 3
05:06because index
05:07number 1
05:08will point
05:09to my index
05:10number 2
05:11which is my new node
05:13which is my new node
05:18so I will find a loop
05:19I will run a loop
05:20while my eye is less than
05:23index
05:23minus 1
05:24and what I will do every time
05:26I will do
05:27I will do
05:27plus plus
05:28and I will do
05:30update
05:30how I will do
05:31temporary
05:33next
05:33a loop
05:34which I will increase
05:36with the index
05:38and I will increase
05:39and I will increase
05:41with the index
05:41as I will increase
05:43my index
05:44minus 1
05:45so I can say
05:46that at that time
05:47when I have a temporary value
05:49that is my previous
05:51so what I have to do
05:52I have to do
05:52my new node
05:54next
05:54it will become
05:57temporary
05:58next
06:00here
06:01temporary
06:01next
06:03was this node
06:03so what I have to do
06:05I have to point it
06:07here
06:07the second step
06:08for me
06:08is that
06:09temporary
06:11next
06:12will become
06:16temporary
06:17next
06:18point
06:18here
06:19this
06:20point
06:20and the linkage
06:22automatically
06:23break
06:24so
06:24with these
06:25two steps
06:25I can add
06:27new nodes
06:28in the middle
06:29so
06:30add index
06:31one time
06:32I will make a new method
06:33in my linked list
06:34class
06:36I will name
06:37this method
06:37I will name
06:38public
06:39void
06:40add
06:41only
06:42add
06:42which
06:43will be
06:44index
06:45and
06:46data
06:47what I have to do
06:49first
06:49because
06:49add
06:50operation
06:50first
06:51I will create a new node
06:54new node
06:55is equal to
06:56new node
06:57of data
06:58what I have to do
07:04then
07:04add
07:04temporary
07:05node
07:06temporary
07:06is equal to my head
07:08now
07:08I will run a loop
07:09with an integer
07:12variable
07:12variable
07:12index
07:13i
07:14will track
07:14which is
07:16index
07:17i
07:19is less
07:20than
07:20index
07:21minus
07:211
07:21equal to
07:22index
07:22i
07:23is equal to
07:25previous node
07:26so
07:27until
07:27I will make
07:28temporary
07:30next
07:33and
07:33I will do
07:34every time
07:34i
07:35plus
07:35now
07:36i
07:38is equal to
07:41index
07:42minus
07:421
07:42equal to
07:44temporary
07:44is equal to
07:46my previous
07:46next
07:47what I have to do
07:47in that case
07:47what I have to do
07:48next
07:48is
07:49temporary
07:51next
07:51is
07:55my new
07:57node
07:58so
07:59here
08:00I have inserted
08:01my new node
08:02in the middle
08:04let's save
08:05I have a link list
08:061
08:072
08:073
08:074
08:08now
08:08I have to insert
08:09another value
08:10in fact
08:11same thing
08:12in the link list
08:13I will add
08:14index
08:152
08:16node
08:179
08:18and
08:19then
08:19I will print
08:21save
08:22and
08:23now
08:23run
08:25so
08:26what happened
08:271
08:272
08:28then
08:289
08:29and
08:313
08:32and
08:334
08:33now
08:34I will add
08:380
08:39so
08:40in
08:40this way
08:40I want to add
08:41things to my head
08:42if I want to add
08:44things to my head
08:44then I will call
08:46add first
08:47if my index
08:49value is 0
08:49then
08:50this will be a special case
08:50in which I will call
08:53add first
08:54I will pass
08:55data
08:56and return
08:58I have written
08:58this step
08:59differently
09:00because
09:01when we add first
09:02then
09:03our first node
09:04is created
09:04this node
09:05is important
09:06for creation
09:07because
09:07my head
09:09and tail
09:10will change
09:10when we add first
09:12so my head
09:13value is always
09:14the most important
09:15so
09:16my
09:16add first
09:18operations
09:18in which I am
09:19handling my head
09:19I am changing
09:21the value
09:22for that case
09:23I have called
09:24add first
09:26and
09:26insert the other
09:26cases
09:27for me
09:28I can insert
09:29myself
09:29insert it
09:30the other
09:30the other
09:30that
09:30I will
09:30the other
09:30to the
09:30that