1 00:00:00,000 --> 00:00:03,325 At the moment, we can create an empty list, but nothing else. 2 00:00:03,325 --> 00:00:06,250 Let's define a method to add data to our list. 3 00:00:06,250 --> 00:00:09,907 Technically speaking, there are three ways we can add data to a list. 4 00:00:09,907 --> 00:00:12,323 We can add nodes at the head of the list, 5 00:00:12,323 --> 00:00:16,366 which means that the most recent node we created will be the head. 6 00:00:16,366 --> 00:00:20,420 And the first node we created will be the tail or we could flip that around. 7 00:00:20,420 --> 00:00:22,730 Most recent nodes are the tail of the list and 8 00:00:22,730 --> 00:00:25,190 the first node to be added is the head. 9 00:00:25,190 --> 00:00:28,360 I mentioned that one of the advantages of linked lists over arrays 10 00:00:28,360 --> 00:00:32,970 is that inserting data into the list is much more efficient than to the array. 11 00:00:32,970 --> 00:00:36,140 This is only true if we're inserting at the head or the tail. 12 00:00:36,140 --> 00:00:39,277 Technically speaking, this isn't an insert, and 13 00:00:39,277 --> 00:00:43,984 you'll often see this method called add prepend if the data is added to the head 14 00:00:43,984 --> 00:00:46,215 or append if it's added to the tail. 15 00:00:46,215 --> 00:00:50,337 A true insert is where you can insert the data at any point in the list, 16 00:00:50,337 --> 00:00:52,626 which is our third way of adding data. 17 00:00:52,626 --> 00:00:56,755 We're gonna circle back on that if we wanted to insert at the tail, 18 00:00:56,755 --> 00:00:59,795 then the list needs a reference to the tail node. 19 00:00:59,795 --> 00:01:02,404 Otherwise, we would have to start at the head and 20 00:01:02,404 --> 00:01:05,790 walk down the length of the list or traverse it to find the tail. 21 00:01:05,790 --> 00:01:09,328 Since our list only keeps a reference to the head, 22 00:01:09,328 --> 00:01:13,043 we're going to add new items at the head of the list. 23 00:01:13,043 --> 00:01:17,687 Now before we add our new method, I forgot that I didn't show you in the last 24 00:01:17,687 --> 00:01:20,784 video how to actually use the code we just added and 25 00:01:20,784 --> 00:01:25,612 how to check every time when we add new code that it works correctly Directly. 26 00:01:25,612 --> 00:01:29,947 So like before, we're going to bring up the console and 27 00:01:29,947 --> 00:01:34,100 here we're gonna say python -i linked_list.py, 28 00:01:34,100 --> 00:01:38,267 which should load it, load the contents of our file. 29 00:01:38,267 --> 00:01:44,427 And now we'll start here by creating a linked list, so l =LinkedList(), 30 00:01:44,427 --> 00:01:49,375 and then we'll use a node, so N1 = Node with the value 10. 31 00:01:49,375 --> 00:01:55,985 And now we can assign N1 to the nodes or to the LinkedList's head attribute. 32 00:01:55,985 --> 00:01:58,487 So l1.head = N1. 33 00:01:58,487 --> 00:02:02,120 And then, we can see if size works correctly. 34 00:02:02,120 --> 00:02:05,123 So if we call l1.size and since this is a method, 35 00:02:05,123 --> 00:02:07,493 we need a set of parenthesis at the end. 36 00:02:07,493 --> 00:02:08,390 Enter. 37 00:02:08,390 --> 00:02:10,652 You'll see that get that one correctly. 38 00:02:10,652 --> 00:02:11,730 Okay, so it works! 39 00:02:11,730 --> 00:02:18,051 Now, let's add our new method, which we're going to call add. 40 00:02:18,051 --> 00:02:24,464 Add is going to accept some data and add to the list inside of the node. 41 00:02:24,464 --> 00:02:26,498 So we'll say def add(). 42 00:02:26,498 --> 00:02:29,998 And every python method takes self as an argument. 43 00:02:29,998 --> 00:02:34,254 And then, we want to add some data to this node, so we're gonna say data for 44 00:02:34,254 --> 00:02:35,547 the second argument. 45 00:02:35,547 --> 00:02:39,692 Inside the method, first, we'll create a new node to hold on to the data. 46 00:02:39,692 --> 00:02:44,419 So new_node = Node(data). 47 00:02:44,419 --> 00:02:47,970 Before we set the new node as the head of the list. 48 00:02:47,970 --> 00:02:50,760 We need to point the new node's next property 49 00:02:50,760 --> 00:02:54,020 at whatever node is currently at Head. 50 00:02:54,020 --> 00:02:56,770 This way when we set the new node as the Head of the list 51 00:02:56,770 --> 00:02:59,524 we don't lose a reference to the old Head. 52 00:02:59,524 --> 00:03:06,929 So new_node.next node = self.head. 53 00:03:06,929 --> 00:03:12,229 Now, if there was no node at head this correctly sets next node to none. 54 00:03:12,229 --> 00:03:16,561 Now we can set the new node as the head of the node. 55 00:03:16,561 --> 00:03:19,221 So say self.head = new_node. 56 00:03:19,221 --> 00:03:25,395 Because the insert operation is simply a reassignment of the head and 57 00:03:25,395 --> 00:03:30,728 next node properties, this is a constant time operation. 58 00:03:30,728 --> 00:03:34,624 So let's add that in as a down string. 59 00:03:34,624 --> 00:03:37,800 First, what the method does. 60 00:03:37,800 --> 00:03:46,138 So it adds a new node containing data at the head of the list. 61 00:03:46,138 --> 00:03:52,760 This operation takes constant time which is our best case scenario. 62 00:03:52,760 --> 00:03:54,160 Okay, let's test this out. 63 00:03:54,160 --> 00:03:56,340 So we're gonna bring the console back up. 64 00:03:56,340 --> 00:04:01,580 We'll exit out of our current level and 65 00:04:01,580 --> 00:04:05,290 we'll load the contents of the file again, and 66 00:04:05,290 --> 00:04:08,250 now we don't need to create a node like we did earlier. 67 00:04:08,250 --> 00:04:11,692 So we can say l = LinkedList. 68 00:04:11,692 --> 00:04:13,356 l.add(1). 69 00:04:13,356 --> 00:04:15,525 Okay, let's see if this works. 70 00:04:15,525 --> 00:04:17,589 We'll call size. 71 00:04:17,589 --> 00:04:23,167 And if it worked, then linked list should now have a size of 1. 72 00:04:23,167 --> 00:04:24,309 There we go. 73 00:04:24,309 --> 00:04:30,645 You can also do l.add(2), l.add(3) and l.size should now be 3. 74 00:04:30,645 --> 00:04:32,490 There we go. 75 00:04:32,490 --> 00:04:33,980 If I were to type l and 76 00:04:33,980 --> 00:04:39,060 just hit print, again, what we get in the repl is nothing useful. 77 00:04:39,060 --> 00:04:43,890 So like before we'll implement the repr function for our linked list. 78 00:04:44,980 --> 00:04:49,700 Now, I'm just going to copy paste this in and we'll walk through it. 79 00:04:49,700 --> 00:04:53,380 Okay, so this is what our implementation of repr looks like for 80 00:04:53,380 --> 00:04:55,200 the linked list object. 81 00:04:55,200 --> 00:04:59,520 You can grab this code from the note section of this video. 82 00:04:59,520 --> 00:05:02,680 Okay, so at the top you'll see a doc string where it says it returns a string 83 00:05:02,680 --> 00:05:04,680 representation of the list. 84 00:05:04,680 --> 00:05:08,430 And like everything we need to do with a link list we need to traverse it. 85 00:05:08,430 --> 00:05:10,690 So this is going to take linear time. 86 00:05:10,690 --> 00:05:12,780 We start by creating an empty list. 87 00:05:12,780 --> 00:05:16,880 Now, I need to distinguish this is python list not linked list. 88 00:05:16,880 --> 00:05:21,770 So we create an empty list called nodes, and to nodes we're going to add strings 89 00:05:21,770 --> 00:05:25,960 that have a description, that provide a description of each node. 90 00:05:25,960 --> 00:05:29,640 But we're not going to use the description that we implemented in the node class, 91 00:05:29,640 --> 00:05:32,110 because we're gonna customize it a bit here. 92 00:05:32,110 --> 00:05:35,940 Next, we stand by signing self.head to current. 93 00:05:35,940 --> 00:05:39,130 So we sort have a point to the head node. 94 00:05:39,130 --> 00:05:41,840 As long as current doesn't equal non, 95 00:05:41,840 --> 00:05:45,130 which mean we not added the tail we are going to implement some logic. 96 00:05:45,130 --> 00:05:50,382 So in the first scenario, if the node assign to current is the same as the head. 97 00:05:50,382 --> 00:05:54,741 Then we're going to append this string to our nodes list. 98 00:05:54,741 --> 00:05:59,721 And the string is simply going to say that hey, this is a head node. 99 00:05:59,721 --> 00:06:04,050 And it contains some data, which we'll extract using current.data. 100 00:06:04,050 --> 00:06:08,491 The next scenario is if the node assigned to current next node is none, 101 00:06:08,491 --> 00:06:13,632 meaning we're at the tail node, then we'll assign a different kind of string. 102 00:06:13,632 --> 00:06:16,062 So it's the same as over there except we're saying tail here. 103 00:06:16,062 --> 00:06:20,353 And then finally, in any other scenario which means we're not at the head or 104 00:06:20,353 --> 00:06:23,719 not at the tail we'll simply print the nodes value inside. 105 00:06:23,719 --> 00:06:26,106 And again, we'll extract it using current.data. 106 00:06:26,106 --> 00:06:30,257 With every iteration of the loop will move current forward by calling 107 00:06:30,257 --> 00:06:32,915 current.next_node and reassigning it. 108 00:06:32,915 --> 00:06:37,118 And then in the very end when we're done, we'll join all the strings 109 00:06:37,118 --> 00:06:41,890 that are inside the nodes list together using the python join method. 110 00:06:41,890 --> 00:06:44,090 And we'll say that with every join. 111 00:06:44,090 --> 00:06:47,440 So when you join these two strings together to make one string, 112 00:06:47,440 --> 00:06:51,140 you need to put this set of characters in between, all right? 113 00:06:51,140 --> 00:06:52,950 So let's see what this looks like. 114 00:06:52,950 --> 00:06:55,920 So I'm going to come down here, exit out of the console again, 115 00:06:55,920 --> 00:07:00,970 clear it out, load the contents of the file again, and let's try that. 116 00:07:00,970 --> 00:07:04,167 So we'll say l = LinkedList. 117 00:07:04,167 --> 00:07:10,560 All right, so l.add1, l.add2, l.add(3). 118 00:07:10,560 --> 00:07:11,970 That seems enough. 119 00:07:11,970 --> 00:07:14,568 And then now if I type our l and hit enter, 120 00:07:14,568 --> 00:07:17,715 we get a nice string representation of the list. 121 00:07:17,715 --> 00:07:20,436 So you can see that we add every new node to the head. 122 00:07:20,436 --> 00:07:22,798 So we added one first. 123 00:07:22,798 --> 00:07:25,750 One ends up being the tail, because it keeps getting pushed out. 124 00:07:25,750 --> 00:07:29,955 Then 2, and then finally 3, so 3 is at the head. 125 00:07:29,955 --> 00:07:33,651 So far we've only implemented a single method which 126 00:07:33,651 --> 00:07:38,355 functions much like the append method on a python list or an array, 127 00:07:38,355 --> 00:07:41,981 except it adds it to the start of the length list. 128 00:07:41,981 --> 00:07:43,891 It prepends it. 129 00:07:43,891 --> 00:07:47,091 Like a pen, this happens in constant time. 130 00:07:47,091 --> 00:07:50,651 In the next video, let's add the ability to search through our list.