Traversing a LinkedList tail to head

Question

I need to traverse through this custom linked list implementation and display its contents:

• from head to tail,
• then again from tail to head.

---

I was able to display the lists contents from head to tail pretty easily with a for loop:

        for (AccountRecordSerializable account : list) {
            System.out.println(account); 
        }

and everything works fine. Now I am trying to reverse that. In provided LinkedList class to use which has a LinkedListIterator class inside it as well. The iterator class has methods such as hasNext(), hasPrevious() which I know can be used to do so, but I'm not quite sure how to use that iterator through my LinkedList to do so.

Is there a simpler way as I had done before to reverse this? Or how would I use the Iterator class to iterate through my list so that it performs the task?

I apologize if this doesn't make any sense... let me know if you need clarifications..Thanks.

Answer 1

The Java LinkedList implements interface Deque that provides method descendingIterator.

Returns an iterator over the elements in this deque in reverse sequential order. The elements will be returned in order from last (tail) to first (head).

My advise for you is to implement that interfaces in your class, and the obtain reversed iterator.

The linked list is data structure with some properties that you should use to get the implementation. The typical construction of linked list is that an element points to next one. In your case you have implementation that supports double linked list.

private int size = 0; // size can never be < 0
private DLNode<E> head;
private DLNode<E> tail;

In your code you have DLNode that stand for Double Linked Node. This means that you can move from head to tail by using hasNex() and from tail to head using hasPrevious().

In your class you have the class LinkedListIterator, that you can obtain with this method:

 public ListIterator<E> listIterator(int index) {
    if ((index < 0) || (index > size)) {
        throw new IndexOutOfBoundsException("index " + index+ " is out of range: 0 to " + size);
    }
    return new LinkedListIterator<E>(index);
}

So to print your elements you could do it like this.

 public <T> void printLinkedListFromHead(LinkedList<T> list) {

   for(ListIterator<T> iterator = list.listIterator(0); iterator.hasNext();) {
       System.out.println(iterator.next());
   }

 }

You should also create a separate class for your code, where you will put your code that contextually does not belong to the linked list implementation. The method readObjectsand writeObjects do not belong to class. same as main.

---

If you would have standard Java LinkedList you could wrote something like this:

public <T> reversePrint(Deque deque) {

 for (Iterator<T> iterator = deque.descendingIterator(); iterator .hasNext();){
      System.out.println(iterator .next());
    }
}

To narrow the scope of iterator promote for loop than while.

Answer 2

A singly linked list is not meant to traverse from tail to head.There are couple of options you have

1. Reverse the linked list and traverse from head to tail (which will be tail to head for the original linked list)
2. Have a stack. Traverse the linked list and put the elements in the stack. Then keep popping the elements from the stack and print.

Answer 3

I've decided just to traverse backwards by assinging a cursor to the end of the list and iterating through with a get(index) which is then decremented. This is what I have:

        System.out.println("Tail to Head");
        for (int i = list.size - 1; list.get(i) != null; i--) {
                System.out.println(list.get(i));
                if (i == 0 ){
                    break;
                }
            }

I'm sure there are prettier ways to write it, but it fulfills its purpose for now.

Answer 4

Using .descendingIterator() will do what you want :)

Example:

LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);


Iterator<Integer> iterator = linkedList.descendingIterator();
while (iterator.hasNext())
{
    System.out.println(iterator.next());
}

If you want to save a new LinkedList reversed.. just

LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);


Iterator<Integer> iterator = linkedList.descendingIterator();
LinkedList<Integer> reversed = new LinkedList<Integer>();
while (iterator.hasNext())
{
    reversed.add(iterator.next());
}