java - Java方法实现中的链表

Question

现在我正在准备编码面试，我有 1 个问题关于 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 实现存在缺陷，因为如果多个线程同时工作，它就无法正常工作。然后需要从Collections类中创建一个synchronizedList，或者至少需要使用一个能够很好地支持多线程的实现。

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

想想你可以用链接列表做什么。为此，您必须考虑您实际考虑的 LinkedList 类型，因为有许多不同类型的 LinkedList，例如 SinglyLinkedList >、DoubleLinkedList、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();
  }
}

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

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