How to build a link list in Java?

Question

Possible Duplicate:
How do I implement a Linked List in Java?

We know there is no pointers in java. Then what is the best way to build the link list in java?

Answer 1

The best way is to not build it. Java already has a LinkedList class amongst its rather large selection of collection classes.

You would be better off using what the language/library already provides.

Answer 2

You have an object that essentially contains two variables, no methods (bare minimum; however, you could have methods if you wanted). Something like:

class Link
{
   int data;
   Link next;
}

Then you create a new Link like any other object. Set the data to the data you want a node to hold. Then set the Link node to the node that it will be "pointing" to (or null if it doesn't point to another one).

Note: you can also have a previous node (which points to the previous node) if need be.

Answer 3

try having this code.

public class Main {
public static void main(String[] args) {
LinkedList theList = new LinkedList();
LinkedListIterator theItr;

theItr = theList.zeroth();
printList(theList);

for (int i = 0; i < 10; i++) {
  theList.insert(new Integer(i), theItr);
  printList(theList);
  theItr.advance();
}
System.out.println("Size was: " + listSize(theList));

}

public static int listSize(LinkedList theList) {
LinkedListIterator itr;
int size = 0;
for (itr = theList.first(); itr.isValid(); itr.advance())
  size++;
return size;
  }

 public static void printList(LinkedList theList) {
if (theList.isEmpty())
   System.out.print("Empty list");
 else {
   LinkedListIterator itr = theList.first();
   for (; itr.isValid(); itr.advance())
    System.out.print(itr.retrieve() + " ");
  }
  System.out.println();
}
}

class LinkedList {
 public LinkedList() {
header = new ListNode(null);
 }

public boolean isEmpty() {
return header.next == null;
}

public void makeEmpty() {
header.next = null;
}

 public LinkedListIterator zeroth() {
  return new LinkedListIterator(header);
 }

 public LinkedListIterator first() {
 return new LinkedListIterator(header.next);
 }

  public void insert(Object x, LinkedListIterator p) {
  if (p != null && p.current != null)
  p.current.next = new ListNode(x, p.current.next);
}

 public LinkedListIterator find(Object x) {
ListNode itr = header.next;

while (itr != null && !itr.element.equals(x))
  itr = itr.next;

return new LinkedListIterator(itr);
 }

  public LinkedListIterator findPrevious(Object x) {
  ListNode itr = header;

 while (itr.next != null && !itr.next.element.equals(x))
  itr = itr.next;

return new LinkedListIterator(itr);
  }

public void remove(Object x) {
LinkedListIterator p = findPrevious(x);

if (p.current.next != null)
  p.current.next = p.current.next.next; // Bypass deleted node
}

 private ListNode header;

}

class LinkedListIterator {
LinkedListIterator(ListNode theNode) {
current = theNode;
  }

  public boolean isValid() {
 return current != null;
  }

  public Object retrieve() {
return isValid() ? current.element : null;
  }

public void advance() {
  if (isValid())
  current = current.next;
  }

  ListNode current;
}

class ListNode {
  public ListNode(Object theElement) {
this(theElement, null);
  }

  public ListNode(Object theElement, ListNode n) {
   element = theElement;
    next = n;
  }

  public Object element;

  public ListNode next;
}