I started my studying today by looking at Programming Interviews Exposed. The author indicates that linked-list problems are common in coding interviews, because they can be solved relatively quickly, but they still expose the coder's thought processes.
As a Java programmer, I don't have much use for linked lists. Java includes a LinkedList class that takes care of all the operations for me. But according to the book, I might still be asked to implement a linked list of my own and solve some linked list problems... because it will expose my thought process.
Okay, I remember linked lists from back when I was a hot-shot C programmer. (I used to think Java was a flash in a pan. With the recent security vulnerabilities, it may turn out that way after all.) I can do this. But perhaps I should pass on the brain teaser for today. The list problems can be my brain teaser.
Implement a singly-linked list. Given a doubly-linked list (with tail pointer) where each node may have a doubly-linked list (without head or tail pointers) as a child, and the children may have their own children, flatten it to a plain doubly-linked list. Now put it back.
Implement a singly-linked list. No problem; that's just a single element that points to the next element. I can even genericize it. Of course, you'll probably want insert and delete operations... and some way to traverse the list... hmmm, there's more work here than just the simple data structure, isn't there? I'll implement just those operations. If you really want me to implement the List interface I can, but it'll take a little longer.
[code]
public class MyList
{
/** The node type. Skipping accessors and constructor for now. */
private class MyNode {
public T value = null;
public MyNode next = null;
}
/** Again, skipping accessors here. They're too simple to worry about. */
private MyNode head = null;
/** Insert at index */
public void add(int index, T val) {
if (index < 0) { throw new IndexOutOfBoundsException("Can't insert at negative index!"); }
if (index == 0) {
// Insert at head
MyNode n = new MyNode();
n.value = val;
n.next = head;
head = n;
return;
}
MyNode curr = head;
int togo = index - 1;
while (togo > 0) {
curr = curr.next;
togo--;
// Did we overrun the bounds of the list?
if (curr == null) {
throw new IndexOutOfBoundsException("Index " + index + " exceeds list size.");
}
}
MyNode n = new MyNode();
n.value = val;
n.next = curr.next;
curr.next = n;
}
/** Add on back */
public boolean add(T val) {
if (head == null) {
add(0, val);
return true;
}
MyNode n = new MyNode();
n.value = val;
MyNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = n;
n.next = null;
return true;
}
/** Insert in front */
public void insert(T val) {
add(0, val);
}
/** Remove at node index */
public T remove(int index) {
if (index < 0) {
throw new IndexOutOfBoundsException("Can't remove at negative index!");
}
if (head == null) {
throw new IndexOutOfBoundsException("Can't remove from null list!");
}
MyNode curr = head;
if (index == 0) {
head = head.next;
return curr.value;
}
int togo = index - 1;
MyNode prev = curr;
curr = curr.next;
while (togo > 0) {
prev = curr;
curr = curr.next;
togo--;
if (curr == null) {
throw new IndexOutOfBoundsException("Index " + index + " exceeds final list index!");
}
}
prev.next = curr.next;
return curr.value;
}
/** Remove first instance of specified value */
public boolean remove(T val) {
if (head == null) { return false; }
MyNode curr = head;
if (head.value.equals(val)) {
head = head.next;
curr.next = null;
return true;
}
while (curr.next != null) {
if (curr.next.value.equals(val)) {
MyNode match = curr.next;
curr.next = match.next;
match.next = null;
return true;
}
}
// Reached end of list without finding a value.
return false;
}
public class MyIterator implements Iterator {
public MyNode curr = null;
public MyIterator() {
curr = head;
}
public boolean hasNext() {
return curr != null;
}
public T next() {
T val = curr.value;
curr = curr.next;
return val;
}
public void remove() {
throw new UnsupportedOperationException("Not on my watch!");
}
}
public MyIterator iterator() {
return new MyIterator();
}
}
[/code]
Wow, it's a good thing I've got Eclipse at my back. Typing that out without code completions and warnings took a lot longer than I expected. And I made a few mistakes. In particular, I have to remember that declaring an inner class with the same generic type parameter doesn't make a generic instance of that type; it hides the outer class's generic type declaration. That's why I can get away without declaring MyNode<T>: it's redundant, and downright harmful.
That's quite a bit of code for one post. I think I'll pick up with the flattening tomorrow!