current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 8 down vote favorite

I am brushing up my Data Structure knowledge (for preparation for internship interviews) and I started by implementing a very simple Linked List class. This is by no means intended to be able to replace the Java library just to be something robust enough for making me understand and remember how to implement a Linked List.

LinkedList class with private Node class:

public class LinkedList<T> {

    private Node _first;
    private int _size;

    public LinkedList() {
        _first = null;
        _size = 0;
    }

    public int getSize() {
        return _size;
    }

    public void add(T data) {
        Node current = _first;

        if (current == null) {
            _first = new Node(data);
            _size++;
            return;
        }

        while (current.getNext() != null) {
            current = current.getNext();
        }

        current.setNext(new Node(data));
        _size++;
    }

    public void add(T[] array) {
        for (T data : array) {
            add(data);
        }
    }

    public void remove(T data) {
        Node current = _first;
        Node next = current.getNext();

        if (_first.getData().equals(data)) {
            if (_size == 1) {
                _first.setData(null);
                _size--;
                return;
            }
            _first.setData(null);
            _first = _first.getNext();
            _size--;
            return;
        }

        while (next != null) {
            if (next.getData().equals(data)) {
                current.setNext(next.getNext());
                next = null;
                _size--;
                return;
            }
            current = next;
            next = current.getNext();
        }
    }

    private class Node<T> {

        private T _data;
        private Node _next;

        public Node(T data) {
            _data = data;
            _next = null;
        }

        public void setData(T data) {
            _data = data;
        }

        public T getData() {
            return _data;
        }

        public void setNext(Node next) {
            _next = next;
        }

        public Node getNext() {
            return _next;
        }
    }
}

Anything I could do to make it better?

share|improve this question
    
What you can and cannot do after receiving answers –  Jamal♦ Oct 14 '14 at 15:46
    
@Jamal If I post a self-answer I don't have to accept that answer as the correct one right? It's just that I believe's tim's answer was the correct one (most helpful) but I would like to have my finalised code for others to see when they stumble upon the question. –  Aki K Oct 14 '14 at 15:55
    
Yes, it would be best to only accept the answer that has helped the most. If your answer was based on another answer, then you shouldn't accept your own. –  Jamal♦ Oct 14 '14 at 15:56
    
Alright, I will do that then later in the day. –  Aki K Oct 14 '14 at 15:57

5 Answers 5

up vote 11 down vote accepted

raw types

Try to avoid raw types. private Node fieldname should be private Node<T> fieldname, same for function returns and method arguments.

Bug

If I do this:

MyLinkedList<String> list = new MyLinkedList<>();
list.remove("foo");

I get a NullPointerException. This is because you first access data of the root, and then check what the size is. It should be the other way around (and checking if the root is null would be a bit clearer).

You also shouldn't set the data to null, you should remove the node, otherwise you have a root node that contains null (also, your list size is wrong from there on out).

It also doesn't make that much sense to first set the data, and then override the node. In that case, just remove the setting of the data.

remove non existing element

If a non existing element is removed, you could throw a NoSuchElementException (it's what Java lists do).

Setting values to null

next = null; this isn't necessary, you are returning right afterwards.

Naming

  • it is a bit uncommon to start a field name with _.
  • I would conform to the names of the List interface (getSize -> size, add(array) -> addAll(array).
share|improve this answer
    
For the bug what I should basically do is have 3 possibilities right? One if the list is empty, one if the list has one element and one for the rest of the cases. –  Aki K Oct 10 '14 at 17:56
    
@SilliconTouch I would say you have these three cases: empty list, deleting root (!= one element list), rest of cases. –  tim Oct 10 '14 at 18:03
    
I updated the code with your recommendations but I feel that I ended up with 4 cases: empty list, deleting root (size == 1), deleting root (size > 1), rest of cases. I have the new code in the post. –  Aki K Oct 10 '14 at 18:31
    
@SilliconTouch I think that you could remove one of those. In the this.first.getData().equals(data) case, you should be able to just do this: this.first = this.first.getNext(); this.size--;. –  tim Oct 10 '14 at 18:37
    
You are right since whatever first.next is that is what the first is going to be. Thank you. –  Aki K Oct 10 '14 at 18:39
up vote 0 down vote

After the recommendations posted here I altered my code mostly following @tim's advice.

Some other improvements I made include adding the last pointer (which makes the add operation time O(1) from O(N) and the contains(T data) method.

This is the finalized LinkedList class:

import java.util.NoSuchElementException;

public class LinkedList<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    public LinkedList() {
        this.first = this.last = null;
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    public void add(T data) {
        Node<T> node = new Node(data);
        if (this.first == null) {
            this.first = this.last = node;
        }else{
            this.last.setNext(node);
            this.last = node;
        }
        this.size++;
    }

    public void addAll(T[] array) {
        for (T data : array) {
            add(data);
        }
    }

    public void remove(T data) {
        if (this.first == null) {
            throw new NoSuchElementException();
        } else if (this.first.getData().equals(data)) {
            this.first = this.first.getNext();
            this.size--;
            return;
        }

        Node<T> current = this.first;
        Node<T> next = current.getNext();
        while (next != null) {
            if (next.getData().equals(data)) {
                current.setNext(next.getNext());
                if (current.getNext() == null) {
                    this.last = current;
                }
                this.size--;
                return;
            }
            current = next;
            next = current.getNext();
        }

        throw new NoSuchElementException();
    }

    public boolean contains(T data) {
        Node<T> current = this.first;

        while (current != null) {
            if (current.getData().equals(data)) {
                return true;
            }
            current = current.getNext();
        }
        return false;

    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        buffer.append("{");

        Node<T> current = this.first;
        while (current != null) {
            buffer.append(current.getData());

            if (current.getNext() != null) {
                buffer.append(", ");
            }

            current = current.getNext();
        }

        buffer.append("}");

        return buffer.toString();
    }

    private class Node<T> {

        private T data;
        private Node<T> next;

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

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

        public T getData() {
            return this.data;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node getNext() {
            return this.next;
        }
    }
}
share|improve this answer
up vote 4 down vote

  1. You could store a pointer to the last element as well so that add operations become O(1), right now they are O(n).

  2. I might be mistaken but right now you can only add elements to the list and remove them but there is no way to iterate over the list or access an element - this diminishes its usefulness somewhat.

Update: I don't know how it is in Java but in .NET .ToString() is meant to return a short helpful description about the object largely for debugging and diagnostics. Dumping the entire list content is probably not very wise - imagine the list contains tens of thousands of entries.

share|improve this answer
    
I plan on adding the last pointer but after I get the basics 100% correct. I will also add the rest of the methods later (like contains, find etc.). –  Aki K Oct 10 '14 at 18:33
    
@SilliconTouch some methods can wait, but an option to traverse the list (and/or print it) are really important, because otherwise you cannot test it. –  tim Oct 10 '14 at 18:43
    
I added the toString() and contains(T data) methods for debugging. –  Aki K Oct 10 '14 at 18:51
    
@SilliconTouch: Slight update to my answer –  ChrisWue Oct 11 '14 at 3:47
    
@ChrisWue re toString: It's different for Java: "Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator". And I think that an output like [1, 2, 3] is a lot more helpful than just a hash value and maybe a list size. –  tim Oct 11 '14 at 11:03
up vote 1 down vote

Your addAll method is inefficient. You're finding the end of the list many times more than is necessary. Instead, consider the following:

public void addAll(T[] array) {
    Node current = this.first;
    while (current.getNext() != null) {
        current = current.getNext();
    }
    // we now have current as the last node - now we can start adding
    for(T t : array) {
        current.setNext(new Node(t));
        current = current.getNext();
    }
    size += array.length;
}

This doesn't cover the speical case of adding the array to an empty list, but I'm sure that would make a trivial exercise.

share|improve this answer
    
I plan on fixing the inefficiency by adding the last pointer. That will make every insertion O(1) therefore the addAll will be O(N). –  Aki K Oct 11 '14 at 11:25
up vote 2 down vote

I don't think special cases in remove are warranted. Streamline the flow by referencing a previous node instead of next, along the lines of

    Node previous = null;
    Node current = _first;

    while (current != null) {
        if (current.getData().equals(data)) {
            if (previous == null) {
                _first = current.getNext();
            } else {
                previous.setNext(current.getNext());
            }
            --_size;
            return;
        }
        previous = current;
        current = current.getNext();
    }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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