remember when i mentioned overhead problems with doubly linked lists on this post. i've said there's a hack around to solve this problem which is using xor(for more about xor and other bitwise operators, see this post).

as always we define node class

  class Node {
    int data;
    Node link; // only one pointer
  }

so for example let's define a traverse method.

  void traverse() {
    Node prev = null;
    Node cur = head;
    while(cur != null) {
      System.out.print(cur.data + " ");
      Node temp = cur;
      cur = cur.link ^ pointerAddress(prev);
      prev = temp;
    }
  }

and an insert method.

  void insert(int data) {
    if(head == null)
      head = new Node(data);
    else {
      Node a = new Node(data);
      head.link = head.link ^ pointerAddress(a);
      head = a;
    }

pointerAddress is not defined. we would have to use "sun.misc.Unsafe" library which is unsafe 'cos type-checking is not performed. this is almost useless besides garbage collector knows nothing about the items we've just inserted. memory is cheap nowadays, but it's fun anyway. if you're really curious about implementing one in java, here's one.

to understand easily how in-place swap, and doubly linked list with one pointer work, here are the properties of XOR.