Original subtitles

- [Instructor] A common algorithm is called a Link List.

And sometimes you might hear technical definitions such as;

it's a linear collection of data elements called nodes.

Each pointing to the next node by means of a pointer.

But really, if we're talking straightly,

it's a collection of items like arrays,

but with less limitations.

For example, there are some cons to using arrays.

Slots in arrays can't be increased.

If you have 50 slots, you can't just add 51.

What you have to do, is to recreate a larger one

and then copy over the data, and that's inefficient.

Also, you can't insert items into an array

without having to do extra work

to reassign all the items over.

Arrays have fixed size with these limitations.

But for Linked List, you don't have this.

You can insert data in the beginning, in the middle,

or the end of the list.

These box combinations are referred to as nodes.

The three with the blank box right next to it,

that's one node.

The five with the blank box next to it, that's one node,

and so forth.

The beginning of the list is referred to as the head.

And the end is referred to as the tail.

If we were to have an analogy of a train,

you could think of each car below as a node.

They contain the data that you want.

And that's what we call them in a Linked List, nodes.

You can add and remove as many nodes as you want.

In our Linked List, each node points to another node,

or it's null, such as the last node.

Here, if we wanted to drop the five,

we can point three to four.

If we're looking at the node here with three,

when coding, the way we create class definitions

is by thinking of each node as an instance of a node class.

Just like here.

The class definition of node

would contain two instance variables.

One of type integer for the number.

That's where the data is.

And the other, where you see the word next, is of type node.

And that points to the next node.

Just like how we see next is pointing

to data in these nodes.

Let's go ahead now and just jump into some code

to demonstrate this.