Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science Introduction to Data Structures Building a Linked List What Is a Linked List?

Teacher Russell
Teacher Russell
16,873 Points

linked list next_node

Probably a stupid question, but..... What exactly is "next_node" here, or in Java "next"? It's never been clear to me how these words are recognized for what they are. I've heard next referred to as "belonging to the node class", but can't find a single reference to it in the docs. Do head or next have any meaning, or are they just the common terms used, and if so,............does any of this babble make my confusion clear? I've read everything I can find on linked lists, and watched every tutorial on youtube and still have no idea how this works. Can there only be 2 elements in a node, so one is reference to the data inserted and the other is next by default?

3 Answers

andren
andren
28,526 Points

Do head or next have any meaning, or are they just the common terms used

The words them self have no special effect. In this video next_node is just an attribute of the Node class. An as with any other attribute it can be named anything you want. If you replace all usages of next_node in the code with abc then the code would still work fine. So yes, the names are entirely based on convention.

Most languages do not care what you name a variable or attribute, they are just labels that make it easier for programmers to keep track of their use. The functionality of next_node comes entirely from the code you write, not from its name. And this is true for pretty much all functionality in programming.

Can there only be 2 elements in a node, so one is reference to the data inserted and the other is next by default?

Yes, essentially. Linked list are an extremely simple list structure. You have a head which will point to the first Node inserted, and then each node will contain some data and a reference to the next node, or None if no next node exists.

That means that in order to traverse through them you have to start at the head and then follow the next_node attribute until you hit one that contains None. Because of this there is no simple way to pull out an item at a specific index like you might be used to with traditional lists. If you want item 5 you still have to start at the head and traverse though the nodes in order to find that item.

One way to think about linked lists is like a series of train cars. A train has a head (the locomotive) and a set of cars attached to it. Each car is attached to the back of another car. If you wanted to get to car 5 from the locomotive you would need to manually traverse each of the cars that came before it.

And if you wanted to insert a car somewhere, lets say at the start, you would have to detach the currently attached car attach it to the new one, then attach the new one to the locomotive. This is essential the same thing you would do in a linked list. You would make the head point to a new Node and then set that node's next_node attribute to the node that used to be assigned to the head.

andren
andren
28,526 Points

Java doesn't know what next is, but it doesn't need to. Your code defines the Node class, and you write all of the methods that interact with and provide the behavior of the linked list. As long as you (the programmer) understands how it works and uses that knowledge when writing the methods then it doesn't matter whether Java itself has any understanding of how linked lists work.

In reality most languages don't understand all that much, they have some predefined behavior and keywords but in the end they are just designed to parse code written by programmers. As a programmer it's your job to explain (through code) exactly how it should behave and work. Java itself doesn't really "think" about the code it executes, it just blindly parses it.

Alex Koumparos
seal-mask
.a{fill-rule:evenodd;}techdegree
Alex Koumparos
Python Development Techdegree Student 36,862 Points

Hi Russell,

The linked list is a (at least for Python, and perhaps Java) custom data structure, not built in to the language (compare to Python's lists or Java's arrays which are data structures that are built in to the language).

However, although the linked list is not part of the language, it is a long-standing data structure in computer science and so there is a generally established set of terms to describe the components of the data structure, and how they fit together.

A linked list can be thought of as a chain of data objects. Each object has only two properties: its own value and where to find the next link in the chain. We call the objects 'nodes' and thus the link to the next object is the 'next node'.

Compare this to an array, where each element in the array only has a single property: its value (the positions of all the elements in the array is a property of the array itself, not the array element).

I'm not sure if this gets to your confusion, if you're still struggling let me know which parts of the above don't make sense and I'll try to clarify further.

Cheers

Alex

Alex Koumparos
seal-mask
.a{fill-rule:evenodd;}techdegree
Alex Koumparos
Python Development Techdegree Student 36,862 Points

Hi Russell,

So, there can ONLY be 2 properties, and one must be the data, and one must be a Node, which is expected to be/must be the pointer to the next Node? That's the only thing I'm confused about.

There can be as many properties as you want to add to the node, but those are the minimum properties for an object to function as a linked list node.

How we know that .next is pointing at the next node. Is it that it CANNOT be anything else? Or, are we using next() without brackets. I know what next represents, but confused about what makes next next:) Thanks for your help!

In the simplified example we use to illustrate the concept of a linked list there is no guarantee that the object that will be passed into the initialiser to create next_node will actually be the next node. We're trusting that the user who is constructing the linked list will only pass a true next node into the constructor. This is especially true for the Python example where we can pass literally anything to __init__(). At least with Java, the type checker will ensure that only valid Node objects can be passed into the constructor. Whatever valid Node object gets passed as the next argument will, by definition, be the next node (regardless of whether the user actually intended that particular Node instance to be the next node).

I hope that clears everything up for you

Cheers

Alex

Teacher Russell
Teacher Russell
16,873 Points

I think I'm clear on the fact that I'm over tired. You may have me closer than ever to realizing that I do understand what I think I'm confused about, and just need to take a long break:) I've been at this 6+ hours a day. Maybe too much for my old brain. Thank you very much!