11
\$\begingroup\$

I'm a C++ programmer learning Java in preparation for an OOP class this fall. That being said, Java is fairly new to me so I'd love to hear feedback on how to improve this code.

A few notes:

  • Code works as expected and is ported from my C++ equivalent code I wrote some time ago.
  • Not all operations that should be implemented have been implemented yet (Search, Remove, etc). Of course, that would be more fitting for BSTs or other data structures for efficiency's sake.

node.java

public class node<T> {
    public node() {
        this.setNext(null);
        this.setPrev(null);
    }

    public node(T k) {
        this.setNext(null);
        this.setPrev(null);
        this.setKey(k);
    }

    public node<T> getNext() {
        return next;
    }

    public void setNext(node<T> next) {
        this.next = next;
    }

    public node<T> getPrev() {
        return prev;
    }

    public void setPrev(node<T> prev) {
        this.prev = prev;
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }

    private node<T> next;
    private node<T> prev;
    private T key;
}

List.java

public class list<T> {
    public list() {
        head = null;
    }

    /* Description: Deletes the head node from the linked list and returns the head node's key.
     * Running Time: O(1)
     * Precondition: Linked list must not be null
     * Postcondition: The head node is deleted and its key is returned. */
    public T pop() {
        if(isEmpty()) return null;

        T k = head.getKey();

        if(head == head.getNext()) {
            head = null;
        }
        else {
            node<T> f = head, b = head.getPrev();
            b.setNext(f.getNext());
            head = head.getNext();
            head.setPrev(b);
        }

        return k;
    }

    /* Description: Deletes the tail node from the linked list and returns its node's key.
     * Running Time: O(1)
     * Precondition: Linked list must not be null
     * Postcondition: The tail node is deleted and its key is returned. */
    public T pop_back() {
        if(isEmpty()) return null;

        T k = head.getPrev().getKey();

        if(head == head.getPrev()) {
            head = null;
        }
        else {
            node<T> b = head.getPrev();
            b.getPrev().setNext(head);
            head.setPrev(b.getPrev());
        }

        return k;   
    }

    public void print() {
        node<T> p = head;

        if(isEmpty()) return;
        else if(p == p.getNext()) {
            System.out.println(p.getKey());
        }
        else {
            do {
                System.out.println(p.getKey());
                p = p.getNext();
            } while (p != head);
        }
    }

    /* Description: Allocates a new node x and inserts the node into the back of the linked list.
     * Running Time: O(1)
     * Precondition: Linked list must be instantiated.
     * Postcondition: A node x with the key passed in through k is inserted into the back of the linked list. */
    public void push_back(T k) {
        node<T> x = new node<T>(k);
        push_back(x);
    }

    /* Description: Inserts node x into the back of the linked list.
     * Running Time: O(1)
     * Precondition: Node x must be allocated
     * Postcondition: A node x is inserted into the back of the linked list.*/
    private void push_back(node<T> x) {
        if(isEmpty()) {
            head = x;
            head.setNext(head);
            head.setPrev(head);
        }
        else {
            node<T> p = head.getPrev();
            p.setNext(x);
            x.setPrev(p);
            x.setNext(head);
            head.setPrev(x);
        }
    }

    /* Description: Allocates a new node x and inserts the node into the front of the linked list.
     * Running Time: O(1)
     * Precondition: Linked list must be instantiated.
     * Postcondition: A node x with the key passed in through k is inserted into the front of the linked list. */
    public void push_front(T k) {
        node<T> x = new node<T>(k);
        push_front(x);
    }

    /* Description: Inserts node x into the front of the linked list.
     * Running Time: O(1)
     * Precondition: Node x must be allocated
     * Postcondition: A node x is inserted into the front of the linked list.*/
    private void push_front(node<T> x) {
        if(isEmpty()) {
            head = x;
            head.setNext(head);
            head.setPrev(head);
        }
        else {
            node<T> b = head.getPrev();
            b.setNext(x);
            head.setPrev(x);
            x.setNext(head);
            x.setPrev(b);
            head = x;
        }
    }

    public T top() {
        if(isEmpty()) return null;

        return head.getKey();
    }

    public boolean isEmpty() {
        return (head == null);
    }

    private node<T> head;
}
\$\endgroup\$
3
  • \$\begingroup\$ You say this is a doubly linked circular list, but none of your behaviors take advantage of the fact that it's circular. What you're doing here could be achieved just as well with a non-circular doubly-linked list. Why then is it circular? \$\endgroup\$
    – corsiKa
    Jul 2, 2014 at 20:22
  • \$\begingroup\$ 1. I never stated that all its functionality was finished. Actually, if you read my original post again, I stated that not all functionality that should be implemented has been implemented. 2. Considering that doubly-linked circular and non-circular doubly-linked with a tail pointer are almost identical, can you give me a reason NOT to use a circular implementation? The only difference I see is that I don't have to manage a tail pointer. \$\endgroup\$
    – user47499
    Jul 3, 2014 at 17:36
  • \$\begingroup\$ On one hand, you don't have to manage a second pointer for the tail. On the other hand, when you iterate you have to manage the head/tail pointer the entire time. Part of a code review is defending your design decisions. "No reason not to" is not the same as "having a reason to", especially in the business world. \$\endgroup\$
    – corsiKa
    Jul 3, 2014 at 18:26

3 Answers 3

10
\$\begingroup\$

Java style convention

One of the first thing you should do when working in a new language is to look at style convention. You used C++ convention and not the Java one. Class name should be PascalCase and method name should be camelCase. Unless it's a constant, you should not use _ (except in some precise case).

    if(isEmpty()) {
        ...
    }
    else {
        ...
    }

Should be :

    if(isEmpty()) {
        ...
    } else {
        ...
    }

The else should be on the same line that the last }.

Variable declaration

I always like to start the class with class and instance variables. It will let me know what my class is using. So private node<T> head; should be before the constructor.

I would suggest that you avoid using single letters as a variable name. Reading x and p does not help to know what it's used for. Try to use descriptive name, there is no or almost no length limitation, so be creative!

Documentation

I see that you have good comments for your public methods. I would suggest that you use JavaDoc. It will almost change nothing, just some syntax changes. Here is one example of a JavaDoc :

/**
 * Here is the description of what the method is doing. Some specific things that will      
 * be helpful to the caller like {@link OtherClass#methodName()}
 * @param aParam What your param is or used for in your method
 * @return what your method is returning
 * @see OtherClass
 */

As @tot2 pointed in comments, you can use tools that will generate html from your Javadoc. If you check the Java 7 html documentation, it's all been built with it. It's useful if you use an IDE as it can be easily accessible when you code. In Eclipse, if you put your mouse hover a method/class, it will show you the Javadoc in a well presented way. If you want more information I would suggest you visit this Oracle page.

Bracket

This is a personal choice, but I would suggest to always use brackets even if you only have one line and it's possible to omit brackets.

if(isEmpty()) return;
else if(p == p.getNext()) {
    System.out.println(p.getKey());
}
if(isEmpty()) {
  return;
} else if(p == p.getNext()) {
    System.out.println(p.getKey());
}

This will "save" you time if you need to add a new line of code in the if part. It will also prevent so weird bug if someone try to add a line, but forget that there was no brackets.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ I just want to add that the Javadoc formatting allows software to generate html documentation automatically from the comments. As you can see in Marc-Andre's example, you can even add http links. \$\endgroup\$
    – toto2
    Jul 2, 2014 at 17:05
  • 2
    \$\begingroup\$ @Joffrey Well my opinion is if you need to think what the variable name means then you had it wrong. But you're right is not an obligation and sometime short variable names are acceptable. This is the reason I used avoid instead of something like you must. It's not crystal clear. \$\endgroup\$
    – Marc-Andre
    Jul 2, 2014 at 17:08
  • 1
    \$\begingroup\$ @Marc-Andre You're right, that's why I use explicit names most of the time. In this specific case, I would have used longer names, indeed. I was rather talking about the general case. Sometimes I have integer variables that don't need explicit names, for instance. \$\endgroup\$
    – Joffrey
    Jul 2, 2014 at 17:12
  • 1
    \$\begingroup\$ A lot of excellent information here. Thank you very much! \$\endgroup\$
    – user47499
    Jul 2, 2014 at 19:31
  • 1
    \$\begingroup\$ Very good. I've always though it inconsistent that try catch needed braces, but if else didn't, so I think always using braces helps consistency/readability. \$\endgroup\$ Jul 3, 2014 at 2:56
6
\$\begingroup\$

While Marc-Andre already talked a lot about Java Style Conventions, here's my 2 cents on your implementation.

Inheriting:

You did create a List. In Java it's customary to implement Interfaces if you have classes with similar use-cases and methods.

public class list<T> {

This should/could be:

public class List<T> implements java.util.List<T> {

In fact

Naming:

I suggest you change the name of your implementation to avoid confustion. Java already comes with two lists ((interface)java.util.List and (class)java.awt.List), that are just named List, you don't really need to introduce a third one ;)

By the way, if you implement an interface you are required to Override the methods that are specified by it.

In the case of List that's quite a few, including but not restricted to:

public int size();
public boolean isEmpty();
public boolean contains(T item);
public void add(T item);
public void remove(T item);

When implementing them make sure to use the @Override annotation:

@Override
public void add(T item) {
    Node<T> oldHead = this.head;
    this.head = new Node<T>(item);
    head.setNext(oldHead);
    oldHead.setPrev(head);
    size++;
}

Which brings me to my next point:

Hiding inner classes:

There is absolutely no need to show how your list works internally by exposing a node-class to all who got your List.

Instead in Java you can use a feature called 'Inner Classes'. It's quite simple:

public class MyList<T> implements List<T> {
    private Node<T> head = null;
    private int size = 0; //you could also use long when you expect more than 2150kk items

    public MyList() {}

    private static class Node<T> {
        private final T value;
        private Node<T> next = null;
        private Node<T> prev = null;

        protected Node<T>(T value) {
            this.key = value;
        }

        T value() {
            return this.value;
        }

        void setNext(Node<T> newNext) {
            this.next = newNext;
        }

        void setPrev(Node<T> newPrev) {
            this.prev = newPrev;
        }

        Node<T> getNext() {
            return this.next;
        }

        Node<T> getPrev() {
            return this.prev;
        }
    }
    //Here goes the rest of MyList implementation
}

I am using a few tricks here:
The first thing you might probably notice is the keyword final. In case you haven't heard of it yet: The compiler enforces, that a final variable is only assigned once. This allows me to make an Instance of Node single-use only. If you want to change an item, you will have to replace it with a whole new node.

Beware this does not prevent changes to Objects themselves. It is very possible to do:

private final Map<String, String> demonstration = new HashMap<String, String>();

public void doSomething() {
    demonstration.put("Demo", "Value");
}

The other thing is that I initialize next and previous not in the constructor. This is just my personal preference!

Additionally the inner class is static. This prevents access from the inner class to the outer one when using this. For more information have a look at this CR-Answer.

While we're at constructors / initialization:

Consistency:

One big issue I see with your code, is that you don't work consistently:

public Node() {
    this.setNext(null);
    this.setPrev(null);
}

public List() {
    head = null;
}

You use quite the mix here. In the Node constructor you use the setters - even with this keyword - to instantiate your Node, in your list you do it directly - and without this - on the field.

While both may be legal, I personally prefer using the middle way. As you have seen in the code above I usually initialize fields by using the this, but not the setter methods. In case of equal names it's required to use this so I usually put it everywhere.


Example no. 2:

node<T> f = head, b = head.getPrev();

node<T> b = head.getPrev();
b.getPrev().setNext(head);

here you have some statements on one and the same line, while throughout the rest of your code, you mostly place statements on separate lines.

Here I advise to wherever possible use the second approach. One Statement has one line and one line has one (or no) statement.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for your advice! There's definitely lot of great information in here \$\endgroup\$
    – user47499
    Jul 2, 2014 at 19:32
  • \$\begingroup\$ @JordanSt.Godard I doubt you can compare them that directly ;) These Interfaces are directly included in the Java Development Kit. Again I can only state how important it is to program against an interface if you already have one given (as it is with list). This allows you to publish your List-Implementation and have it possibly used everywhere a List<T> is used. But that is up to you ;) \$\endgroup\$
    – Vogel612
    Jul 2, 2014 at 19:38
  • \$\begingroup\$ Shouldn't you use a nested class for that (with static) rather than an inner class, since members of the parent are never accessed? \$\endgroup\$
    – Ben Voigt
    Jul 2, 2014 at 22:54
  • 1
    \$\begingroup\$ @Vogel612 All non-static inner classes hold a reference to the outside this object. When no such reference is needed, it's better to declare them as static. See my answer here \$\endgroup\$ Jul 3, 2014 at 10:19
  • 2
    \$\begingroup\$ OP is not creating an implementation of java.util.List. While java.util.list does not specify that the sequence should be finite, the fact that OP's seqence will have no last element breaks assumptions made in the contract of java.util.list. \$\endgroup\$
    – Taemyr
    Jul 3, 2014 at 10:24
1
\$\begingroup\$

Although it is not a duplicate thread there is a interesting thread discussing circular lists, with a simpler approach than starting from scratch:

https://stackoverflow.com/questions/18659792/circular-arraylist-extending-arraylist

It shows simple extension of the ArrayList class and applying decorator pattern. essentially all you have to do is return the index referenced by the modulus(using the size of the ArrayList) of the required index and this will have circular behaviour. However this is a hack really and not a true circular list, where the last element holds reference to first element. One possibility I have not seen is just implementing Iterable interface to behave in a circular manner, this seems to be an ideal decoupled solution and it returns a Iterator, a much more mature approach. This has the advantage of multiple Iterators present on one list.

\$\endgroup\$

Your Answer

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