Preview
Video Player
00:00
00:00
Adding Nodes to a Linked List
7:50In 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
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