Stack and Queue implemented with a LinkedList

Question

I am looking for feedback on my implementations of Queue, Stack, and LinkedList using Java generics. I would very much appreciate feedback on what I can improve and any errors I made.

LinkedList

public class LinkedList<T> {
 private int size;
 private Node<T> head;
 public LinkedList() {
 this.head = null;
 this.size = 0;
 }
 public int size() {
 return size;
 }
 public boolean isEmpty() {
 return this.size == 0;
 }
 public boolean contains(T element) {
 Node<T> current = head;
 while(current != null) {
 if(current.getValue().equals(element)) {
 return true;
 }
 current = current.getNext();
 }
 return false;
 }
 public boolean add(T e) {
 Node<T> toAdd = new Node<T>(e, null);
 if(head == null) {
 this.head = toAdd;
 } else {
 Node<T> current = head;
 while(current.getNext() != null) {
 current = current.getNext();
 }
 current.setNext(toAdd);
 }
 size++;
 return true;
 }
 public boolean remove(T e) {
 Node<T> current = head;
 if(head.getValue().equals(e)) {
 head = head.getNext();
 size--;
 return true;
 }
 while(current.getNext() != null) {
 if(current.getNext().getValue().equals(e)) {
 current.setNext(current.getNext().getNext());
 size--;
 return true;
 }
 current = current.getNext();
 }
 return false;
 }
 public T get(int index) {
 int count = 0; 
 if(index >= size) {
 return null;
 }
 Node<T> current = head;
 while(count != index) {
 current = current.getNext();
 count++;
 }
 return current.getValue();
 }
 public T set(int index, T element) {
 int count = 0;
 if(index >= size) {
 return null;
 }
 Node<T> current = head;
 while(count != index) {
 current = current.getNext();
 count++;
 }
 current.setValue(element);
 return current.getValue();
 }
 public void add(int index, T element) {
 int count = 0;
 if(index > size) {
 return;
 } 
 if(index == 0) {
 Node<T> add = new Node<T>(element, head);
 this.head = add;
 size++;
 return;
 }
 Node<T> current = head;
 if(index == size) {
 while(current.getNext() != null) {
 current = current.getNext();
 }
 Node<T> toAdd = new Node<T>(element, null);
 current.setNext(toAdd);
 size++;
 return;
 }
 while((count + 1) != index) {
 current = current.getNext();
 count++;
 }
 Node<T> toAdd = new Node<T>(element, current.getNext());
 current.setNext(toAdd);
 size++;
 }
 public T remove(int index) {
 int count = 0;
 if(index >= size) {
 return null;
 }
 if(index == 0) {
 T toReturn = head.getValue();
 this.head = head.getNext();
 size--;
 return toReturn;
 }
 Node<T> current = head;
 while((count + 1) != index) {
 current = current.getNext();
 count++;
 }
 T toReturn = current.getNext().getValue();
 current.setNext(current.getNext().getNext());
 size--;
 return toReturn;
 }
 public int indexOf(T element) {
 int count = 0;
 Node<T> current = head;
 while(current.getNext() != null) {
 if(current.getValue().equals(element)) {
 return count;
 }
 current = current.getNext();
 count++;
 }
 return -1;
 }
 public String toString() {
 Node<T> current = head;
 String string = "";
 while(current != null) {
 string += current.getValue().toString();
 string += ", ";
 current = current.getNext();
 }
 return string;
 }
 private class Node<E> {
 private E thing;
 private Node<E> next;
 public Node(E thing, Node<E> next) {
 this.thing = thing;
 this.next = next;
 }
 public E getValue() {
 return this.thing;
 }
 public Node<E> getNext() {
 return this.next;
 }
 public void setValue(E thing) {
 this.thing = thing;
 }
 public void setNext(Node<E> next) {
 this.next = next;
 }
 }
}

Queue

public class Queue<T> {
 private LinkedList<T> list;
 public Queue() {
 list = new LinkedList<T>();
 }
 public void add(T element) {
 list.add(list.size(), element);
 }
 public T remove() {
 return list.remove(0);
 }
 public T peek() {
 return list.get(0);
 }
 public String toString() {
 return list.toString();
 }
}

Stack

public class Stack<T> {
 private LinkedList<T> list;
 public Stack() {
 list = new LinkedList<T>();
 }
 public boolean empty() {
 return list.isEmpty();
 }
 public T push(T element) {
 list.add(0, element);
 return element;
 }
 public T pop() {
 T element = list.remove(0);
 return element;
 }
 public T peek() {
 return list.get(0);
 }
 public int search(T element) {
 return list.indexOf(element);
 }
 public String toString() {
 return list.toString();
 }
}

• Thijs Riezebeek: The add method on your LinkedList now silently does nothing when the index is incorrect. Instead you should be throwing an exception to let the caller know that they did something wrong.

Answer 1

LinkedList

 private int size;
 private Node<T> head;
 public LinkedList() {
 this.head = null;
 this.size = 0;
 }

You could just write this as

 private int size = 0;
 private Node<T> head = null;

You don't actually need a constructor for this.

 Node<T> current = head;
 while(current != null) {
 if(current.getValue().equals(element)) {
 return true;
 }
 current = current.getNext();
 }

You can also write this as

 for (Node<T> current = head; current != null; current = current.getNext()) {
 if (current.getValue().equals(datum)) {
 return true;
 }
 }

I changed element to datum, as I would expect an element to be a Node rather than a Node value.

Functionally both the for and the while do the same thing. The for is arguably more readable and uses fewer lines.

 if(head == null) {
 this.head = toAdd;
 } else {
 Node<T> current = head;

You use head twice and this.head once here. Why not always use head? It's shorter and doesn't imply that you are using two different variables. You seem to be writing out this.head whenever you assign to it. You only have to do so when you have two variables with the same name that you disambiguate with the this..

 while((count + 1) != index) {

This would be easier to follow as

 while (count < index) {

Then you don't have to play around with extra math.

Consider using LinkedList

Java has its own LinkedList class that implements the List interface. Perhaps this is simply a programming exercise, but normally you'd just use that class.

Putting the reinventing-the-wheel tag on your question would let people know that you are deliberately reimplementing rather than accidentally.

Paragraphing

I'd find this easier to follow with more vertical whitespace. As a rough rule of thumb, I'd almost always add a blank line after any closing } (i.e. not an } else { but anytime the block of code ends) that is followed by more code.

Double LinkedList

Consider using a double linked list for a queue. That way both head and tail are easy to find.

Array

Consider using an array to store a stack. Since the head always stays in the same place and only the tail changes, an array holds all the information you need (although you have to maintain size yourself) and is lower overhead than a linked list. This is also true of an ArrayList which also maintains the size for you.

Answer 2

In addition to everything @mdfst13 said in his/her review, consider this:

public String toString() {
 Node<T> current = head;
 String string = "";
 while(current != null) {
 string += current.getValue().toString();
 string += ", ";
 current = current.getNext();
 }
 return string;
 }

In Java, strings are immutable objects. Each of the += operations you're doing on it is actually creating new temporary copies of the old string in the process. The fix is to use a StringBuilder to build the string out and prevent all the temporary copies being made:

public String toString() {
 Node<T> current = head;
 StringBuilder sb = new StringBuilder();
 while(current != null) {
 sb.append(current.getValue().toString());
 sb.append(", ");
 current = current.getNext();
 }
 return sb.toString();
 }

Also, since your Node class is internal to the LinkedList class, I don't really see a need for having the Node class members be private and having setters/getters for them if the only code able to access them is the LinkedList class anyway. While I realize this is "good OO practice", in this particular case, I think it just leads to more verbose code. I would consider just making the member methods public and allowing the LinkedList class to just access them directly. Finally, I'd probably add another constructor to the Node class that would assign the next value to null for me:

 public Node(E thing) {
 this.thing = thing;
 this.next = null;
 }