Doubly-Linked Circular Linked List

Question

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;
}

Answer 1

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.

Answer 2

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.

Answer 3

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.