Java Util Linked List - how to find next?

Question

When using Java LinkedList how do you find out the element's next or previous relationships?

I mean, in a regular linked list I would do something like this:

Node node1 = new Node();
Node node2 = new Node();
LinkedList list = new LinkedList();
list.add(node1);
list.add(node2);
//then my node1 will know who it's next is:
assertEquals(node2, node1.next());

where Node is my own container for data/object.

But in Java's LinkedList, the data does not seem to be modified. So how do I actually find out who the "next" (or "previous" in the case of doubly-linked lists) element is?

• Anon.: What would happen if I went list.add(node1); list.add(node1);?
• SyntaxT3rr0r: Java's LinkedList is a bit of a misleading misnomer for people who've learned about "linked list". It's not the only misleading or, at least, poorly named thing in Java ("Concurrent modification exception" comes to mind too). But of course you can expect comments from Java-kool'aid drinkers that believe that everything the Java gods created is perfect to explain you why LinkedList is really a comp-sci linked list and why I'm stupid and all ;)
• maaartinus: There's a lot of bad and terrible things in Java, but both LinkedList and CME are quite OK. Unless you want to name it like ListImplementedAsDoubleLinkedList and YouOrSomebodyElseHadModifiedYourCollectionInTheMeantime, I don't know how to name it. That's said, I agree that a better name would be nice, I just can't find any.

Answer 1

You can't. LinkedList is just an implementation of List and offers about nothing more. You'd need to make your own.

For node1.next() you'd need a reference from node1 to the List. Actually, you'd need multiple references, since node1 may be there multiple times. Moreover, it may be contained in multiple Lists.

Maybe you can use ListIterator for this.

• Andriy Drozdyuk: That is rather sad, as I was hoping for a "linked list" implementation. Oh well, I'm going to roll my own.
• Stephen C: @drozzy - alternatively, take a second look at what you are doing and see if you can implement it better if you don't think in terms of next and prev pointers.
• Andriy Drozdyuk: I wish, but I am implementing a Range Tree, which requires a doubly-linked list of it's leaves.
• maaartinus: @drozzy Wouldn't Guava's RangeMap do?

Answer 2

I don't know what Node class you're using, but LinkedList<T> has its own internal node class, which you don't get access to. Calling add will add a value to the list - you can't explicitly insert a node holding a value, or access the nodes themselves in any other way. Yes, that can be a pain sometimes.

If you need a linked list with a public encapsulation of the node as well, you'll need to find a different implementation or roll your own.

• Andriy Drozdyuk: Sorry, Node was my own imaginary container for the data. I would say java's LinkedList is not suitable for me in this case.

Answer 3

Best Solution: Make your own next and last Links when constructing an new List Item Object:

Just have a lastInserted Object somewhere more globally

public MyLinkedListItem(){
 if(lastInserted != null){
 lastInserted.next = this;
 this.last = lastInserted;
 }
 lastInserted = this;
}

Answer 4

You can use an iterator to move through the nodes such as:

 Node node1 = new Node();
 Node node2 = new Node();
 LinkedList list = new LinkedList();
 list.add(node1);
 list.add(node2);
 Iterator <Node> m_iterator=list.iterator();
 //set iterator to first node
 m_iterator.next();
 //then my node1 will know who it's next is:
 assertEquals(node2, m_iterator.next());

• shabunc: with iterator of this kind one would be able to move only in one direction with devalues the very idea of using some kind of linked list.
• MikaelF: @shabunc ListIterator also has hasPrevious() and previous() methods that you can use to traverse the list backwards.

Answer 5

The "linked" part of the LinkedList class name only refers to its implementation. The interface does not expose explicit methods to do what you want.

LinkedList implements the Collection (and List) interface, so given an index i of an element in the list list, you can get previous and next elements with list.get(i-1) and list.get(i+1), respectively. For a LinkedList, the implementation of these methods are quite slow. If you do a lot of prev/next operation, consider to implement your list or to use an ArrayList instead.

• Andriy Drozdyuk: Yeah, so much for the "linked" list.

Answer 6

I have to disagree with the accepted answer. You can as long as you have the head element. Once you lose reference to the first element by deleting and not returning the next element or insert an element before the first element and not return it, you will not be able to do your searches.

• maaartinus: This makes no sense to me. Let the first element be "f", find what comes next after the element "e".