Self-made Linked List

Question

I was tasked by my teacher with making a linked list by myself, so I could understand the concept better. Here is the MyLinkedList class:

public class MyLinkedList<T>{
    private Node<T> lastNode;
    private int nodeCount;

    public MyLinkedList(){
        this.lastNode = null;
        this.nodeCount = 0;
    }

    public int size() {
        return nodeCount;
    }

    public boolean isEmpty() {
        return this.nodeCount == 0;
    }

    public void add(T data) {
        Node<T> currentNode = new Node<T>(data);

        if (this.lastNode != null) {
            currentNode.index = lastNode.index + 1;
            currentNode.previousNode = lastNode;
            lastNode.nextNode = currentNode;
        }else {
            currentNode.previousNode = null;
            currentNode.index = 0;
        }
        this.lastNode = currentNode;
        this.nodeCount++;
    }

    public T get(int index){
        //error handling
        if(this.isEmpty() || index < 0 || index > this.nodeCount){
            return null;
        }
        //
        Node<T> currentNode;
        int count = lastNode.index - index;
        currentNode = lastNode;

        while (count > 0) {
            currentNode = currentNode.previousNode;
            count--;
        }

        return currentNode.data;
    }

    public Node<T> getNode(int index){
        //error handling
        if(this.isEmpty() || index < 0 || index > this.nodeCount){
            return null;
        }
        //
        int count = lastNode.index - index;
        Node<T> currentNode = lastNode;

        while (count > 0){
            currentNode = currentNode.previousNode;
            count--;
        }

        return currentNode;
    }

    public boolean insert(T data, int index){
        Node<T> currentNode;

        if (this.getNode(index) != null){
            Node<T> newNode = new Node<T>(data);
            currentNode = this.getNode(index);
            newNode.index = index;

            if (currentNode.previousNode != null) {
                currentNode.previousNode.nextNode = newNode;
                newNode.previousNode = currentNode.previousNode;
                currentNode.previousNode = newNode;
                newNode.nextNode = currentNode;
            } else {
                currentNode.previousNode = newNode;
                newNode.nextNode = currentNode;
            }
            currentNode = newNode;

            while (currentNode.nextNode != null){
                currentNode = currentNode.nextNode;
                currentNode.index++;
            }

            this.nodeCount++;
            return true;
        } else {
            return false; // error handling
        }
    }

    public boolean remove(int index){
        Node<T> currentNode;

        if (this.getNode(index) != null){
            currentNode = this.getNode(index);

            if(currentNode.previousNode != null) {
                currentNode.nextNode.previousNode = currentNode.previousNode;
                currentNode.previousNode.nextNode = currentNode.nextNode;
            } else if (currentNode.nextNode != null){
                currentNode.nextNode.previousNode = null;
            } else if (this.isEmpty()){
                this.lastNode = null;
            }

            while (currentNode.nextNode != null){
                currentNode = currentNode.nextNode;
                currentNode.index--;
            }

            this.nodeCount--;
            return true;
        }else {
            return false;
        }
    }
}

And the Node class :

public class Node<T>{
    public Node<T> nextNode = null;
    public Node<T> previousNode = null;
    public int index;
    public T data;

    public Node(T data){
        this.data = data;
    }
}

I guess this will be much slower than the original, but it is not an objective here to make it faster. Although, if you could point out big performance hits, please do so. I ask this question, because I suspect I made mistakes that are not presented in bugs or errors, they are "just ugly". Please focus on these beginner mistakes.

Answer 1

All things considered this looks like a really good beginner's attempt at the problem. The really good things I can see are:

1. you have used generics
2. it appears to all look functional
3. it has advanced concepts (you have a double-linked list, not a single-linked list).

The generics look right, and the double-link is used well for locating data.

There are two major issues I see though that should be resolved though:

1. there is no need for the Node to be public. The Node should be a static inner class of the List, or a package-private (default) if the node is reused between different classes.

   public class MyLinkedList<T> {
       private static class Node<U> {
           ....
       }
       ....
   

   Note how the generic type of the node U is different to the list T, but that is because they are in different contexts, they are actually the same when you use the Node class like:

   Node<T> currentNode = new Node<T>(data);
   

   Because the Node is currently public, and especially because you 'leak' the node with the getNode(int) method, it is is possible of anyone to break your list, by getting a node, and then messing with the node internals.

2. The other concern is the index value in the node. It actually serves no purpose. You do not use it for anything, and you can do all the math you need based on the loop counters and list size. It is a lot of work to maintain, and it adds no value to the result.

You will find your code is much simpler if you resolve those two issues.

Answer 2

There's a bug in the get method. If we run this code:

MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
System.out.printf("%d %d%n", list.get(0), list.get(1));

the output is 1 1. I think you want to change

if(this.isEmpty() || index < 0 || index > this.nodeCount){

to

if (this.isEmpty() || index < 0 || index >= this.nodeCount) {

---

The following code will cause remove to throw a NullPointerException:

MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
list.add(2);
list.remove(1);

Answer 3

In insert, you have

        if (currentNode.previousNode != null) {
            currentNode.previousNode.nextNode = newNode;
            newNode.previousNode = currentNode.previousNode;
            currentNode.previousNode = newNode;
            newNode.nextNode = currentNode;
        } else {
            currentNode.previousNode = newNode;
            newNode.nextNode = currentNode;
        }

You could shorten this to

        if ( null != currentNode.previousNode ) {
            currentNode.previousNode.nextNode = newNode;
            newNode.previousNode = currentNode.previousNode;
        }

        currentNode.previousNode = newNode;
        newNode.nextNode = currentNode;

There's no need for an else clause that has the same code as the then portion.

I also changed the inequality order. The reason is that in C style languages it is particularly easy to write = where you meant to write ==, !=, <=, or >=. As a general rule, it is valid to have an = there, so the compiler can warn at most. If you write the comparison backwards, e.g. null = currentNode.previousNode, then the compiler will throw an error on the typo. This is by no means required, but some of us do it as a matter of course. Obviously there's no point to this unless you are comparing to a constant type value or an expression.

Incidentally, I prefer not to use an else with a !=. An else is essentially negating the if check, so you have clauses for != and not !=. I find it easier to follow if it is == and not ==. Note that in some cases the else is so trivial relative to the main clause that it doesn't make sense to invert them, e.g.

    if (this.getNode(index) != null) {
// do stuff
    } else {
        return false;
    }

But in that specific case, you might instead want to do it like this:

    if ( null == this.getNode(index) ) {
        return false;
    }

    // do stuff

That will also save you a level of indent. This works because the else ended with a return, so you don't actually need to invert. You can just move the check before everything else. A return statement in a then clause makes for an implicit else. You don't have to add an explicit one of top of it.

Answer 4

This is related rather to the design than to the code itself:

One normally uses a LinkedList when frequently adding and/or removing elements from the beginning and/or the end, and an ArrayList when index-based access is needed frequently. As you see with your code, index access in a LinkedList is costly, as you have to go through (potentially) the whole list to get to the nth element.

You have an add() method which adds an element to the end of the list, which is good (I would rename it to append() though, so that it's clear at which end it adds). You should also provide a prepend() method, as well as removeFirst() and removeLast(), to enable your LinkedList to be used for what it's efficient at.

If you add these operations, it will be more efficient to keep a reference to both the first and the last element of the list, for quick access.

Personally I would also add a linkTo(Node other) method to the Node class, which links a node to the next one in the List by setting the nextNode and previousNode of the two nodes. This way you reduce code duplication and make the code easier to read.

Answer 5

public Node<T> getNode(int index)

This should not be public, nor should the Node class be. This allows someone to mess with the content of the list, and make it crash (e.g. by removing arbitrary items from the list and not notifying you). If Node is to be public, you need to add getters and setters and make sure the setters can only be called from within the LinkedList, by making the Node class an inner class.

if(this.isEmpty() || index < 0 || index > this.nodeCount){
    return null;
}

Here you are doing bounds checking. Should be index >= this.nodeCount. Typical implementation will throw IndexOutOfBoundsException if the index is not within the bounds. null is a valid value, and get can return null for a valid index.

You may want to consider implementing the List interface, so you can use your implementation where a List is expected.