public class MyLinkedList<E> implements MyList<E> {
  protected Node<E> head, tail;
  protected int size = 0; // Liczba elementów na liście
  
  /** Tworzenie pustej listy */
  public MyLinkedList() {
  }

  /** Tworzenie listy na podstawie tablicy obiektów */
  public MyLinkedList(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]); 
  }

  /** Zwraca pierwszy element listy */
  public E getFirst() {
    if (size == 0) {
      return null;
    }
    else {
      return head.element;
    }
  }

  /** Zwraca ostatni element listy */
  public E getLast() {
    if (size == 0) {
      return null;
    }
    else {
      return tail.element;
    }
  }

  /** Dodaje element na początku listy */
  public void addFirst(E e) {
    Node<E> newNode = new Node<>(e); // Tworzenie nowego węzła
    newNode.next = head; // Wiązanie nowego węzła z head
    head = newNode; // head wskazuje nowy węzeł
    size++; // Zwiększenie wielkości

    if (tail == null) // Nowy węzeł jest jedynym węzłem na liście
      tail = head;
  }

  /** Dodaje element na końcu listy */
  public void addLast(E e) {
    Node<E> newNode = new Node<>(e); // Tworzenie nowego węzła na element e

    if (tail == null) {
      head = tail = newNode; // Jedyny węzeł na liście
    }
    else {
      tail.next = newNode; // Powiązanie nowego węzła z ostatnim
      tail = newNode; // tail wskazuje teraz ostatni węzeł
    }

    size++; // Zwiększanie wielkości
  }

  @Override /** Dodaje nowy element o podanym indeksie.
    * Indeks pierwszego elementu to 0 */
  public void add(int index, E e) {
    if (index == 0) {
      addFirst(e);
    }
    else if (index >= size) {
      addLast(e);
    }
    else {
      Node<E> current = head;
      for (int i = 1; i < index; i++) {
        current = current.next;
      }
      Node<E> temp = current.next;
      current.next = new Node<>(e);
      (current.next).next = temp;
      size++;
    }
  }

  /** Usuwa pierwszy węzeł i zwraca
    * obiekt z tego węzła */
  public E removeFirst() {
    if (size == 0) {
      return null;
    }
    else {
      E temp = head.element;
      head = head.next;
      size--;
      if (head == null) {
        tail = null;
      }
      return temp;
    }
  }

  /** Usuwa ostatni węzeł i zwraca
    * element z tego węzła */
  public E removeLast() {
    if (size == 0) {
      return null;
    }
    else if (size == 1) {
      E temp = head.element;
      head = tail = null;
      size = 0;
      return temp;
    }
    else {
      Node<E> current = head;

      for (int i = 0; i < size - 2; i++) {
        current = current.next;
      }

      E temp = tail.element;
      tail = current;
      tail.next = null;
      size--;
      return temp;
    }
  }

  @Override /** Usuwa z listy element o podanej pozycji.
              * Zwraca usunięty element */
  public E remove(int index) {   
    if (index < 0 || index >= size) {
      return null;
    }
    else if (index == 0) {
      return removeFirst();
    }
    else if (index == size - 1) {
      return removeLast();
    }
    else {
      Node<E> previous = head;

      for (int i = 1; i < index; i++) {
        previous = previous.next;
      }

      Node<E> current = previous.next;
      previous.next = current.next;
      size--;
      return current.element;
    }
  }

  @Override /** Przesłania metodę toString(), aby zwracała elementy listy */
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    Node<E> current = head;
    for (int i = 0; i < size; i++) {
      result.append(current.element);
      current = current.next;
      if (current != null) {
        result.append(", "); // Rozdziela dwa elementy przecinkiem
      }
      else {
        result.append("]"); // Dodaje końcowy znak ] do łańcucha znaków
      }
    }

    return result.toString();
  }

  @Override /** Opróżnianie listy */
  public void clear() {
    size = 0;
    head = tail = null;
  }

  @Override /** Zwraca true, jeśli lista zawiera element e */
  public boolean contains(Object e) {
    // Ćwiczenie dla czytelników
    return true;
  }

  @Override /** Zwraca element o podanym indeksie */
  public E get(int index) {
    // Ćwiczenie dla czytelników
    return null;
  }

  @Override /** Zwraca indeks pierwszego pasującego elementu listy.
   * −1 oznacza brak dopasowania. */
  public int indexOf(Object e) {
    // Ćwiczenie dla czytelników
    return 0;
  }

  @Override /** Zwraca indeks ostatniego pasującego elementu z listy.
   * −1 oznacza brak dopasowania. */
  public int lastIndexOf(E e) {
    // Ćwiczenie dla czytelników
    return 0;
  }

  @Override /** Zastępuje element ze wskazanej pozycji listy
   * podanym elementem. */
  public E set(int index, E e) {
    // Ćwiczenie dla czytelników
    return null;
  }

  @Override /** Przesłania metodę iterator() zdefiniowaną w interfejsie Iterable */
  public java.util.Iterator<E> iterator() {
    return new LinkedListIterator();
  }
  
  private class LinkedListIterator 
      implements java.util.Iterator<E> {
    private Node<E> current = head; // Bieżący indeks
    
    @Override
    public boolean hasNext() {
      return (current != null);
    }

    @Override
    public E next() {
      E e = current.element;
      current = current.next;
      return e;
    }

    @Override
    public void remove() {
      // Ćwiczenie dla czytelników
    }
  }
  
  protected static class Node<E> {
    E element;
    Node<E> next;

    public Node(E element) {
      this.element = element;
    }
  }
  
  @Override /** Zwraca liczbę elementów na liście */
  public int size() {
    return size;
  }
}