current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 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.

(Newer code bellow!)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;
        }
    }
}

Updated after recommendations:

public class LinkedList<T> {

    private Node<T> first;
    private int size;

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

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

    public void add(T data) {
        Node<T> current = this.first;

        if (current == null) {
            this.first = new Node(data);
            this.size++;
            return;
        }

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

        current.setNext(new Node(data));
        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());
                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;
        }
    }
}

Anything I could do to make it better?

share|improve this question

4 Answers 4

up vote 9 down vote

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. –  Sillicon Touch 13 hours ago
    
@SilliconTouch I would say you have these three cases: empty list, deleting root (!= one element list), rest of cases. –  tim 13 hours ago
    
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. –  Sillicon Touch 12 hours ago
    
@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 12 hours ago
    
You are right since whatever first.next is that is what the first is going to be. Thank you. –  Sillicon Touch 12 hours ago
up vote 3 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.). –  Sillicon Touch 12 hours ago
    
@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 12 hours ago
    
I added the toString() and contains(T data) methods for debugging. –  Sillicon Touch 12 hours ago
    
@SilliconTouch: Slight update to my answer –  ChrisWue 3 hours ago
up vote 1 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
up vote 0 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

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.