Delete Element
by Isai Damier

/***************************************************************************
 * Author: Isai Damier
 * Title: Singly Linked List
 * Project: geekviewpoint
 * Package: datastructure
 *
 * Description: A LinkedList is a data structure that allows access
 *   to a collection of data using pointers/references. While an
 *   array can also be defined as above, LinkedLists and arrays differ
 *   in how they are stored in memory and in the operations they
 *   allow. Unlike an array that must be stored in a block of memory,
 *   the nodes of a LinkedList can be stored anywhere because each
 *   node has a reference to the node that succeeds it. Because the
 *   nodes are stored so loosely, inserting nodes into a LinkedList
 *   is easy; whereas in an array, all the succeeding elements must
 *   be shifted. Of course, insertion also means changing the size of
 *   the array, which means creating the entire array anew.
 *
 *   Perhaps the greatest beauty of LinkedList is that it allows
 *   accessing an entire sequence of nodes using only one variable:
 *   a reference to the first node in the sequence.
 *
 *   Countless operations can be performed on LinkedLists. Following
 *   are a few, ranging from the common to the very interesting.
 **************************************************************************/ 
 public class SinglyLinkedList {

  Node head = null;
  Node tail = null;

  /*****************************************************************
   * Description: Delete and retrieve the specified element.
   *
   *   One of the drawbacks of LinkedList is that
   *   it allows no random access. Therefore deleting a random
   *   element is a O(n) process because the list must first be
   *   traversed to find the node containing the element.
   *
   * Technical Details:
   *   0] If el is the head, simply delete from head and return: O(1).
   *   1] If el is the tail, simply delete from tail and return: O(1).
   *   2] Otherwise, find the node containing el, and its parent.
   *   3] If said node is not null, give its parent custody of its child.
   *   4] Return the node.
   *****************************************************************/
  public Node delete(int el) {
    if (el == head.data)//O(1)
    {
      return this.deleteFromHead();
    }
    if (el == tail.data)//O(1)
    {
      return this.deleteFromTail();
    }

    Node del = null;
    Node parent = null, curr = head;
    while (null != curr && el != curr.data) {
      parent = curr;
      curr = curr.next;
    }
    if (null != curr) {
      parent.next = curr.next;
    }
    return curr;
  }
}
public class SinglyLinkedListTest {

   /**
   * Test of delete method, of class SinglyLinkedList.
   */
  @Test
  public void testDelete_int() {
    System.out.println("delete");
    int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11};
    SinglyLinkedList linkedList = new SinglyLinkedList();
    for (int i = 0; i < input.length; i++) {
      linkedList.addToTail(input[i]);
    }
    assertEquals(input[0], linkedList.delete(input[0]).data);
    assertEquals(input[5], linkedList.delete(input[5]).data);
    int last = input.length - 1;
    assertEquals(input[last], linkedList.delete(input[last]).data);
    int[] expected = {4, 5, 2, 1, 6, 7, 4, 8, 3, 0, 16, 19};
    assertEquals(null, linkedList.delete(51));
    assertTrue(Arrays.equals(expected, linkedList.toArray()));
  }
}