2
\$\begingroup\$

I have to make a linked list as a quasi-homework task, about which I have already asked two questions about here and here. Since the whole code is really big (400 lines approx.), I will include only the few functions I am asking you to review, although, if you need any more code, I will upload it.

Here is the .add(int, T) function:

public void add(int index, T data){
    if (getNode(index) == null){
        throw new NoSuchElementException();
    } else if (index<0 || index>=size){
        throw new NullPointerException();
    }

    Node<T> crntNode;
    Node<T> newNode = new Node<T>(data);
    crntNode = getNode(index);
    newNode.index = index;

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

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

    size++;
}

The .get(int) function:

public T get(int index){
    if(isEmpty() || index < 0 || index >= size){
        return null;
    }

    Node<T> crntNode;
    int count = size - index - 1;
    crntNode = lastNode;

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

    return crntNode.data;
}

And the .remove(int) function:

public T remove(int index) {
    if (getNode(index) == null || isEmpty()) {
        return null;
    } else if (size == 1){
        size = 0;
        Node<T> crntNode = firstNode;
        firstNode = null;
        lastNode = null;
        return crntNode.data;
    }

    Node<T> crntNode = getNode(index);

    if (crntNode.nextNode != null){
        if (crntNode.previousNode != null){
            crntNode.previousNode.nextNode = crntNode.nextNode;
        } else {
            firstNode = crntNode.nextNode;
            firstNode.previousNode = null;
            size--;
            return crntNode.data;
        }
    }
    if (crntNode.previousNode != null){
        if (crntNode.nextNode != null) {
            crntNode.nextNode.previousNode = crntNode.previousNode;
        } else {
            lastNode = crntNode.previousNode;
            lastNode.nextNode = null;
            size--;
            return crntNode.data;
        }
    }
    crntNode = crntNode.nextNode;
    size--;

    for(int i = index; i < size-1; i++){
        crntNode = crntNode.nextNode;
        crntNode.index--;
    }

    return crntNode.data;
}

I thought a lot about improving these functions, but I can't seem to find a better concept. The reason might be my lack of knowledge, in which case, I hope you could help me.

Is this code efficient and error-safe enough to be used in real programming situations?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

add paramater check

else if (index<0 || index>=size){
    throw new NullPointerException();
}

This isn't necessary, because get already catches these cases. You do the same in remove, where you check for isEmpty, which you already checked via the call to get.

You should also try to be consistent with your exceptions. get throws a NoSuchElementException in this case, while add throws NullPointerException.

Oracles implementation throws an IndexOutOfBoundsException which makes a lot of sense (and if you want to stay close to the List interface, you should use it as Tavian Barnes pointed out), but you could make a case for a NullPointerException or IllegalArgumentException if you wanted to. NoSuchElementException on the other hand would not match the description (Thrown by the nextElement method of an Enumeration).

Don't return null

The only occasion you should return null is if the data inside the node is null. If a value is requested that doesn't exist, throw an exception. You violate this in get and remove, which will make it really difficult for a user in case they do store null in the list.

Naming

  • crntNode: just add the extra characters, its not that much longer: currentNode.

Assign value when declaring variables

Instead of

Node<T> crntNode;
Node<T> newNode = new Node<T>(data);
crntNode = getNode(index);

do this:

Node<T> crntNode = getNode(index);
Node<T> newNode = new Node<T>(data);

You do the same thing in get.

Performance

To increase performance, save the previous result of expensive method calls in local variables. For example, getNode is expensive, and you call it twice in add as well as remove.

index

You should get rid of index (not the parameter, but the node field).

In a linked list, nodes don't have an index, they only have a next node (and maybe previous if its doubly linked). Maintaining the index adds a lot of complexity and reduces performance, which can be avoided.

so just remove index, you are not using it anywhere anyways.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ "there isn't a convention for the type of exception" ... Yes there is, IndexOutOfBoundsException \$\endgroup\$ Oct 18, 2014 at 21:46
  • \$\begingroup\$ @TavianBarnes you are right, thanks. updated my answer \$\endgroup\$
    – tim
    Oct 18, 2014 at 21:56
  • \$\begingroup\$ Thanks, valuable answer. My only concern is about dropping the index of nodes. How should I implement the indexOf method, if I don't have an index? I know it's doable, but seems a bit odd. \$\endgroup\$ Oct 18, 2014 at 22:00
  • \$\begingroup\$ @AttilaHerbert just iterate over the list and check if the item is equal to the current item. keep a count, and then return that. even with an index you would still need to iterate, so it's not even worse for performance. \$\endgroup\$
    – tim
    Oct 18, 2014 at 22:03
  • \$\begingroup\$ I need the indexOf method, because I am implementing the java.util.List<E> interface. I added the index only to be able to implement this method of the interface. \$\endgroup\$ Oct 18, 2014 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.