Simple LinkedList implementation

Question

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?

Answer 1

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).

• Aki K: 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.
• tim: @SilliconTouch I would say you have these three cases: empty list, deleting root (!= one element list), rest of cases.
• Aki K: 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.
• tim: @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--;.
• Aki K: You are right since whatever first.next is that is what the first is going to be. Thank you.

Answer 2

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.

• Aki K: 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.).
• tim: @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.
• Aki K: I added the toString() and contains(T data) methods for debugging.
• ChrisWue: @SilliconTouch: Slight update to my answer
• tim: @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.

Answer 3

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

Answer 4

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.

• Aki K: 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).

Answer 5

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