Node definition

class Node {
  T val;
  Node next;
  Node(T val) { this.val = val; }
}
Advertisement

Insert head — O(1)

Node insertHead(Node head, T val) {
  Node n = new Node<>(val);
  n.next = head;
  return n;
}
Advertisement

Insert tail — O(N) unless tail pointer

Node insertTail(Node head, T val) {
  if (head == null) return new Node<>(val);
  Node cur = head;
  while (cur.next != null) cur = cur.next;
  cur.next = new Node<>(val);
  return head;
}

Delete by value — O(N)

Walk with prev pointer, unlink node. Handle head separately.