• Post Reply Bookmark Topic Watch Topic
  • New Topic

Linked Lists in Java  RSS feed

 
Kevin Olome
Ranch Hand
Posts: 44
1
Android Firefox Browser Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, in school we are currently programming a linked list in java.

I currently don't understand how the node's work.



Why do I make private Node<AnyType> next;
What does this do?

And why do I have an inner class of Node for a linked list?
I had the same topic in C, but there it was somehow easier than in java. Because there you have pointers.


Thanks in advance for your answers ;)
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kevin Olome wrote:Why do I make private Node<AnyType> next;
What does this do?

It points to the next Node in sequence, whatever that is, or (usually) contains null if there is no "next" Node.

And why do I have an inner class of Node for a linked list?

Well, first up: What you've shown, even if it is defined inside another class is not an "inner" class, it's a nested class (because it's static).

Second: it doesn't have to be defined that way. However, it kind of makes sense, since this particular Node class only really has any meaning in the context of your list.

I had the same topic in C, but there it was somehow easier than in java. Because there you have pointers.

If it was defined as:
private *Node<AnyType> next;
would that make it any clearer for you? Because that's basically what you're doing, even if it doesn't "look" like it.

Java references are basically like pointers; the main differences being:
1. You don't have all those nasty '*'s to worry about, because all Java object types ARE references. You never actually deal with Java objects directly.
2. You can't do anything with them (eg, arithmetic).
3. You can't allocate arbitrary space for them (as with malloc/calloc).

HIH

Winston
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The 'next' field is actually a 'reference' to a Node. This is usually handled as a c-style pointer behind the scenes, but one where 'the contents of' (*pointer) is all you get access to in Java. You cannot perform pointer arithmetic but in your Node example you can get to the next Node by: next = next.node.

This might be helpful:
http://programmers.stackexchange.com/questions/141834/how-is-a-java-reference-different-from-a-c-pointer
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't call the formal type parameter AnyType. Call it something short like T or E. Then you can see immediately that it refers only to a notional type rather than a specific type.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pencil and paper. Draw a diagram.

Draw a series of squares each with two little black spots in. 3 or 4 squares will suffice. Label one T value (or T data or similar). Label the other one next. Then take the next square and draw an arrow from it pointing to the “next” spot in the square you have just finished.
When you come to the end of the series, go a little way beyond the last square and right “null” with an arrow to the “next” spot in the last square.

You will probably find that diagram helps you. It also warns you that the last Node has a null reference. That null is unavoidable but needs to be considered when you traverse the list. Had you used my class with a previous reference (a doubly‑linked list) you would have arrows pointing the other direction, too.

There is a very similar diagram on this Wikipedia page; the numbers represent the data and the ☒ represents the null at the end.
 
Kevin Olome
Ranch Hand
Posts: 44
1
Android Firefox Browser Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the helpful replies.

I slowly understand how the singly linked list works.

Trying to understand what this code means: (Inserting a new node at the first place in the list)
Picture:
Image




 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kevin Olome wrote:Trying to understand what this code means: (Inserting a new node at the first place in the list)

It looks to me like your list has two "nodes" that it points to - which you haven't illustrated in your diagrams - 'first' and 'end'. And I suspect that 'end' is meant to point to the last Node in the list.

So: if you're adding the first Node, then 'first' and 'end' will both point to the same Node. Any other time it'll depend on what you're doing; but I'd say that a better name for the method you've written would be insertAsFirst() (or possibly push()), since that's what it's doing.

Presumably, you'll then also want a insertAsLast() (or append()) method, which will be slightly different.

It might be worth mentioning that linked lists can also be implemented as "rings" - ie, end.next points to first - which saves some code (and actually makes 'end' redundant), but can also be more difficult to "visualise"; so don't worry about it too much just yet.

HIH

Winston
 
Kevin Olome
Ranch Hand
Posts: 44
1
Android Firefox Browser Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks so much for you help.
I think I can solve the rest of the exercise alone.

 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kevin Olome wrote:Trying to understand what this code means: (Inserting a new node at the first place in the list)

Just FYI: I don't know whether you were given that code, or wrote it yourself; but there is a much simpler way of doing an "insert first" that uses your
public Node(T data, Node<T> next)
constructor:HIH

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!