Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
What Is a Linked List?13:18 with Pasan Premaratne
Despite having powerful collection types built in to most languages we often have a need for custom data structures that store data in different ways. In this video let's take a look at what a linked list is
[MUSIC] 0:00 [SOUND] Over the next few videos, we're going to build a data structure that you 0:04 may have worked with before, a linked list. 0:09 Before we get into what a linked list is, let's talk about why we build data 0:11 structures instead of just using the ones that come built in to our languages. 0:15 Each data structure solves a particular problem. 0:19 We just went over the basics of the array data structure. 0:23 And looked at the cost of common operations that we carry out on arrays. 0:26 We found that arrays were particularly good at accessing, 0:30 reading values happens in constant time. 0:33 But arrays are pretty bad at inserting and deleting, 0:36 both of which run in linear time. 0:39 Linked lists, on the hand, are somewhat better at this, 0:41 although there are some caveats. 0:44 And if we're trying to solve a problem that involves far more inserts and 0:46 deletes than accessing, a linked list can be a better tool than an array. 0:50 So what is a linked list? 0:55 A linked list is a linear data structure where each element in the list is 0:56 contained in a separate object called a node. 1:01 A node models two pieces of information, an individual 1:05 item of the data that we want to store and a reference to the next node in the list. 1:08 The first node in the linked list is called the head of the list, 1:13 while the last node is called the tail. 1:17 The head and the tail nodes are special. 1:20 The list only maintains a reference to the head, although in some implementations, 1:22 it keeps a reference to the tail as well. 1:26 This aspect of linked lists is very important. 1:29 And as you'll see, most of the operations on the list need to be implemented 1:32 quite differently compared to an array. 1:36 The opposite of the head, the tail, denotes the end of the list. 1:38 Every node other than the tail points to the next node in the list, but 1:42 tail doesn't point to anything. 1:47 This is basically how we know it's the end of the list. 1:49 Nodes are what are called self referential objects. 1:52 The definition of a node includes a link to another node. 1:56 And self referential here means the definition of node 2:00 includes the node itself. 2:03 Linked lists often come in two forms. 2:05 A singly linked list, 2:07 where each node stores a reference to the next node in the list. 2:08 Or a doubly linked list, 2:12 where each node stores a reference to both the node before and after. 2:13 If an array is a train with a bunch of cars in order, 2:18 then a linked list is like a treasure hunt. 2:21 When you start the hunt, 2:25 you have a piece of paper with a location of the first treasure. 2:26 You go to that location and you find an item, 2:29 along with a location to the next item of treasure. 2:32 When you finally find an item that doesn't also include a location, 2:35 you know that the hunt has ended. 2:39 Now that we have a high level view of what a linked list is, let's jump into code and 2:41 build one together. 2:46 We'll focus on building a singly linked list for this course. 2:47 There are advantages to having a doubly linked list, but 2:51 we don't want to get ahead of ourselves. 2:54 Let's start here by creating a new file where we're going to put all our code for 2:57 our linked list, so we'll call this linked_list.py. 3:04 And first, we're going to create a class to represent a node. 3:10 Say, class Node. 3:15 Now, Node is a simple object, in that it won't model much. 3:17 So, first we'll add a data variable. 3:22 oS an instance variable here called data, and 3:26 we'll assign the value None, initially. 3:28 And then we'll add one more, we'll call this next_node. 3:31 And to this, we'll assign None as well. 3:34 So we've created two instance variables. 3:36 data, to hold onto the data that we're storing. 3:39 And next_node to point to the next node in the list. 3:42 Now we need to add a constructor to make this class easy to create. 3:46 So we'll add an __init__ method here that takes self and some data to start off. 3:51 And all we're going to do is assign data to that instance variable we created. 3:57 So that's all we need to model Node. 4:02 Before we do anything else though, let's document this. 4:05 So, right after the class definition, let's create a doc string. 4:08 So """. 4:12 Next line, and we'll say, An object for 4:14 storing a single node of a linked list. 4:19 And then on the next line, we'll say, Models two attributes, 4:23 data and the link to the next node in the list. 4:30 And then we'll close this doc string off with three more quotation marks. 4:33 Okay, using the Node class is fairly straightforward. 4:41 So we can create a new instance of Node with some data to store. 4:46 Now the way we're going to do this is we're going to bring up the console and 4:49 we're going to type out, like we've been typing out before, python, followed by 4:54 the name of the script that we wrote, which is linked list linked_list.py. 4:59 But before we do that we're going to pass an argument to the python command, 5:04 we're gonna say -i and then the name of the script, linked_list.py. 5:09 So what this does is this is going to run the python repel, 5:13 the read evaluate print loop in the console, but 5:17 it's gonna load the contents of our file into that so that we can use it. 5:20 So I'll hit Enter, and we have a new instance going. 5:25 And now we can use the Node in here. 5:28 So we can say N1 = Node. 5:31 And since we defined that constructor, we can pass it some data. 5:33 So we'll say 10 here. 5:37 Now, if we try to inspect this object, the representation returned isn't very useful, 5:39 which will make things really hard to debug as our code grows. 5:44 So for example, if I type out N1, you'll see that we have a valid instance here, 5:48 but it's not very helpful the way it's printed out. 5:52 So we can customize this by adding a representation of the object using 5:55 the repr function. 6:00 Now in the terminal still, we'll type out exist, 6:01 like that, hit Enter to exit the console. 6:05 And then down here, let's add in some room. 6:08 Okay, and here we'll say, def __repr, another set of __, 6:13 and then this function takes the argument self. 6:18 And in here, we can provide a string representation of what we want printed 6:22 to the console when we inspect that object inside of it, inside of the console. 6:28 So here we'll say return, again, this is a string representation. 6:34 So inside quotes we'll say, <Node>, so this represents a Node instance. 6:38 And the data it contains, it will say %s. 6:43 Which is a Python way of substituting something into a string, 6:47 string interpolation. 6:52 And outside of the string we can say, %, again and 6:54 here we're saying we want to replace this %s with self.data. 6:58 Okay, let's hit Save. 7:03 And before we move on, let's verify that this works. 7:05 So I'm gonna come in here, type clear to get rid of everything. 7:08 And then we'll do what we did again. 7:12 And you can just hit the up arrow a couple of times to get that command. 7:14 All right, so hit Enter. 7:18 And now, just so you know, every time you run this you start off from scratch. 7:19 So N1 that we created earlier, not there anymore. 7:24 So it's going to create it, N1 = Node(10). 7:27 And we can type N1 again and hit Enter, and 7:31 you have a much better representation now. 7:34 So we can see that we have a Node and it contains the data, 10. 7:37 We can also create another one. 7:41 N2 = Node, that contains the data, 20. 7:44 And now we can say N1.next_node = N2. 7:46 So N1 now points to N2. 7:50 And if we say N1.next_node, you'll see that it points to that Node. 7:53 The node contained 20. 7:58 Nodes are the building blocks for a list. 8:00 And now that we have a Node object, we can use it to create a singly linked list. 8:03 So again, I'm gonna exit out of this and then go back to the text editor. 8:08 And here, we'll create a new class. 8:14 So, class LinkedList:. 8:16 The LinkedList class is going to define a head. 8:18 And this attribute models the only node that the list is going to have 8:23 a reference to. 8:27 So here we'll say, head, and we'll assign None, initially. 8:28 And then, like we did earlier, let's create a constructor. 8:31 So __init__, this takes self. 8:36 And then inside, like before, we'll say, self.head = None. 8:41 This is the same as doing this, so 8:45 we can actually get rid of that and just use the constructor. 8:48 Okay, so again, 8:53 this head attribute models the only node that the list will have a reference to. 8:54 Since every node points to the next node, to find a particular node, 9:00 we can go from one node to the next in a process called list traversal. 9:04 So in the class constructor here, we'll have set the default value of head to None 9:09 so that new lists created are always empty. 9:13 Again, you'll notice here, that I didn't explicitly declare the head attribute at 9:16 the top of the class definition, and don't worry, that's not an oversight. 9:20 The self.head in the initializer means that it's still created. 9:25 Okay, so, that's all there is to modeling a linked list. 9:29 Now, we can add methods that make it easier to use this data structure. 9:32 First, a really simple doc string to provide some information. 9:36 So here, we'll create a doc string, """, and 9:40 then we'll say Singly linked list, and then close it off. 9:44 A common operation carried out on data structures is checking whether it 9:49 contains any data or whether it's empty. 9:54 At the moment, to check if a list is empty, 9:56 we would need to query these instance variables, head and so on, every time. 9:59 Ideally, we would like to not expose the inner workings of our data 10:04 structure to code that uses it. 10:09 Instead, let's make this operation more explicit by defining a method. 10:11 So, we'll say, def is_empty, and this method takes itself as an argument. 10:16 And here we'll say it return self.head == None. 10:21 All we're doing here is checking to see if head is None. 10:25 If it is, this condition evaluates to true, which indicates the list is empty. 10:29 Now, before we end this video, 10:35 let's add one more convenience method to calculate the size of our list. 10:36 The name convenience method indicates that what this method is doing, 10:41 is not providing any additional functionality that our data structure 10:45 can't handle right now, but instead making existing functionality easier to use. 10:48 We could calculate the size of our linked list by traversing it every time using 10:54 a loop until we hit a tail node, but doing that every time is a hassle. 10:58 Okay, so we'll call this method size, and as always, it takes (self). 11:04 Unlike calling len on a Python list, not to be confused with a linked list, which 11:10 is a constant time operation, our size operation is going to run in linear time. 11:15 The only way we can count how many items we have is to visit each node and 11:20 call next until we hit the the tail node. 11:25 So we'll start by getting a reference to the head, we'll say current = self.head. 11:28 Let's also define a local variable named count with an initial 11:34 value of 0 that will increment every time we visit a node. 11:38 Once we hit the tail, count will reflect the size of that list. 11:43 Next, we'll define a while loop that will keep going until there are no more nodes. 11:47 So we'll say, while current. 11:52 While current is the same as writing out while current != None, but 11:54 it's more succinct, so we'll go with this former. 11:59 If the latter is more precise for you, you can go with that. 12:03 Now inside this loop, we'll increment the count value. 12:07 So count + = 1. 12:10 +=, if you haven't encountered it before, is the same as writing count = count + 1. 12:12 So if count is 0 initially, so it's 0 + 1 is 1, and 12:17 then we'll assign that back to count. 12:21 Okay, so count + = 1. 12:23 Next we're going to assign the next node in the list to current. 12:26 So current = current.next_node. 12:31 This way, once we get to the tail and call next_node, 12:34 current will equal None and the while loop terminates. 12:39 So at the end we can return count. 12:44 As you can see, we need to visit every node to determine the size, 12:46 meaning our algorithm runs in linear time. 12:52 So let's document this. 12:55 Up in our document string, which we'll add now to size, 12:57 we'll say, Returns the number of nodes in the list. 13:02 Take linear time. 13:06 Let's take a break here. 13:08 We can now create lists, check if they're empty and check the size. 13:09 In the next video, let's start implementing some common operations. 13:13
You need to sign up for Treehouse in order to download course files.Sign up