Java方法实现中的链表

Question

现在我正在准备编码面试，我有一个关于Java链表的问题。你能告诉我一些可靠的来源，我可以从那里学习和实践基本的链表方法。我喜欢这个:www.cs.cmu.edu/~adamchik/15-121/structions/linked%20lists/code/linkedlist.java，但我对一些方法实现感到困惑。例如，方法E get（int pos）返回的不是node，而是位于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

数据结构是一个非常概念性和基于上下文的学科。每个数据结构的各种实现都基于数据结构的需求和范围。
甚至可以认为集合API的LinkedList实现有缺陷，因为如果多个线程同时在它上工作，它就不能很好地工作。然后需要从Collections类中创建一个SynchronizedList，或者至少需要使用一个能够很好地处理多个线程的实现。

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

请考虑如何使用链表。为此，您必须考虑实际考虑的LinkedList类型，因为有许多不同类型的LinkedList、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();
  }
}

正如您所看到的，我的实现可能不同于您可能在其他地方找到的实现。只要数据结构的概念没有发生根本性的变化，只要它能正确地使用其定义的接口，微小的差异就不是什么问题。