The new data structure that we're going to use to implement stacks and queues,

is called a linked list.

It's a fundamental data structure with all kinds of applications,

and that's the one that's going to solve this problem for us.

So, the idea is a distinction

between sequential and linked allocation of memory to hold data.

Sequential data structure are an array,

we put all the objects right next to one another.

In your computer's memory they just go consecutively in the memory of the computer.

So, here this is pointing ahead a little

to a small machine that we're going to talk about in detail later in the course.

The memories have names,

and here the names all begin with C. And

the items are stored one after another consecutively in the memory.

It's like a Java array.

The thing is fixed size,

but you can get quickly to any item in there,

that's a sequential data structure.

A linked data structure is a different thing.

There, we're going to associate with each object a link to a different object.

In this case, what we have in the computer is

a memory address of another object and on the left

is the names where the objects are located in the memory,

and every object has associated with it,

the name of another object in memory.

So in this case, Alice is linked through the memory address to Bob,

and Bob is linked to the memory address to Carol,

and Carol's link is null so that indicates the end.

In Java, these things are called references.

That's the Java name for the memory address.

And we're going to work with Java code and then later on we're going to

talk more detail about how things are represented in a machine.

So the whole idea is that the size of the structure is variable,

is just as many links as you have.

They're not stored next to one another in memory.

And the only thing you can do is get to the next element in the memory.

The next element in the sequence each time.

Most novice programmers don't get this far.

This is the level of sophistication that's not reached by a lot of programmers.

It's not very difficult but it's quite different

than the idea of using an array to access a place in memory.

And it's an introduction to a whole new world of organizing

data and we're going to see another more important example on the next lecture.

Very flexible and it's very widely used within the system and it's important to

understand the concept of

linked data structures when it comes

to efficiently processing data and implementing algorithms.

So the very simplest linked data structures is called a linked list.

And one way to think of it is as a recursive data structure.

A linked list is either null or a reference to a node,

and a node is a data type that has a reference to a node.

So if we unwind that recursion,

we can say a linked list is a sequence of nodes,

or it's a node followed by a linked list as a number of ways to unwind that recursion.

So what we do to represent a linked list is

use a private class node to implement the node abstraction.

First this is a little complicated,

but it's actually very simple and we use

this one construct to create all different types of data structures.

So taking the time to understand it in this simple context is worthwhile.

So we're going to start with nodes just having two values,

a string and a node.

And we can add generics to the code and so forth later.

But let's just work with,

a node is a data type that has a string with it and

then it's got another value which is a reference to another node.

And that's what that data type is.

So we're going to use this as a nested class within our code,

so we can refer directly to these variables item and next in any given node.

So it's a string and a reference to another node.

And so this diagram shows abstraction of a linked list built from nodes.

First as a variable,

that's a reference to a node.

That node, its item got the string

Alice and its next is a reference to another node which contains Bob and so forth.

That's an example of

a linked list and we're going to use a Java code like that to build a linked list.

Now even with just one link like this,

a value linked to another node.

Things can get pretty complicated and we talked about this simple one but you could

have multiple nodes pointing to a given node that creates a structure called a tree.

Or it could be circular or you could get a rho shape or

in general you could get a pretty complicated mathematical shape.

This just indicates how powerful this abstraction is.

We're going to stick for now just with the simplest linked list.

So the thing is from the point of view of any particular object,

the data structure could be any one of these things.

We have to ensure in our code that we have the simple one.

Next time we're going to talk about structures that have

more than one link and then brings a lot more possibilities.

Very powerful concept, the idea of structuring data with links.

So let's look at the what the Java code that creates a linked list might look like.

And again, we've got abstract representation of what

the memory of the computer might be like over on the right.

So we've got a variable third,

that's of type nodes,

that's going to be a reference to a node.

We say that's a new node,

then Java's going to allocate two spaces for it.

One actually be a reference to a string but in the example we'll just put the string in,

and the other would be a reference to a node.

So if we say third dot item equals Carol,

we can refer directly to item,

given the variable because we're using an inner class.

On third next equals null,

again it would be a reference to the string Carol and will be more complicated,

but let's think of it in this way.

That's what we're going to get.

It's a node with a variable that's a reference to a node,

that node contains a string and another reference,

in this case it's null.

Or in our diagrammatic representation,

that's what we've got so far.

So now let's create another new node.

Now the system decides where it's going to be in memory and just returns a reference.

And yes C9,CA,CB you'll understand what that means in a couple of lectures.

So, second.item = ''Bob'';

and second.next = third.

So this is linking the node containing

''Bob'' in front of the node containing ''Carol'' in the list.

So now we have second points to ''Bob'' which then refers to ''Carol''.

And how do we get that link to Carolynn there?

That last line second.next = third.

Third's a reference to the node containing ''Carol''.

Second.next is a reference to the node

following ''Bob'' and that simple code gets that done.

And again if we want to put another one in,

first = new Node, that's ''Alice''.

And then we say first.next = second;

that links ''Alice'' in front of ''Bob''.

That's the example of code for building a linked list.

We're not going to write a lot of code like this,

but we're going to write some code like this.

And the point is that,

with the ability to manipulate links

and references we can build rather complicated data structures.

So, before higher level languages

like Java where people were writing in much lower level languages,

building list was done with lower level code and there's a lot of

standard operations developed for

processing data that's structured as a singly-linked list.

So, like one thing you might want to do is add a new node at the beginning,

or remove and return the node at the beginning,

or add a node at the end.

Well, actually you need a reference to the last node in order

to be able to add a new node at the end so it can always do it.

Or traverse the list,

visit every node in sequence.

And for many years,

we would teach in

introductory programming courses quite a bit about writing code of this type.

Sometimes we might have a doubly-linked list which we're not going to

do where each node points to the one after it and the one before it in the list.

In that one you can maybe remove and return

the node at the end and other types of operations.

So let's look at what these first couple of

basic operations look like with just a singly-linked list.

How about remove and return the first item in a linked list.

Well, we can get the item,

the string, by just first start item,

and we'll put that in a variable.

And so now we have that first item stored away.

So now how do we remove it from the list?

Is actually very easy.

Just say first = first.next, and that will,

the first refer to the same place

that ''Alice's'' next fear was referring to, and that's ''Bob''.

And what's really significant about this is it leaves no reference to ''Alice''.

In Java, that's no problem.

That's precisely what Java's garbage collection system is for.

Eventually, Java will find that memory and reclaim it for later use.

And then we just return item.

So, three lines of code we can remove and return the first item in a linked list,

a very simple code.

And what we're left is with the list that just has the later two items.

What about adding an item to the beginning of a linked list?

Well, it's just manipulating

the few pieces of data that references that we have available.

So, we're going to say that after we're done with this,

the ''Alice'' is going to be the second list, second node in the list.

So, we save that away second = first.

And to put ''Dave'' in,

we're going to need a new node.

So first = new Node(); And so,

that we've got first is new node,

and then we get the rest of the list pointed to by second.

So we fill in the new node first.item = item.

That puts ''Dave'' in and first.next = second.

Now we've got a linked list,

and the second variable is no longer relevant.

But it's critical that we held on to that before we reset first to be new node.

If we hadn't done that, there'd be no way to access anything in the list.

That's the kind of challenge that we face in developing this processing code.

What about traversing a list?

Visiting every node on a list.

Well, that's just a simple while loop,

we could do it in a for loop as well.

x = first, while x is not null,

printx.item and set x to x.next.

Printx.item and set x to x.next.

Just moves right through the list if not null,

print out the list in order.

So that's three examples of operations on linked lists that are easy to code.

So, let's look at a couple of pop quizzes and I'll not address these directly.

I'll leave this for you to study and look at the answers.

So, here's a more complicated piece of code that processes a list,

it reads from StdIn and it does a few operations on the list and then goes through it.

The answer is, what it does is,

it winds up printing the strings from StdIn on StdOut but in reverse order.

So, it reads a man and then puts him at

the beginning of the list which winds up reversing.

Better to use a stack than this code,

although this code is kind of implicitly

within the stack implementation that we're going to look about.

So, here's the code that uses a stack to do it.

One reason we don't teach that much less processing nowadays is that

most of this kind of processing is embodied in higher level data structures like stacks.

Here's another one. And again,

this is worth a little bit of study just to cement your understanding of linked list.

This one it turns out,

puts the string from StdIn on a linked list in the proper order.

And it does that by adding nodes at

the end of the list by keeping track of the last one in the list.

Again, this kind of processing is embodied in

our queue implementation as we'll see in a bit.

So those are basic examples of code that process linked list.

Next we're going to look at how to use code like this

within an ADT implementation to actually implement the stack API.

Linked lists

Computer Science: Algorithms, Theory, and Machines

Rencontrer les enseignants