链表在Java中的方法实现

Question

现在我正在准备编码面试，我有一个关于Java链表的问题。你能告诉我一些可靠的来源，我可以从中学习和练习基本的链表方法吗?我喜欢这个:www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/code/LinkedList.java但我对一些方法实现感到困惑。例如，方法E get(int pos)返回的不是节点，而是位置pos节点中包含的数据E。而这里http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/LinkedList.java#LinkedList方法node node(int index)返回该位置的节点(而不是其中包含的数据)。我应该遵循哪个实现?

Answer 1

数据结构是一个非常概念化和基于上下文的学科。针对每种数据结构存在的各种实现是基于数据结构的需求和范围的。有人甚至认为Collection API的LinkedList实现是有bug的，因为如果多个线程并发地工作，它就不能很好地工作。然后需要从Collections类中创建一个synchronizedList，或者至少需要使用一个可以很好地与多个线程一起工作的实现。

遵循让你前进的最小可行约定，因为面试官不会只问你LinkedList的实现。面试官想知道的是你的概念和编码技巧是否达到了一定的标准。

想想你可以用Linked List做什么。为此，您必须考虑您实际考虑的是哪种类型的LinkedList，因为有许多不同类型的LinkedList，如SinglyLinkedList, DoublyLinkedList, SkipList等。

考虑到SinglyLinkedList，您的LinkedList实现至少应该具有以下方法:add(), remove(), contains(), clear(), size()。

下面是我的SinglyLinkedList的实现:

import java.util.Iterator;
import java.util.StringJoiner;
public class LinkedList<T> implements Iterable<T>
{
  private Node head;
  private Node tail;
  private int size;
  private class Node
  {
    private T value;
    private Node next;
    public Node(T value)
    {
      this.value = value;
    }
  }
  public void add(T value)
  {
    Node node = new Node(value);
    if (head == null)
    {
      head = node;
    }
    else
    {
      tail.next = node;
    }
    tail = node;
    ++size;
  }
  public boolean remove(T value)
  {
    Node previous = null;
    Node current = head;
    while (head != null)
    {
      if (current.value.equals(value))
      {
        if (previous != null)
        {
          previous.next = current.next;
          if (current.next == null)
          {
            tail = previous;
          }
        }
        else
        {
          head = current.next;
          if (head == null)
          {
            tail = null;
          }
        }
        --size;
        return true;
      }
      previous = current;
      current = current.next;
    }
    return false;
  }
  public boolean contains(T value)
  {
    Node current = head;
    while (current != null)
    {
      if (current.value.equals(value))
      {
        return true;
      }
      current = current.next;
    }
    return false;
  }
  public void clear()
  {
    head = null;
    tail = null;
    size = 0;
  }
  public int size()
  {
    return size;
  }
  @Override
  public Iterator<T> iterator()
  {
    return new Iterator<T>()
    {
      private Node current = head;
      @Override
      public boolean hasNext()
      {
        return current != null;
      }
      @Override
      public T next()
      {
        Node next = current;
        current = current.next;
        return next.value;
      }
    };
  }
  @Override
  public String toString()
  {
    StringJoiner joiner = new StringJoiner(", ");
    for (T value : this)
    {
      joiner.add(value.toString());
    }
    return joiner.toString();
  }
}

如您所见，我的实现可能与您在其他地方找到的实现不同。只要数据结构的概念没有发生根本性的变化，只要它与定义的接口正常工作，小的差异就不是问题。

对于像数据结构这样的学科，你必须自己考虑，根据你的需求，使用或实现适合你需要的数据结构。就面试而言，您所需要展示的就是最小可行数据结构的实现。只要确保这种最小可行数据结构在其上下文中没有错误即可。