1 00:00:01,890 --> 00:00:02,480 OK. 2 00:00:03,300 --> 00:00:14,490 So previously, we looked at the singly linked list being templated, and now we are actually going 3 00:00:14,490 --> 00:00:17,400 to change it to a link list. 4 00:00:18,330 --> 00:00:21,090 So this is actually going to be a pretty short video. 5 00:00:21,840 --> 00:00:28,560 There is not a lot we have to do actually to change this from single English to double link list. 6 00:00:29,970 --> 00:00:37,860 But as you see, I have already added my or changed my preprocessor directives here to accommodate for 7 00:00:37,860 --> 00:00:41,640 us having a link list and just renamed it basically. 8 00:00:41,650 --> 00:00:42,920 So you can do that as well. 9 00:00:42,930 --> 00:00:47,250 I did it here in the L.A. header and the list header as well. 10 00:00:49,170 --> 00:00:56,430 So let's go ahead and get started, so if you remember pretty much all we have to do. 11 00:00:56,670 --> 00:00:57,030 Yeah. 12 00:00:57,480 --> 00:01:02,910 Basically, the difference between a single rolling list and the mailing list is just that previous 13 00:01:02,910 --> 00:01:03,510 pointer. 14 00:01:03,870 --> 00:01:10,080 So each node will not only have a pointer to the next node, but it'll also have a pointer to the previous 15 00:01:10,080 --> 00:01:10,410 node. 16 00:01:11,280 --> 00:01:17,250 So to accommodate that, we're pretty much just going to copy what we have here for our next. 17 00:01:18,060 --> 00:01:24,060 And just do that for previous and I am going to just call that. 18 00:01:24,060 --> 00:01:29,070 So I'm doing a templated L node pointer here, and I'm I call that underscore preve. 19 00:01:30,400 --> 00:01:32,980 And so I'm also going to make some functions here. 20 00:01:35,780 --> 00:01:41,860 This is going to be returned and it's included L.A. and we're just going to call that preview and then 21 00:01:41,860 --> 00:01:44,080 we'll do our setter one here. 22 00:01:44,090 --> 00:01:51,880 So this will also like that and I'll just call that you as well. 23 00:01:52,750 --> 00:01:55,030 OK, and that's all we have to do in here, actually. 24 00:01:55,040 --> 00:02:00,040 So let's head over to the implementation file to add these. 25 00:02:01,550 --> 00:02:04,790 So I am going to put it right here. 26 00:02:07,680 --> 00:02:10,610 So this first function 27 00:02:14,480 --> 00:02:19,160 and this is just going to return our crew underscore preve data, remember? 28 00:02:20,390 --> 00:02:22,340 I'm going to go down here to end this next one. 29 00:02:23,660 --> 00:02:33,800 And this is our deployed function, and I call this preve, and it's going to get past a typically known 30 00:02:33,800 --> 00:02:37,070 point or for setting the previous note. 31 00:02:37,940 --> 00:02:43,120 And I will just say preve underscore preve equals to past preve. 32 00:02:44,630 --> 00:02:47,420 OK, so that was pretty simple. 33 00:02:48,230 --> 00:02:49,400 We just added that in there. 34 00:02:49,400 --> 00:02:59,090 We also want to come up here, though, and set initialize our three pointer to null pointer the constructor 35 00:02:59,090 --> 00:02:59,480 there. 36 00:03:01,150 --> 00:03:09,490 And that is going to be it, actually, I believe, for our nodes, a node class. 37 00:03:10,030 --> 00:03:12,550 I don't think we need to do anything in the header of the link list. 38 00:03:12,550 --> 00:03:17,560 So we're just going to head straight to the implementation. 39 00:03:18,430 --> 00:03:20,740 What we're going to be changing here. 40 00:03:21,770 --> 00:03:25,160 Is this part and that part? 41 00:03:25,460 --> 00:03:33,320 So if we have size zero and we're just adding a new node, the previous pointer that preve pointer and 42 00:03:33,320 --> 00:03:38,810 the next pointer are both just going to be no pointer, so we don't have to worry about setting those. 43 00:03:39,200 --> 00:03:43,280 But here, when the size is one, we're setting our next pointer to new node. 44 00:03:43,580 --> 00:03:54,380 But we also now need that new node to point back to head somewhere, do new node arrow preve and then 45 00:03:54,380 --> 00:03:59,900 set it to head because head's pointing to new node and new nodes going back to head. 46 00:04:00,300 --> 00:04:04,380 You see, we set our tail here, so we're all good with that already. 47 00:04:05,430 --> 00:04:12,960 Down here and do the same thing pretty much, but it's going to be with carrier, so currents next is 48 00:04:12,960 --> 00:04:16,150 equal to null pointer in this condition. 49 00:04:16,170 --> 00:04:19,830 And then right here we set next equal to our new node. 50 00:04:19,830 --> 00:04:21,960 So it's going to be the final node in the list. 51 00:04:22,230 --> 00:04:24,300 It's going to be the tail, which is what we see right here. 52 00:04:24,300 --> 00:04:29,400 But in between setting the tail and setting currents next, we're going to do the same thing where we 53 00:04:29,400 --> 00:04:29,670 go. 54 00:04:30,240 --> 00:04:35,520 New nodes, previous pointer points to her. 55 00:04:37,270 --> 00:04:40,330 And so now we're pointing back each time when we add a new node. 56 00:04:42,310 --> 00:04:48,830 And all the only other thing we really got to do is to prove that our link list is working. 57 00:04:48,850 --> 00:04:54,790 I'm going to go ahead and make this print function go forwards and backwards, so head to tail and tail 58 00:04:54,790 --> 00:04:55,270 to head. 59 00:04:55,270 --> 00:05:00,220 And to do that, I'm just going to actually declare another point I and call it backwards. 60 00:05:01,420 --> 00:05:05,560 Kerr actually said an eagle, a tail because we're starting out with tail. 61 00:05:07,210 --> 00:05:13,450 I'm going to go ahead and put OCR statement here and say for words. 62 00:05:16,750 --> 00:05:27,760 So we know when we're going forwards and then I'm going to say just do a new line and then say backwards 63 00:05:27,760 --> 00:05:28,300 here. 64 00:05:30,820 --> 00:05:34,750 OK, and we're pretty much just going to copy this 65 00:05:37,420 --> 00:05:42,260 paste array here, but we're actually going to say backwards, Kerr. 66 00:05:42,400 --> 00:05:50,990 So while backwards, Kerr is not equal to null pointer, we want to print out backwards curve data and 67 00:05:51,100 --> 00:05:52,930 we have put our arrows the same. 68 00:05:52,930 --> 00:06:03,100 And then we're going to say backwards cur equals backwards curve and we're going to use the three pointers 69 00:06:03,100 --> 00:06:05,050 to traverse this list in reverse. 70 00:06:06,250 --> 00:06:07,960 And I'm also just going to do a little. 71 00:06:09,280 --> 00:06:11,340 Let's just put a little like new line here. 72 00:06:14,620 --> 00:06:19,030 OK, so now we're putting our forwards and backwards, we actually don't need to modify anything in 73 00:06:19,030 --> 00:06:24,910 our main because we're still going to do the same thing using our print function for both lists. 74 00:06:25,360 --> 00:06:32,860 Our input files still has this one two three four five six seven a 3G in it, but it's going to print 75 00:06:32,860 --> 00:06:38,410 out a forwards version and a backwards version using the next pointer for the first in the pre four 76 00:06:38,410 --> 00:06:43,900 pointer for the second version there, so we can confirm that our link list implementation is actually 77 00:06:43,900 --> 00:06:44,380 working. 78 00:06:45,490 --> 00:06:46,600 So let's go ahead and run this. 79 00:06:46,600 --> 00:06:47,590 Hopefully it runs well. 80 00:06:47,590 --> 00:06:48,640 We don't run the errors. 81 00:06:48,640 --> 00:06:50,770 But while this possibility? 82 00:06:56,160 --> 00:06:58,590 OK, looking pretty good. 83 00:07:00,020 --> 00:07:06,230 All right, so there we have our forwards one through seven and then we have spring out backwards and 84 00:07:06,230 --> 00:07:09,890 then it goes in reverse and everything looks pretty good. 85 00:07:10,940 --> 00:07:12,620 Both of our types of lists. 86 00:07:14,050 --> 00:07:15,970 OK, so I know that was a short video. 87 00:07:16,600 --> 00:07:25,870 We're actually going to get into a couple of problems after this and look into insertion and also maybe 88 00:07:25,870 --> 00:07:27,190 just some little. 89 00:07:29,240 --> 00:07:34,670 Kind of test sound like interviewee problems where you have to do a specific thing with the delay list 90 00:07:34,670 --> 00:07:41,300 now that we have two different types, so maybe some coding exercises and then we'll put some video 91 00:07:41,300 --> 00:07:43,790 solutions for you, but hopefully this was clear enough. 92 00:07:44,180 --> 00:07:52,100 Really not modifying very much to make it a link list and still have the template option. 93 00:07:52,100 --> 00:07:55,940 So, all right, I will see you in the next lecture then.