3
\$\begingroup\$

I recently submitted an implementation of a singly linked list and tried to apply some of the suggestions on this implementation. I decided not to implement the List interface as I only wanted to practice what I believed to be the most important methods. I'm wondering how I could tidy this up some more and improve upon it.

Singly Linked List: Java Singly Linked List Implementation

DoublyLinkedList.java

public class DoublyLinkedList<T> {

    private class Node {

        private T data;
        Node next, prev;

        public Node() {
        }

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

    private Node head, last;
    private int size;

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

    public void addToBeginning(T data) {
        Node temp = new Node(data);
        if (head == null) {
            head = temp;
            last = head;
        } else {
            temp.next = head;
            head.prev = temp;
            head = temp;
        }
        size++;
    }

    public void add(T data) {
        Node temp = new Node(data);
        if (head == null) {
            head = temp;
            last = head;
        } else {
            last.next = temp;
            temp.prev = last;
            last = temp;
        }
        size++;
    }

    public void add(T data, int index) {
        Node temp = new Node(data);
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        } else if (index == 0) {
            addToBeginning(data);
        } else if (index == size) {
            add(data);
        } else {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            Node previous = current.prev;
            previous.next = temp;
            temp.prev = previous;
            temp.next = current;
            current.prev = temp;
            size++;
        }
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        } else {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current.data;
        }
    }

    public void delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        } else if (index == 0) {
            head = head.next;
            head.prev = null;
            size--;
        } else if (index == size - 1) {
            last = last.prev;
            last.next = null;
            size--;
        } else {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            Node previous = current.prev;
            Node next = current.next;
            previous.next = current.next;
            next.prev = previous;
            size--;
        }
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ You're Node class doesn't seem to be finished. Don't you still need to add methods to manipulate the prev and next members? \$\endgroup\$
    – jax
    Mar 11, 2016 at 6:41
  • \$\begingroup\$ Because my node class is an inner class, my DoublyLinkedList class has full access to its fields, including next and prev. \$\endgroup\$
    – j.castillo
    Mar 11, 2016 at 16:13
  • \$\begingroup\$ A couple of things that I noticed after skimming through the code again. I overlooked making the next and prev fields of the Node class private. Also, for the sake of consistency I should have named the 'last' field of the DoublyLinkedList class 'tail'. Either 'head' and 'tail', or 'first' and 'last' would have made more sense. \$\endgroup\$
    – j.castillo
    Mar 11, 2016 at 18:04
  • \$\begingroup\$ Right, I overlooked scope. You should definitely make them private. And consistency is always important. What about also changing delete to remove? Other than that, for starters its pretty solid. \$\endgroup\$
    – jax
    Mar 12, 2016 at 5:25

3 Answers 3

Reset to default
3
\$\begingroup\$

There is one thing missing: iteration.

There is no way for the user code to get all items stored in the list without doing get(int) for each item which will result in O(n^2) time complexity.

Building the ListIterator without remove support is simple enough you just need to have it keep a reference to the current node.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I created an iterator when I was testing the functionality but removed it prior to posting. Decided to pass on implementing the 'Iterable' interface for this example. \$\endgroup\$
    – j.castillo
    Mar 11, 2016 at 17:57
1
\$\begingroup\$ 
public void add(T data) {
    Node temp = new Node(data);
    if (head == null) {
        head = temp;
        last = head;
    } else {
        last.next = temp;
        temp.prev = last;
        last = temp;
    }
    size++;
}

If head is null, do stuff, then set last to the added node. If head is not null, do other stuff, then set last to the added node.

In such cases, you should move it out of the if-statement:

public void add(T data) {
    Node temp = new Node(data);
    if (head == null) {
        head = temp;
    } else {
        last.next = temp;
        temp.prev = last;
    }
    last = temp;
    size++;
}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Just one quick point. Your add(T data, int index) function does bounds checking wrong. In the others you got it right. You have to check for index >= size.

Improve this answer
\$\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.

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