How to implement an iterator for a custom doubly linked list implementation?

Question

I'm implementing a custom doubly linked list in Java and I don't know exactly how to implement an iterator for it so that it can for example be easily iterated using a foreach (enhanced for) loop.

I basically want to be able to get the next or previous element with something like the code below, where it starts from a given Node and then continues to get the "next" (or "previous") element in the node variable. I want it to stop once "next" is null (which obviously will be handled by "hasNext"). I know that the approach below might not strictly make sense from a Java perspective because what I'm searching for is a for loop that does not loop through a Collection but logically it makes sense.

for (Node node : firstNode)

Otherwise I would need to do something like

Node node = getFirstNode();
while (node != null) {
   //do stuff with current node
   node = node.next;
}

The reason I don't want to use java.util.LinkedList is because of the lower amount of memory that will be used with the custom approach. Basically I also need the "next" and "previous" references in a Node so that I can easily access them with just having the Node at hand. If I would go with the java.util.LinkedList approach for each Node additionally I would need to keep an integer index to indicate at which index the object is located in the list and then be able to access "next" or "previous" or edit the list at that location in O(1) time.

Note that I would still prefer the java.util.LinkedList approach If there is a way to get away without needing the indexInList variable in the Node itself

@Joni because I also want to be able to get the "previous" and "next" object with just looking at the Node itself (without finding it in the actual java.util.LinkedList and then looking at "previous" or "next"). I want to avoid doing a search. — Jordan Jordanovski
– Jordan Jordanovski, Commented Jul 20, 2020 at 12:14
Why you don't implement the listIterator interface? Then you can do your custom next/previous. Then if you implements iterable, you will be able to use foreach. — Olf
– Olf, Commented Jul 20, 2020 at 12:31
You know that even with an index you still need to search right? There's no O(1) element access with linked lists — Joni
– Joni, Commented Jul 20, 2020 at 12:37

Not a bug · Accepted Answer · 2020-07-20 12:45:07Z

2

Here is a very basic implementation of Iterator for a linked list that only iterates forward using the next pointer:

class NodeIterator implements Iterator<Node> {
    Node current;

    public NodeIterator(Node firstInList) {
        this.current = firstInList;
    }

    @Override
    public boolean hasNext() {
        return current != null;
    }

    @Override
    public Node next() {
        Node savedCurrent = current;
        current = current.next;
        return savedCurrent;
    }
}

To be able to use the enhanced for loop syntax, your custom linked list has to implement the Iterable interface. That interface has just one method, which creates a new iterator:

class LinkedList implements Iterable<Node> {
    Node first;
    @Override
    public Iterator<Node> iterator() {
        return new NodeIterator(first);
    }
}

For reference, the Node class:

class Node {
    Node next;
   // add other fields you need
}

edited Jul 20, 2020 at 12:45

Not a bug

4,3342 gold badges43 silver badges82 bronze badges

answered Jul 20, 2020 at 12:36

Joni

112k14 gold badges151 silver badges201 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to implement an iterator for a custom doubly linked list implementation?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related