🤑 Join the Treehouse affiliate program and earn 25% recurring commission!

New No-Code Track! 🚀start learning today!

🌟 Dreaming of a bright future? 🎓 Ask about the Treehouse Scholarship program! 🚀

✨ Earn college credits in Cybersecurity, JS, HTML, CSS and Python

Well done!

You have completed Introduction to Data Structures!

Sign up for Treehouse Back to Library

Preview

Sign up for Treehouse Continue

Adding Nodes to a Linked List

7:50 with Pasan Premaratne

In the previous video we created the outlines of a linked list but without the ability to add nodes it's not really a list. Let's define an add operation to prepend nodes

Teacher's Notes
Questions?
Video Transcript
Downloads
Workspaces

Code Snippet for repr Function:

def __repr__(self):
  """
  Returns a string representation of the list.
  Takes O(n) time
  """

  nodes = []
  current = self.head

  while current:
    if current is self.head:
      nodes.append("[Head: %s]" % current.data)
    elif current.next_node is None:
      nodes.append("[Tail: %s]" % current.data)
    else:
      nodes.append("[%s]" % current.data)

    current = current.next_node

  return '-> '.join(nodes)

Related Discussions

Have questions about this video? Start a discussion with the community and Treehouse staff.

Sign up

Related Discussions

Have questions about this video? Start a discussion with the community and Treehouse staff.

Sign up

At the moment, we can create an empty list, but nothing else. 0:00

Let's define a method to add data to our list. 0:03

Technically speaking, there are three ways we can add data to a list. 0:06

We can add nodes at the head of the list, 0:09

which means that the most recent node we created will be the head. 0:12

And the first node we created will be the tail or we could flip that around. 0:16

Most recent nodes are the tail of the list and 0:20

the first node to be added is the head. 0:22

I mentioned that one of the advantages of linked lists over arrays 0:25

is that inserting data into the list is much more efficient than to the array. 0:28

This is only true if we're inserting at the head or the tail. 0:32

Technically speaking, this isn't an insert, and 0:36

you'll often see this method called add prepend if the data is added to the head 0:39

or append if it's added to the tail. 0:43

A true insert is where you can insert the data at any point in the list, 0:46

which is our third way of adding data. 0:50

We're gonna circle back on that if we wanted to insert at the tail, 0:52

then the list needs a reference to the tail node. 0:56

Otherwise, we would have to start at the head and 0:59

walk down the length of the list or traverse it to find the tail. 1:02

Since our list only keeps a reference to the head, 1:05

we're going to add new items at the head of the list. 1:09

Now before we add our new method, I forgot that I didn't show you in the last 1:13

video how to actually use the code we just added and 1:17

how to check every time when we add new code that it works correctly Directly. 1:20

So like before, we're going to bring up the console and 1:25

here we're gonna say python -i linked_list.py, 1:29

which should load it, load the contents of our file. 1:34

And now we'll start here by creating a linked list, so l =LinkedList(), 1:38

and then we'll use a node, so N1 = Node with the value 10. 1:44

And now we can assign N1 to the nodes or to the LinkedList's head attribute. 1:49

So l1.head = N1. 1:55

And then, we can see if size works correctly. 1:58

So if we call l1.size and since this is a method, 2:02

we need a set of parenthesis at the end. 2:05

Enter. 2:07

You'll see that get that one correctly. 2:08

Okay, so it works! 2:10

Now, let's add our new method, which we're going to call add. 2:11

Add is going to accept some data and add to the list inside of the node. 2:18

So we'll say def add(). 2:24

And every python method takes self as an argument. 2:26

And then, we want to add some data to this node, so we're gonna say data for 2:29

the second argument. 2:34

Inside the method, first, we'll create a new node to hold on to the data. 2:35

So new_node = Node(data). 2:39

Before we set the new node as the head of the list. 2:44

We need to point the new node's next property 2:47

at whatever node is currently at Head. 2:50

This way when we set the new node as the Head of the list 2:54

we don't lose a reference to the old Head. 2:56

So new_node.next node = self.head. 2:59

Now, if there was no node at head this correctly sets next node to none. 3:06

Now we can set the new node as the head of the node. 3:12

So say self.head = new_node. 3:16

Because the insert operation is simply a reassignment of the head and 3:19

next node properties, this is a constant time operation. 3:25

So let's add that in as a down string. 3:30

First, what the method does. 3:34

So it adds a new node containing data at the head of the list. 3:37

This operation takes constant time which is our best case scenario. 3:46

Okay, let's test this out. 3:52

So we're gonna bring the console back up. 3:54

We'll exit out of our current level and 3:56

we'll load the contents of the file again, and 4:01

now we don't need to create a node like we did earlier. 4:05

So we can say l = LinkedList. 4:08

l.add(1). 4:11

Okay, let's see if this works. 4:13

We'll call size. 4:15

And if it worked, then linked list should now have a size of 1. 4:17

There we go. 4:23

You can also do l.add(2), l.add(3) and l.size should now be 3. 4:24

There we go. 4:30

If I were to type l and 4:32

just hit print, again, what we get in the repl is nothing useful. 4:33

So like before we'll implement the repr function for our linked list. 4:39

Now, I'm just going to copy paste this in and we'll walk through it. 4:44

Okay, so this is what our implementation of repr looks like for 4:49

the linked list object. 4:53

You can grab this code from the note section of this video. 4:55

Okay, so at the top you'll see a doc string where it says it returns a string 4:59

representation of the list. 5:02

And like everything we need to do with a link list we need to traverse it. 5:04

So this is going to take linear time. 5:08

We start by creating an empty list. 5:10

Now, I need to distinguish this is python list not linked list. 5:12

So we create an empty list called nodes, and to nodes we're going to add strings 5:16

that have a description, that provide a description of each node. 5:21

But we're not going to use the description that we implemented in the node class, 5:25

because we're gonna customize it a bit here. 5:29

Next, we stand by signing self.head to current. 5:32

So we sort have a point to the head node. 5:35

As long as current doesn't equal non, 5:39

which mean we not added the tail we are going to implement some logic. 5:41

So in the first scenario, if the node assign to current is the same as the head. 5:45

Then we're going to append this string to our nodes list. 5:50

And the string is simply going to say that hey, this is a head node. 5:54

And it contains some data, which we'll extract using current.data. 5:59

The next scenario is if the node assigned to current next node is none, 6:04

meaning we're at the tail node, then we'll assign a different kind of string. 6:08

So it's the same as over there except we're saying tail here. 6:13

And then finally, in any other scenario which means we're not at the head or 6:16

not at the tail we'll simply print the nodes value inside. 6:20

And again, we'll extract it using current.data. 6:23

With every iteration of the loop will move current forward by calling 6:26

current.next_node and reassigning it. 6:30

And then in the very end when we're done, we'll join all the strings 6:32

that are inside the nodes list together using the python join method. 6:37

And we'll say that with every join. 6:41

So when you join these two strings together to make one string, 6:44

you need to put this set of characters in between, all right? 6:47

So let's see what this looks like. 6:51

So I'm going to come down here, exit out of the console again, 6:52

clear it out, load the contents of the file again, and let's try that. 6:55

So we'll say l = LinkedList. 7:00

All right, so l.add1, l.add2, l.add(3). 7:04

That seems enough. 7:10

And then now if I type our l and hit enter, 7:11

we get a nice string representation of the list. 7:14

So you can see that we add every new node to the head. 7:17

So we added one first. 7:20

One ends up being the tail, because it keeps getting pushed out. 7:22

Then 2, and then finally 3, so 3 is at the head. 7:25

So far we've only implemented a single method which 7:29

functions much like the append method on a python list or an array, 7:33

except it adds it to the start of the length list. 7:38

It prepends it. 7:41

Like a pen, this happens in constant time. 7:43

In the next video, let's add the ability to search through our list. 7:47

You need to sign up for Treehouse in order to download course files.

Sign up

You need to sign up for Treehouse in order to set up Workspace

Sign up