java - 如何在 Java 中构建链接列表？

Question

可能重复：
如何在 Java 中实现链表？

我们知道java中没有指针。那么在java中构建链接列表的最佳方法是什么？

Answer 1

最好的方法是不构建它。Java在其相当大的集合类选择中已经有一个LinkedList类。

最好使用语言/库已经提供的内容。

Answer 2

你有一个对象，它基本上包含两个变量，没有方法（最低限度；但是，如果你愿意，你可以有方法）。就像是：

class Link
{
   int data;
   Link next;
}

然后你像任何其他对象一样创建一个新的链接。将数据设置为您希望节点保存的数据。然后将 Link 节点设置为它将“指向”的节点（如果它不指向另一个节点，则为 null）。

注意：如果需要，您还可以拥有前一个节点（指向前一个节点）。

Answer 3

尝试使用此代码。

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;
}