Double Chained List in Java

Question

I have to implement the classes "DoubleChainedList" and "Elem".DoubleChainedList manages a doubly chained list and Elem is the associated node class with the pointers to the successor and the predecessor.

I have to implement the following methods:

public void removeAtIndex(int i) // Removes the element at position i. If i > length-1 or i<0 throw IndexOutOfBoundsException

• public int[] toArray() // Returns the list as an array

DoubleChainedList

import java.util.Collections;
import java.util.LinkedList;

public class DoubleChainedList {

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(4);
        list.add(1);
        list.add(7);
        list.add(2);
        list.add(9);
        Integer[] arr = list.toArray(new Integer[0]);

        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

public int[] toArray() {

        Integer[] arr = list.toArray(new Integer[0]);
        return null;

    }

    public int smallest() {
        int min = Integer.MAX_VALUE;

        // Check loop while head not equal to NULL
        while (head != null) {
            if (min > head.data)
                min = head.data;

            head = head.next;
        }
        return min;
    }

Elem:

public class Elem {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

    private Node head = null;
    private Node tail = null;

    public class Node {
        public int data;
        public Node next;
        public Node prev;

    }

}

My problem: It shows me following error : head cannot be resolved to a variable and my question was how can I fix it ?

Answer 1

Your DoubleChainedList should have a head and a tail. Those are the beginning and end of the List respectively. Each node of the list, which you have been instructed to name Elem, should have a prev and a next of type Elem. Your Elem class contains another class named Node - this appears to be superfluous and will likely confuse yourself - flatten this into the Elem class.

Your smallest() method contains an error in that it is altering the list. Create a separate Elem variable to navigate the contents of the list - do not alter head or tail here.

It is misleading to return Integer.MIN_VALUE when the list is empty. Consider throwing an Exception if the list is empty instead. You will find that you will have to define special handling for the is-empty case in nearly every method the list implements.

public class DoubleChainedList {
  private Elem head;
  private Elem tail;

  // using protected here because you aren't exposing this to consumers
  // but its available for extension
  protected class Elem {
    private int data;
    private Elem prev;
    private Elem next;
  }

  public int smallest() {
    if (head == null) {
      throw new Exception("list is empty - no smallest value");
    }
    int min = Integer.MAX_VALUE;

    Elem cursor = head;
    while (cursor != null) {
      min = Math.min(min, cursor.data);
      cursor = cursor.next;
    }
    return min;
  }
}