Связанный список в реализации метода Java

Структуры данных — очень концептуальная дисциплина, основанная на контексте. Различные реализации, существующие для каждой структуры данных, основаны на требованиях и области действия структуры данных.
Можно даже утверждать, что LinkedList реализация Collection API ошибочна, поскольку она не работает должным образом, если над ней работают несколько потоков. одновременно. Затем необходимо создать synchronizedList из класса Collections или, по крайней мере, использовать реализацию, которая хорошо работает с несколькими потоками.

Следуйте минимально жизнеспособному соглашению, которое поможет вам начать работу, поскольку интервьюер не просто спросит вас о реализации 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();
  }
}

Как видите, моя реализация может отличаться от реализаций, которые вы можете найти в других местах. Небольшие различия не являются проблемой до тех пор, пока концепции структуры данных не меняются радикально и пока она правильно работает с определенным интерфейсом.

Для таких дисциплин, как структуры данных, вы должны думать самостоятельно и, основываясь на своих требованиях, использовать или внедрять структуры данных, соответствующие вашим потребностям. Что касается интервью, реализация минимально жизнеспособной структуры данных — это все, что вам нужно показать, и все, что требуется. Просто убедитесь, что такая минимально жизнеспособная структура данных не содержит ошибок в своем контексте.