import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A deque implemented using a doubly-linked list.
 *
 * @author CS 240 instructors and YOU
 * @version Fall 2025
 *
 * @param <E> the type of elements in this deque
 */
public class LinkedDeque<E> extends AbstractDeque<E> {

  //////////////////////////////////////////////////////
  // DO NOT MODIFY THE CODE IN THIS SECTION

  // Node class for a doubly-linked list
  private class Node {
    E item;
    Node prev;
    Node next;

    Node(E item, Node prev, Node next) {
      this.item = item;
      this.prev = prev;
      this.next = next;
    }
  }

  private Node head;
  private Node tail;
  private int size;

  // Default constructor.
  public LinkedDeque() {
    head = null;
    tail = null;
    size = 0;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public void clear() {
    head = null;
    tail = null;
    size = 0;
  }

  @Override
  public E peekFirst() {
    if (head == null) {
      return null;
    }

    return head.item;
  }

  @Override
  public E peekLast() {
    if (tail == null) {
      return null;
    }

    return tail.item;
  }


  @Override
  public Iterator<E> iterator() {
    return new LinkedDequeIterator();
  }


  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("[");

    Node current = head;
    while (current != null) {
      sb.append(current.item);
      if (current.next != null) {
        sb.append(", ");
      }
      current = current.next;
    }

    sb.append("]");
    return sb.toString();
  }

  // END OF UNMODIFIABLE SECTION
  //////////////////////////////////////////////////////

  @Override
  public boolean offerFirst(E item) {
    // As an example, this one is implemented for you.

    Node newNode = new Node(item, null, head);

    if (size == 0) { // Consider the case when the deque is empty.
      head = newNode;
      tail = newNode;
    } else { // Have at least one element in the deque.
      head.prev = newNode;
      head = newNode;
    }

    size++;
    return true;
  }

  @Override
  public boolean offerLast(E item) {
    // This should add the item to the end of the deque.

    // TODO

    return true;
  }

  @Override
  public E pollFirst() {
    // This should remove AND return the first element in the deque.

    // There are three cases to consider:
    // 1. The deque is empty.
    // 2. The deque has only one element.
    // 3. The deque has more than one element.

    // TODO

    return null;
  }

  @Override
  public E pollLast() {
    // This should remove AND return the last element in the deque.

    // There are three cases to consider:
    // 1. The deque is empty.
    // 2. The deque has only one element.
    // 3. The deque has more than one element.

    // TODO

    return null;
  }

  // Iterator for the LinkedDeque class.
  // Feel free to modify the LinkedDequeIterator class in any way you wish.
  private class LinkedDequeIterator implements Iterator<E> {

    private Node current;
    private Node last;

    public LinkedDequeIterator() {
      current = head;
    }

    @Override
    public boolean hasNext() {
      return current != null;
    }

    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }

      E data = current.item;
      last = current; // The last node visited by next()
      current = current.next; // Go right
      return data;
    }

    @Override
    public void remove() {
      if (last == null) {
        throw new IllegalStateException();
      }

      // Hints:
      // 1. Make sure you know which node to remove. It's the last node visited by next().
      // 2. You will need to think about three possible cases:
      // a. If "last" is the first node in the deque.
      // (Tip: do you have a method do remove the first node?)
      // b. If "last" is the last node in the deque.
      // (Tip: do you have a method to remove the last node?)
      // c. If "last" is in the middle of the deque.
      // (The nodes before and after "last" need to be updated.)
      // 3. Don't forget to update the size of the deque.

      // TODO
    }
  }

  @Override
  public Iterator<E> descendingIterator() {
    // TODO
    return null;
  }

  @Override
  public boolean removeFirstOccurrence(Object object) {
    // TODO
    // Hint: This should be relatively simple once you have completed the iterator.

    return false;
  }

  @Override
  public boolean removeLastOccurrence(Object object) {
    // TODO
    // Hint: This should be relatively simple once you have completed the descending iterator.
    return false;
  }



}