Implementing LinkedSet

Here is the Set interface:

public interface Set<T> {
  boolean add(T item);       // adds item if it is absent; returns true if the set changed
  boolean remove(T item);    // removes item if it is present; returns true if the set changed
  boolean contains(T item);  // returns true if item is in the set
  int size();                // returns the number of items in the set
}

add, remove, and contains throw an IllegalArgumentException if the item is null.

LinkedSet<T> implements the Set<T> interface with a singly linked list:

public class LinkedSet<T> implements Set<T> {

  private Node<T> head;  // the first node, or null when empty
  private int size;      // how many items the set holds

  private static class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
      this.value = value;
    }
  }

  public LinkedSet() {
    head = null;
    size = 0;
  }

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

  // the other operations go here
}

Solution

@Override
public boolean contains(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> curr = head;
  while (curr != null) {
    if (item.equals(curr.value)) {
      return true;
    }
    curr = curr.next;
  }
  return false;
}

Solution

@Override
public boolean add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (contains(item)) {
    return false;
  }
  Node<T> newNode = new Node<>(item);
  newNode.next = head;
  head = newNode;
  size++;
  return true;
}

Solution

@Override
public boolean remove(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> prev = null;
  Node<T> curr = head;
  while (curr != null) {
    if (item.equals(curr.value)) {
      if (prev != null) {
        prev.next = curr.next;
      } else {
        head = head.next;
      }
      size--;
      return true;
    }
    prev = curr;
    curr = curr.next;
  }
  return false;
}

Solution

size is $O (1)$ : it returns a field. contains is $O (n)$ : it is a linear search. add is $O (n)$ : the insert at the head is $O (1)$ , but the duplicate check before it is a linear search. remove is $O (n)$ : the unlink is $O (1)$ , but finding the node is a linear search.

Solution

No. All three are $O (n)$ because they have to find an item, and the only way to find an item in the list is a linear search. A prev link and a tail reference make it cheaper to reach or unlink a node at the end, but they do not make the search any faster.