Coding Interview Practice: Linked Lists

LinkedList.java

import java.util.HashSet;
import java.util.Set;

public class LinkedList {

  private Node head;
  private int size;

  public LinkedList(Node head) {
    this.head = head;
    size = 1;
  }

  public LinkedList() {
    this.head = null;
    size = 0;
  }

  public Node head() {
    return this.head;
  }

  public int size() {
    return this.size;
  }

  public Node search(Object value) {
    Node cur = head;
    if (head.value() == value) {
      return head;
    }
    while (cur != null) {
      if (cur.value() == value) {
        return cur;
      }
      cur = cur.next();
    }
    return null;
  }

  public void add(Node n) {
    if (head == null) {
      head = n;
      size++;
      return;
    }
    Node cur = head;
    while (cur.next() != null) {
      cur = cur.next();
    }
    cur.setNext(n);
    size++;
  }

  public void addToFront(Node n) {
    Node oldHead = head;
    head = n;
    head.setNext(oldHead);
  }

  public void delete(Node n) {
    Node nodeInList = search(n.value());
    if (nodeInList == null) {
      return;
    }
    // beginning
    if (nodeInList == head) {
      head = head.next();
      size--;
      return;
    }
    // middle
    if (nodeInList.next() != null) {
      nodeInList.setValue(nodeInList.next().value());
      Node temp = nodeInList.next();
      nodeInList.setNext(temp.next());
    }
    // end
    if (nodeInList.next() == null) {
      nodeInList = null;
    }
    size--;
  }

  public void remove3rdFromLast() {
    if (head == null) {
      return;
    }
    Node first = head;
    Node behind = head;
    for (int ind = 0; ind < 2; ind++) {
      first = first.next();
    }
    while (first.next() != null) {
      first = first.next();
      behind = behind.next();
    }
    delete(behind);
  }

  public void removeDuplicates() {
    Node cur = head;
    Set<Object> values = new HashSet<Object>();
    while (cur != null) {
      if(!values.add(cur.value())) {
        Node temp = cur;
        delete(cur);
        cur = temp.next();
        continue;
      }
      cur = cur.next();
    }
  }

  public boolean detectLoop() {
    Node tortoise = head;
    Node hare = head.next();

    if (tortoise == null || hare == null) {
      return false;
    }
    while (hare.next() != null) {
      tortoise = tortoise.next();
      hare = hare.next().next();
      if (tortoise == hare) {
        return true;
      }
    }
    return false;
  }

  @Override
  public String toString() {
    Node cur = head;
    String val = "";
    while (cur != null) {
      val += cur.value().toString();
      cur = cur.next();
      if (cur != null) {
        val += " -> ";
      }
    }
    return val;
  }
}

LinkedListTest.java

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import org.junit.Test;


public class LinkedListTest {

  @Test
  public void testAddSetsHeadProperly() {
    Node n = new Node(1);
    LinkedList list = new LinkedList(n);
    assertEquals(n, list.head());
  }

  @Test
  public void testAddWorksWithTwoElements() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    assertEquals(n, list.head());
    assertEquals(n2, list.head().next());
    assertEquals(n3, list.head().next().next());
  }

  @Test
  public void testAddWorksWithNElements() {
    LinkedList list = new LinkedList();
    for (int ind = 0; ind < 10; ind++) {
      Node n = new Node(ind);
      list.add(n);
    }
  }


  @Test
  public void testSearch() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    LinkedList list = new LinkedList(n);
    list.add(n2);
    assertEquals(n, list.search(1));
    assertEquals(n2, list.search(2));
    assertEquals(null, list.search(1000));
  }

  @Test
  public void testDeleteHead() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    LinkedList list = new LinkedList(n);
    list.add(n2);
    assertEquals(n, list.head());
    list.delete(n);
    assertEquals(n2, list.head());
    assertEquals(null, list.search(n));
  }

  @Test
  public void testDeleteMiddle() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    assertEquals(n2, list.head().next());
    list.delete(n2);
    assertEquals(n3.value(), list.head().next().value());
  }

  @Test
  public void testDeleteEnd() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    assertEquals(n3, list.head().next().next());
    list.delete(n3);
    assertEquals(n2, list.head().next());
  }

  @Test
  public void testRemoveThirdFromLast() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    Node n4 = new Node(4);
    Node n5 = new Node(5);
    Node n6 = new Node(6);

    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    list.add(n4);
    list.add(n5);
    list.add(n6);

    list.remove3rdFromLast();
    assertNull(list.search(n4));
  }

  @Test
  public void testRemoveDuplicates() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(1);
    Node n4 = new Node(4);
    Node n5 = new Node(5);
    Node n6 = new Node(5);

    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    list.add(n4);
    list.add(n5);
    list.add(n6);

    assertEquals(6, list.size());
    list.removeDuplicates();
    assertEquals(4, list.size());
  }

  @Test
  public void testCycle() {
    Node n = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(1);
    Node n4 = new Node(4);
    Node n5 = new Node(5);
    Node n6 = new Node(5);

    LinkedList list = new LinkedList(n);
    list.add(n2);
    list.add(n3);
    list.add(n4);
    list.add(n5);
    list.add(n6);

    assertFalse(list.detectLoop());

    LinkedList list2 = new LinkedList(n);
    list.addToFront(n2);
    list.addToFront(n);

    assertTrue(list2.detectLoop());
  }

}

Node.java

public class Node {

  private Node next;
  private Object value;

  public Node(Node next, Object value) {
    this.next = next;
    this.value = value;
  }

  public Node(Object value) {
    this.value = value;
    this.next = null;
  }

  public Node next() {
    return this.next;
  }

  public Object value() {
    return this.value;
  }

  public void setNext(Node n) {
    this.next = n;
  }

  public void setValue(Object value) {
    this.value = value;
  }


}

Q1

A linked list is a non-indexed data structure that consists of nodes that are chained together.  A node typically contains a data field and a next pointer, which points to another node in the list or null to signify the end of the list.  

Some implementation consideration for a linked list are whether the list is doubly or singly linked, that is to say if each node contains a next and previous pointer (doubly linked) or solely a next pointer (singly linked).  Other considerations include circular linked lists, in which the ending node points to the beginning node, and the usage or sentinel values which are, in a sense, "phantom" nodes that do not contain actual data but simplify algorithms usually need to check for the end of the list.

An important choice when deciding on using a linked list is whether or not an array would suffice for the job, since an array provides O(1) lookup time for random access, whereas a linked list will cost O(N).  If the amount of memory required for storing your data is known in advance, an array is usually the best choice.

I couldn't find a great solution for question #2 (removing the duplicates). My solution adds each element to a set and checks for a collision. I'm sure there is some clever way to do this with pointers. The other 2 questions I have actually been asked in interviews and remembered the solutions!

I'm not currently looking for work, but would love tips of any sort. I'm just beginning my career as a Java developer and want to improve my skills.