Singly Linked List implementation in Java

Question

Here's my implementation of a Singly Linked List. Would appreciate a review.

public class SList<T> {
 private Node head;
 private int size;
 private class Node<T>{
 public Node(){
 item = null;
 next = null;
 }
 public Node(T item){
 this.item = item;
 this.next = null;
 }
 private T item;
 private Node next;
 }//end of node
 //constructor
 public SList(){
 head = null;
 size = 0;
 }
 public void add(T item){
 Node p = new Node(item);
 if(head == null){
 head = p;
 size++;
 return;
 }
 p.next = head;
 head = p;
 size++;
 }
 public boolean isEmpty(){
 return size == 0;
 }
 public int getSize(){
 return size;
 }
 public void remove(T item){
 Node current = head;
 while(current.next != item){
 if(current.next == null) {
 System.out.println("Item doesn't exist in the list:");
 return;
 }
 current = current.next;
 }
 current.next = current.next.next;
 size--;
 }
 public void insertAfter(T item1, T item2){
 Node current = head;
 Node p = new Node(item2);
 do{
 if(current == null) {
 System.out.println("Item doesn't exist in the list:");
 return;
 }
 current = current.next;
 }while(current.item != item1);
 Node q = current.next;
 current.next = p;
 p.next = q;
 size++;
 }
 public void insertBefore(T item1, T item2){
 Node current = head;
 Node p = new Node(item2);
 do{
 if(current.next == null) {
 System.out.println("Item doesn't exist in the list:");
 return;
 }
 current = current.next;
 }while(current.next.item != item1);
 Node q = current.next;
 current.next = p;
 p.next = q;
 size++;
 }
}

• Emz: this.next = null; all those null initializes are redundant as Java uses default values for fields. The default value for Objects is null.

Answer 1

General

Default Values

Java uses default values for all its fields. Meaning :

public Node(){
 item = null;
 next = null;
}

Does nothing except take up space for you. I would remove it, and the other lines / constructors like it. Some consider it bad practice to rely on the default values, you can then explicitly state the default value of a field on the same row as you are declaring it.

private Node head = null;

Reference

Inconsistency

You are inconsistent at spacing your code. I also recommend having fields at the right below the class declaration. I should not have to look for the fields, I want to find them instantly.

Bug in remove, insertBefore

If head is null, then current.next will throw a NullPointerException. I suggest guarding against null for head first in the method.

if (head == null) {
 System.out.println ("Item doesn't exist in the list.");
 return;
}

Nitpicks

public void add(T item)

You always execute the size++; why have it in two different places? And not directly under Node p = new Node (item);

public boolean isEmpty()

Looks perfect, why can't every method turn out to be like this? One option is to match against head == null as well, however in terms micro-optimization, it is slower.

public int getSize()

Nothing needs to be said, a simple getter.

public void remove(T item)

Instead of letting it handle the error printing, let remove return a boolean, true if removed, false if not, making it more flexible to use in future applications.

Answer 2

remove needs to check for an empty list (head == null) before searching. And I think you meant while (current.item != item) in there.

insertAfter advances past the first element before checking for the value, so it will fail if you're trying to insert after the first one. insertBefore has the same problem.

The 'find node in list' code can go into a method, rather than duplicating it in several methods.

• Fabio Filippi: Is current.next.item, you have to stop one node before to be able to skip it.

Answer 3

There is a bug in the remove function

while(current.next != item){

You are comparing a node with an item, you should compare current.next.item.

I would also add and use getters/setters methods to Node class: getNext(), getItem(), setNext(), setItem().