1
\$\begingroup\$

I've written a quick implementation of a doubly-linked list in java, looking for critiques and advice on approach, efficiency, and style. From my understanding, the primary advantage of using a doubly-linked list over a singly-linked list is not requiring a pointer to previous node when performing removals; are there any other real benefits? Also, would my implementation be considered a circular list, since it maintains a pointer to the tail element of the list?

DoublyLinkedList:

public class DoublyLinkedList<T> {

    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;

    public DoublyLinkedList() {
        this.head = new ListNode();
        this.size = 0;
    }

    /**
    * Inserts data element at the front of the list.
    * @param data data to insert.
    */ 
    public void insertFront(T data) {
        ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build();
        if(isEmpty()) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.head.setPrev(newNode);
            newNode.setNext(this.head);
            this.head = newNode;
        }
        this.size++;
    }

    /**
    * Inserts data element at the end of the list.
    * @param data data to insert.
    */  
    public void insertEnd(T data) {
        ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build();
        if(isEmpty()) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            ListNode<T> temp = this.tail;
            newNode.setPrev(temp);
            temp.setNext(newNode);
            this.tail = temp.getNext();
        }
        this.size++;
    }

    /**
    * Inserts element at a specific index within the list.
    * @param index position at which to insert.
    * @param data element to insert.
    */  
    public void insertAt(int index, T data) {
        ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build();
        if(isEmpty()) {
            this.head = newNode;
            this.tail = this.head;
        } else if(index == 0) {
            insertFront(data);
        } else {
            ListNode<T> temp = this.head;
            for(int i = 1; i < index; i++) {
                temp = temp.getNext();
            }
            newNode.setPrev(temp);
            newNode.setNext(temp.getNext());
            temp.setNext(newNode);
        }
        this.size++;
    }

    /**
    * Removes head element of list.
    */  
    public void removeFront() {
        if(!isEmpty()) {
            if(this.head.getNext() != null) {
                this.head = this.head.getNext();
            } else {
                this.head = null;
                this.tail = null;
            }
            this.size--;
        }
    }

    /**
    * Removes tail element of list.
    */ 
    public void removeEnd() {
        if(!isEmpty()) {
            if(this.tail.getPrev() != null) {
                this.tail = this.tail.getPrev();
            } else {
                this.tail = null;
                this.head = null;
            }
            this.size--;
        }
    }

    /**
    * Removes element at a specific index from list.
    * @param index position at which to remove element.
    */  
    public void removeAt(int index) {
        if(!isEmpty()) {
            if(index == 0) {
                removeFront();
            } else {
                ListNode<T> temp = this.head;
                for(int i = 0; i < index; i++) {
                    temp = temp.getNext();
                }
                temp.getPrev().setNext(temp.getNext());
                temp = temp.getPrev();
            }
            this.size--;
        }
    }

    /**
    * Returns the head element of the list.
    * @return the element at the head of the list
    */   
    public T getElementAtFront() {
        return (!isEmpty()) ? this.head.getData() : null;
    }

    /**
    * Returns the tail element of the list.
    * @return the tail element of the list.
    */  
    public T getElementAtEnd() {
        return (!isEmpty()) ? this.tail.getData() : null;
    }

    /**
    * Returns the element at a specific index within the list.
    * @param index position at which to search for / return element.
    * @return the element located at the given index.
    */   
    public T getElementAt(int index) {
        if(!isEmpty()) {
            if(index == 0) {
                return getElementAtFront();
            } else if(index == this.size - 1) {
                return getElementAtEnd();
            } else {
                ListNode<T> temp = this.head;
                for(int i = 0; i < index; i++) {
                    temp = temp.getNext();
                }
                return temp.getData();
            }
        }
        return null;
    }

    /**
    * Finds the index of a specific element within the list, if it exists.
    * @param data the element to search for within the list.
    * @return the index of the queried element, -1 if element does not exist within list.
    */    
    public int find(T data) {
        if(!isEmpty()) {
            ListNode<T> temp = this.head;
            int i = 0;
            while (temp != null) {
                if (temp.getData().equals(data)) {
                    return i;
                }
                temp = temp.getNext();
                i++;
            }
        }
        return -1;
    }

    /**
    * Returns contents of list in an array format.
    * @param clazz class of underlying generic type.
    * @return the array containing all list elements.
    */  
    public T[] toArray(Class<T> clazz) {
        T[] arr = (T[])Array.newInstance(clazz, this.size);
        ListNode<T> temp = this.head;
        for(int i = 0; i < arr.length; i++) {
            arr[i] = temp.getData();
            temp = temp.getNext();
        }
        return arr;
    }

    /**
    * Determines whether the underlying list structure is empty or not.
    * @return true if list is empty, false if otherwise.
    */   
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
    * Returns the current size of the list.
    * @return integer representing current list size.
    */   
    public int getSize() {
        return this.size;
    }

}

ListNode:

public class ListNode<T> {
    private T data;
    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode() {}

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

    private ListNode(ListNodeBuilder<T> builder) {
        this.data = builder.data;
        this.next = builder.next;
        this.prev = builder.prev;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

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

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

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

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

    public static class ListNodeBuilder<T> {
        private T data;
        private ListNode<T> next;
        private ListNode<T> prev;

        public ListNode<T> build() {
            return new ListNode<>(this);
        }

        public ListNodeBuilder<T> data(T data) {
            this.data = data;
            return this;
        }

        public ListNodeBuilder<T> next(ListNode<T> next) {
            this.next = next;
            return this;
        }

        public ListNodeBuilder<T> prev(ListNode<T> prev) {
            this.prev = prev;
            return this;
        }
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Constructors

In your constructor, you allocate a node for the head of the list, but never use it. The first time you insert something into the list, this allocated node will be discarded. So you can just let the head node be null like you do with the tail. (When you remove the last element of the list, you set both head and tail to null so setting them both null here would make it more consistent.)

insertFront and insertEnd

In insertFront you directly access this.head, while in insertEnd you assign this.tail to a local variable and access that. The code would be clearer if these two methods used the same approach (using this.head and this.tail directly).

insertAt

insertAt has inconsistent behavior. If the list is empty, it ignores the requested position and always inserts the element. But if there are elements in the list, and the requested insertion location is more than the size of the list, you'll walk off the end of the list and get an exception. This can cause things like

DoublyLinkedList<int> lst = new DoublyLinkedList<int>;
lst.insert(1, 3);
lst.insert(1, 4);

to result in an exception on the second insert, when it should generate one on the first. This should check to see if index is valid first, and take appropriate measures (either throw an exception or not insert anything, depending on how you want to handle it).

Another problem with insertAt is it doesn't update the tail node if the insert location is the end of the list.

removeAt

removeAt has many of the same problems as insertAt. It doesn't update this.tail when removing the last element, and trying to remove an element that isn't in the list could be detected early and an appropriate exception thrown, rather than walking the whole list and getting a null dereference exception.

getElementAt

getElementAt does not need to check for index to be for the first or last elements in the list, as the loop will handle that just fine.

If speed is a consideration, this could be sped up a bit by seeing if the desired element is in the second half of the list, then starting at the tail and walking towards the front of the list to locate it.

ListNodeBuilder

I'm not quite sure why you're using ListNodeBuilder. You never set any links in it (only the data), which could be done directly using ListNode.

\$\endgroup\$
2
  • \$\begingroup\$ thanks for the insights; didn't catch those out-of-bounds exceptions, and now I feel silly. Quick question though on GetElementAt's implementation...wouldn't it be more efficient to have a quick check to see if the supplied index is referencing the last element in the list, and then calling the getElementAtEnd method instead of traversing the entire list, in the case of a large list size? \$\endgroup\$
    – koprulu
    Feb 2, 2018 at 15:04
  • 1
    \$\begingroup\$ @koprulu It depends on how often GetElementAt is called to get the last element. While it can save a lot of time for that one element, it comes at the expense of a little more time (for the check) when accessing every other element. If this is a common case, then doing adding a "check for index in the second half of the list" that I mention in my answer would help more. \$\endgroup\$ Feb 2, 2018 at 15:17

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.