IntLinkedList.java

package com.cavoirom.java.recursion.example;

public class IntLinkedList {
  private Node first;

  public IntLinkedList() {}

  public void add(int data) {
    Node newNode = new Node(data);
    if (first == null) {
      this.first = newNode;
    } else {
      addLast(first, newNode);
    }
  }

  public void add(int index, int data) {
    if (index < 0) {
      throw new IndexOutOfBoundsException();
    } else if (index == 0 && this.first == null) {
      this.first = new Node(data);;
    } else if (index == 0) {
      this.first = new Node(data, this.first);
    } else {
      insert(index, 1, this.first, data);
    }
  }

  public int remove(int index) {
    if (index < 0) {
      throw new IndexOutOfBoundsException();
    } else if (index == 0 && this.first == null) {
      throw new IndexOutOfBoundsException();
    } else if (index == 0) {
      Node removedNode = this.first;
      this.first = this.first.next;
      return removedNode.data;
    } else {
      return remove(index, 1, this.first);
    }
  }

  private int remove(int expectedIndex, int currentIndex, Node previousNode) {
    if (previousNode == null) {
      throw new IndexOutOfBoundsException();
    } else if (expectedIndex == currentIndex && previousNode.next == null) {
      throw new IndexOutOfBoundsException();
    } else if (expectedIndex == currentIndex) {
      Node removedNode = previousNode.next;
      previousNode.next = previousNode.next.next;
      return removedNode.data;
    } else {
      return remove(expectedIndex, currentIndex + 1, previousNode.next);
    }
  }

  private void insert(int expectedIndex, int currentIndex, Node previousNode, int data) {
    if (previousNode == null) {
      throw new IndexOutOfBoundsException();
    } else if (expectedIndex == currentIndex) {
      previousNode.next = new Node(data, previousNode.next);
    } else {
      insert(expectedIndex, currentIndex + 1, previousNode.next, data);
    }
  }

  private void addLast(Node currentNode, Node newNode) {
    if (currentNode.next == null) {
      currentNode.next = newNode;
    } else {
      addLast(currentNode.next, newNode);
    }
  }

  private static class Node {
    private int data;
    private Node next;

    public Node(int data) {
      this.data = data;
    }

    public Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }
  }
}