public class Test {

  public static void main(String args[]) throws Exception {
    XORLinkedList l = new XORLinkedList();
    l.put(9);
    l.put(8);
    l.put(7);
    l.put(6);
    l.debug();
    l.traverseForward();
    l.traverseBack();
  }

}

public class XORLinkedList {

  private final int SIZE = 10;
  private int[] data; // data nodes
  private int[] link; // corresponding links
  private int valCount; // how many items
  private Random random; // rng
  private int head, tail; // pointers to first and last item

  XORLinkedList() { // make a new empty list
    data = new int[SIZE];
    for (int i = 0; i < SIZE; i++) {
      data[i] = -1; // codes empty slot
    }
    link = new int[SIZE];
    valCount = 0;
    random = new Random();

  }

  public void put(int val) {
    // add val to linked list, linked to current tail
    // is it full?
    if (valCount == SIZE) {
      return; // throw exception really
    }
    // not full..
    int where; // where to put it
    do {
      where = random.nextInt(SIZE); // random location
    } while (data[where] != -1); // until find empty location
    data[where] = val;
    if (valCount == 0) // insertion in empty list
    {
      head = where;
      tail = where;
      link[where] = 0 ^ 0;
    } else {// setup link to previous end
      int linkEnd = link[tail]; // previous tail link
      linkEnd = linkEnd ^ 0; // get index
      link[tail] = linkEnd ^ where; // make new link
      int lastTail = tail; // move on
      tail = where; // new tail
      link[tail] = lastTail ^ 0; // set its link
    }
    valCount++;
  }

  void traverseForward() {
    int where = head; // start at head node
    int previous = 0; // the previous node visited
    int next;
    do {
      System.out.println(data[where] + " link=" + link[where] + " at:" + where);
      next = previous ^ link[where]; // find next
      previous = where; // prepare previous
      where = next; // move on
    } while (previous != tail); // until we visited tail

  }

  void traverseBack() {
    int where = tail; // see traverseForward
    int previous = 0;
    int next;
    do {
      System.out.println(data[where] + " link=" + link[where] + " at:" + where);
      next = previous ^ link[where];
      previous = where;
      where = next;
    } while (previous != head);

  }

  void debug() { // output both arrays for debugging
    System.out.println("Head = " + head);
    System.out.println("Tail = " + tail);
    for (int i = 0; i < SIZE; i++) {
      System.out.println(i + " " + data[i] + " " + link[i]);
    }

  }

}