3
\$\begingroup\$

I just started learning Java, and wrote up a linked list. I'm coming from just having learned Haskell, so I've been out of the mindset of stateful computations for awhile.

I'd like to know how it could be improved in any way. Please be critical. Mainly though, I'd like suggestions on readability, and safe practices.

It's very simple right now, only allowing additions at the end and deletions; but I figured it would be sufficient for a review.

class Node<T> {
    T cargo;
    Node<T> tail;

    public Node(T nCargo) {
        cargo = nCargo;
        tail = null;
    }

    public Node<T> getNext() {
        return tail;
    }

    public T getCargo() {
        return cargo;
    }

    public boolean isLast() {
        return tail == null;
    }

    public Node<T> getLast() {
        Node<T> curNode = this;
        while (!curNode.isLast()) {
            curNode = curNode.getNext();
        }
        return curNode;
    }

    public void add(T nCargo) {
        tail = new Node<T>(nCargo);
    }

    public boolean canLink() {
        return this.getNext().getNext() != null;
    }

    public void deleteNext() {
        if (this.canLink()) { tail = tail.getNext(); 
            } else { tail = null; }
    }

}

public class Vect<T> {
    Node<T> head;
    int vSize;

    public Vect() {
        head = null;
        vSize = 0;
    }
    public Vect(T cargo) {
        head = new Node<T>(cargo);
        vSize = 1;
    }

    public void pushBack(T cargo) {
        Node<T> last = head.getLast();
        vSize += 1;
        last.add(cargo);
    }

    private Node<T> getNodeAt(int i) {
        Node<T> curNode = head;
        for (int cI = 0; i > cI; cI++) {
            curNode = curNode.getNext();
        }
        return curNode;
    }

    public T getAt(int i) {
        return getNodeAt(i).getCargo();
    }

    public int length() {
        return vSize;
    }

    public void deleteHead() {
        if (head.getNext() != null) { head = head.getNext();
            } else { head = null; }
        vSize -= 1;
    }

    public void deleteAt(int i) {
        if (i == 0) {
            deleteHead();
        } else {
            Node<T> curNode = this.getNodeAt(i - 1);
            curNode.deleteNext();
            vSize -= 1;
        }
    }
}

and its use:

public class Main {

    public static void main(String[] args) {
        Vect <Integer> v = new Vect<Integer>(2);
        v.pushBack(3);
        v.pushBack(4);
        v.pushBack(5);
        v.pushBack(6);

        for (int i = 0; i < v.length(); ++i) {
            System.out.println(v.getAt(i));
        }

        v.deleteAt(2);

        for(int i = 0; i < v.length(); ++i) {
            System.out.println(v.getAt(i));
        }

    }
}
\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

Access to member variables

Restrict the accessibility of member variables as much as possible:

private final T cargo;
private Node<T> tail;

You don't want these fields to be editable outside of this class. Both of these should be private. And since you never change cargo after setting it, it can be final.

Naming

I suggest the following renames:

  • data instead of cargo
  • cargo instead of nCargo in the constructor (and then use this.cargo = cargo to assign to the field)
  • index instead of i in getAt and getNodeAt
  • size instead of vSize

Use the diamond operator

Assuming you can use Java 7 (hopefully, because Java 6 is no longer supported), you should change this:

tail = new Node<T>(nCargo);

to this:

tail = new Node<>(nCargo);

This is called the diamond operator. The compiler can figure out the right type.

Formatting

This is very badly formatted

public void deleteNext() {
    if (this.canLink()) { tail = tail.getNext(); 
        } else { tail = null; }
}

It should have been like this:

public void deleteNext() {
    if (this.canLink()) {
        tail = tail.getNext();
    } else {
        tail = null;
    }
}

But actually, I would use a ternary operator to make it more compact:

public void deleteNext() {
    tail = canLink() ? tail.getNext() : null;
}

Simplifications

This is not only badly formatted, it can also be vastly simplified:

public void deleteHead() {
    if (head.getNext() != null) { head = head.getNext();
        } else { head = null; }
    vSize -= 1;
}

to this:

public void deleteHead() {
    head = head.getNext();
    --size;
}

Misc

A more common way of writing x += 1 is ++x, and x -= 1 as --x.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks. That last one surprised me. You'd think I would have caught that. \$\endgroup\$ Nov 26, 2014 at 21:49
3
\$\begingroup\$

Disclaimer: This review is reviewing this as work-in-process, and not as "finished".

On a quick glance this looks mostly correct. I still got a few points, that definitely need to be fixed before proceeding:

  1. Index handling:
    You don't do anything with negative indexes. vector.getAt(-1); results in an infinite loop, as well as vector.deleteAt(-1);. I suggest you just check and throw an InvalidArgumentException for any \$index < 0\$

  2. Empty list:
    Your empty list throws null-pointer exceptions all around. Don't do that. You should check your head before doing stuff with it, and if it's null, throw IllegalStateException or similar.

  3. Optimizing pushBack():
    There is a relatively simple and quick-to-implement optimization for your pushBack. Your Vect<T> should maintain a "pointer" to the last node. On deleting the last node you need to check for the special-case just like when deleting head, but after that your pushBack becomes dead-simple:

     public void pushBack(T cargo) {
         tail.add(cargo);
         tail = tail.getNext();
         vSize++;
     }
    
\$\endgroup\$
1
  • \$\begingroup\$ Whoops. I should have caught the first 2 points. I rushed it, and missed some testing :/. Sorry. I like the third point though. I'll see if I can neatly add it in. Thank you. \$\endgroup\$ Nov 26, 2014 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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