Remake of Java's doubly LinkedList

Question

I've been learning to program in Java and I decided to implement a doubly linked list as practice and as a bridge project before going on to learn C++. I know Java includes a LinkedList implementation, but I wrote this for practice. I have finished the code and it works correctly. However, I'd appreciate some feedback on style and things that I should do differently or not at all.

Also, note: I'm not really worried about a unified documentation style; I know it's a bit broken. I only added it out of courtesy to the people who may be reading my code. I'm more interested in feedback on my coding style.

MyLinkedList

import java.util.NoSuchElementException;

public class MyLinkedList<T> {

protected MyNode<T> firstNode;
protected MyNode<T> lastNode;
protected int size;

/**
 * Constructs a new Linked List
 */
public MyLinkedList() {
    firstNode = new MyNode<T>();
    lastNode = firstNode;
    size = 0;

}

/**
 * Adds an element to the linked list
 * 
 * @param element
 *            to be added to linked list
 */
public void add(T content) {
    if (size == 0)
        firstNode.setContent(content);
    else
        lastNode = lastNode.spawnNode(content);
    size++;
}

/**
 * Adds an element to the beginning of the linked list
 * 
 * @param content
 *            element to be added to linked list
 */
public void addFirst(T content) {
    if (size == 0)
        firstNode.setContent(content);
    else {
        MyNode<T> newFirst = new MyNode<T>(content);
        MyNode<T> oldFirst = firstNode;
        firstNode = newFirst;
        newFirst.setNextNode(oldFirst);
        oldFirst.setPreviousNode(newFirst);
    }
    size++;
}

/**
 * Returns an arbitrary item from the linked list
 * 
 * @param index
 *            Index of item to be retrieved from the linked list
 * @return Item residing at index
 */
public T get(int index) {
    return getNode(index).getContent();
}

/**
 * Returns the first item in the linked list
 * 
 * @return First item in the linked list
 */
public T getFirst() {
    return firstNode.getContent();
}

/**
 * Returns the last item in the linked list
 * 
 * @return Last item in the linked list
 */
public T getLast() {
    return lastNode.getContent();
}

/**
 * Returns the node at a given index 
 * @param index Which node to retrieve
 * @return Node at index
 */
private MyNode<T> getNode(int index) {
    if (index < 0 || index >= size)
        throw new NoSuchElementException(index < 0 ? "Negative index"
                : "Index does not exist");

    MyNode<T> which;
    if (index <= size / 2) {
        which = firstNode;
        for (int i = 0; i < index; i++)
            which = which.getNextNode();
    } else {
        which = lastNode;
        for (int i = size - 1; i > index; i--)
            which = which.getPreviousNode();
    }
    return which;
}

/**
 * Inserts an element before an arbitrary point in the list
 * 
 * @param index
 *            Index to element before
 * @param content
 *            What to insert at index
 */
public void insertBefore(int index, T content) {
    if (index == 0) {
        addFirst(content);
        return;
    }

    MyNode<T> currentOcc = getNode(index);
    MyNode<T> prev = currentOcc.getPreviousNode();
    MyNode<T> newGuy = new MyNode<T>(content);
    newGuy.setNextNode(currentOcc);
    newGuy.setPreviousNode(prev);
    prev.setNextNode(newGuy);
    currentOcc.setPreviousNode(newGuy);
    size++;
}

/**
 * Determines if the list is empty
 * 
 * @return If the list is empty
 */
public boolean isEmpty() {
    if (size == 0)
        return true;
    return false;
}

/**
 * Removes the node (and consequently element) at index and "heals" the list
 * 
 * @param index
 *            Location of element to be removed
 */
public void remove(int index) {

    if (index == 0) {
        removeFirst();
        return;
    }

    if (index == size - 1) {
        removeLast();
        return;
    }

    MyNode<T> marked = getNode(index);
    MyNode<T> before = marked.getPreviousNode();
    MyNode<T> after = marked.getNextNode();
    before.setNextNode(after);
    after.setPreviousNode(before);
    marked = null;
    size--;
}

/**
 * Removes first node (and consequently first element) from the list
 */
public void removeFirst() {

    if (size != 1) {
        @SuppressWarnings("unused")
        MyNode<T> temp = firstNode;
        firstNode = firstNode.getNextNode();
        firstNode.setPreviousNode(null);
        temp = null;
    } else
        firstNode.setContent(null);

    size--;
}

/**
 * Removes last node (and consequently last element) from the list
 */
public void removeLast() {
    if (size != 1) {
        @SuppressWarnings("unused")
        MyNode<T> temp = lastNode;
        lastNode = lastNode.getPreviousNode();
        lastNode.setNextNode(null);
        temp = null;
    } else
        lastNode.setContent(null);
    size--;
}

/**
 * Updates the content of a node
 * 
 * @param index
 *            Location of node to update
 * @param content
 *            New content for node
 */
public void set(int index, T content) {
    getNode(index).setContent(content);
}

/**
 * Returns size of node
 * 
 * @return size of node
 */
public int size() {
    return size;
}
}

MyNode

public class MyNode<T> {

private T content;
private MyNode<T> nextNode;
private MyNode<T> previousNode;

/**
 * Constructs a new node without adding content
 */
public MyNode() {
    nextNode = null;
    this.content = null;
    previousNode = null;
}

/**
 * Constructs a new node and sets its content
 * 
 * @param content
 *            Content to occupy new node
 */
public MyNode(T content) {
    nextNode = null;
    this.content = content;
    previousNode = null;
}

/**
 * Returns this node
 * 
 * @return This node
 */
public MyNode<T> get() {
    return this;
}

/**
 * Returns the content of the node
 * 
 * @return The content of the node
 */
public T getContent() {
    return content;
}

/**
 * Returns the next node
 * 
 * @return The next node
 */
public MyNode<T> getNextNode() {
    return nextNode;
}

/**
 * Returns the previous node
 * 
 * @return The previous node
 */
public MyNode<T> getPreviousNode() {
    return previousNode;
}

/**
 * Determines if this is the last node
 * 
 * @return If this is the last node
 */
public boolean isLast() {
    if (nextNode == null)
        return true;
    return false;
}

/**
 * Sets the content of this node
 * 
 * @param content
 *            Content to be given to this node
 */
public void setContent(T content) {
    this.content = content;
}

/**
 * Sets the next node
 * 
 * @param next
 *            The node to be defined as next
 */
public void setNextNode(MyNode<T> next) {
    nextNode = next;
}

/**
 * Sets the previous node
 * 
 * @param previous
 *            Which node is to become the previous node
 * @return the previous node
 */
public MyNode<T> setPreviousNode(MyNode<T> previous) {
    previousNode = previous;
    return previousNode;
}

/**
 * Convenience method that creates a new node and links it after this node
 * 
 * @precondition This is the last node in the list
 * @param content
 * @return
 */
public MyNode<T> spawnNode(T content) {
    nextNode = new MyNode<T>(content);
    nextNode.setPreviousNode(this);
    return nextNode;
}
}

Answer 1

Firstly, MyNode isn't going to be used by any class outside of MyLinkedList. It would be better if you implemented it as a private class inside the same file as MyLinkedList. Its only purpose is as data storage for MyLinkedList, its not really an object in its own right.

As part of that, I'd make all of member variables public and get rid of your getter/setter functions. The point of private access is to prevent outside code from mucking with it. But here the only code using MyNode's is MyLinkedList which is supposed to much with it. All those getters/setters just complicate the situation.

if (size == 0)
    firstNode.setContent(content);
else
    lastNode = lastNode.spawnNode(content);

Most people will say that you should always put { and } even in one line blocks.

public boolean isEmpty() {
    if (size == 0)
        return true;
    return false;
}

Just use

return size == 0;

Its simpler and easier to read.

    @SuppressWarnings("unused")
    MyNode<T> temp = firstNode;
    firstNode = firstNode.getNextNode();
    firstNode.setPreviousNode(null);
    temp = null;

What you are you doing with temp? The warning is telling you that the code involving temp does nothing.

In your constructor you create one empty node to start with, in several places in your code you have a special case to handle it by storing the first inserted value into that node. As far as I can tell you've managed to find all the case where its a problem. But there doesn't seem to be a good reason to do it that way.

In general, your code is more complicated then it needs to be. For example you have both insertBefore and insertAfter. But insertAfter could have been implemented as insertBefore(index + 1); You have lots of different insert/remove methods when you really only want to have one. The others might be useful from an interface perspective, but they should all call into a single implementation. (Unless they can implement it way more efficiently)

I suggest a method like the following

private link_together(MyNode<T> left, MyNode<T> right)
{
    if(left != null)
    {
        left.next = right;
    }else{
        firstNode = right;
    }

    if(right != null)
    {
        right.previous = left;
    }else{
        lastNode = left;
    }
}

This will link two nodes together. It will also handle the case where either of the nodes is null which means that the current node is either at the beginning or end of the list.

Now insert becomes:

   public void insertBefore(int index, T value)
   {
       Node<T> new_node = new Node<T>(value);
       Node<T> node_after = getNode(index);
       // if we are trying to insert at the end of the list
       // node_after will be null
       Node<T> node_before = node_after : node_after.previous : lastNode;
       link_together(node_before, new_node);
       link_together(new_node, node_after);
       size++;
   }

This function can be used to insert nodes anywhere in the list even at the beginning or end or in empty lists. In a similar way, remove also works.

public void remove(int index)
{
    Node<T> node = getNode(index);
    Node<T> node_before = node.previous;
    Node<T> node_after = node.next;
    link_together(node_before, node_after);
    size--;
}

Answer 2

I don't have much to add to Winston's post.

if (index < 0 || index >= size)
        throw new NoSuchElementException(index < 0 ? "Negative index"
                : "Index does not exist");

I'd handle both cases separate:

if (index < 0 ) throw new NoSuchElementException("Negative index");
if (index >= size) throw new NoSuchElementException("Index does not exist");

Your getNode does three things and I'd extract getFromTail and getFromHead (as protected methods) for better separation of concerns and testability.