linked list implementation java

Question

I have implemented a Linked List into Java. I have created everything, but I am having difficulty removing a specific node with specific data. It is throwing a NullPointerException. I believe, I am getting a NullPointerException because the next node is null. If someone could please point me in the right direction that would be great.

Input

anything
one
two
three

exception:

Exception in thread "main" java.lang.NullPointerException
 at LinkedList.remove(LinkedList.java:28)
 at Main.main(Main.java:29)

Classes: Linked list class

public class LinkedList {
 // fields
 private Node head;
 private Node last;
 private int size = 0;
 // constructor, used when the class is first called
 public LinkedList() {
 head = last = new Node(null);
 }
 // add method
 public void add(String s) {
 last.setNext(new Node(s));
 last = last.getNext();
 size++;
 }
 // remove method, if it returns false then the specified index element doens not exist
 // otherwise will return true
 public boolean remove(String data) {
 Node current = head;
 last = null;
 while(current != null) {
 if(current.getData().equals(data)) {
 current = current.getNext();
 if(last == null) {
 last = current;
 }else {
 last.getNext().setNext(current);
 size--;
 return true;
 }
 }else {
 last = current;
 current = current.getNext();
 }
 }
 return false;
 }
 //will return the size of the list - will return -1 if list is empty
 public int size() {
 return size;
 }
 // will check if the list is empty or not
 public boolean isEmpty() {
 return true;
 }
 // @param (index) will get the data at specified index
 public String getData(int index) {
 if(index <= 0) {
 return null;
 }
 Node current = head.getNext();
 for(int i = 1;i < index;i++) {
 if(current.getNext() == null) {
 return null;
 }
 current = current.getNext();
 }
 return current.getData();
 }
 //@param will check if the arguement passed is in the list
 // will return true if the list contains arg otherwise false
 public boolean contains(String s) {
 for(int i = 1;i<=size();i++) {
 if(getData(i).equals(s)) {
 return true;
 }
 }
 return false;
 }
 //@return contents of the list - recursively 
 public String toString() {
 Node current = head.getNext();
 String output = "[";
 while(current != null) {
 output += current.getData()+",";
 current = current.getNext();
 }
 return output+"]";
 }
 //@return first node
 public Node getHead() {
 return head;
 }
 // @return (recursively) list
 public void print(Node n) {
 if(n == null) {
 return;
 }else {
 System.out.println(n.getData());
 print(n.getNext());
 }
 }
}

Main

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 public static void main(String[] args) throws IOException{
 LinkedList list = new LinkedList(); // declaring main linked list
 LinkedList b_List = new LinkedList(); // declaring the backup list
 String input = null;
 // getting input from user, will stop when user has entered 'fin'
 while(!(input = br.readLine()).equals("fin")) {
 list.add(input); // adding to main list
 b_List.add(input);
 }
 list.print(list.getHead().getNext());
 System.out.println("Input Complete.");
 if(list.size() == 1) {
 System.out.println("You have entered only one name. He/She is the survior");
 }else {
 System.out.println("Enter the name(s) would like to remove: ");
 while(b_List.size() != 1) {
 String toRemove = br.readLine();
 b_List.remove(toRemove);
 }
 }
 System.out.println("The contestants were: ");
 list.print(list.getHead().getNext());
 }
}

node

public class Node {
 // Fields
 private String data;
 private Node next;
 // constructor
 public Node(String data) {
 this(data,null);
 }
 // constructor two with Node parameter
 public Node(String data, Node node) {
 this.data = data;
 next = node;
 }
 /**
 * Methods below return information about fields within class
 * */
 // @return the data
 public String getData() {
 return data;
 }
 // @param String data to this.data
 public void setData(String data) {
 this.data = data;
 }
 // @return next
 public Node getNext() {
 return next;
 }
 // @param Node next set to this.next
 public void setNext(Node next) {
 this.next = next;
 }
}

• user684934: Question: why does an empty list imply size -1? Isn't the initial list (size 0) also empty?

Answer 1

First of all, your head is just a before-first marker so you shouldn't start the remove check from it.

Second, your remove method fails if node data is null

Third - your implementation is broken anyway because of last.getNext().setNext(current) - it won't link previous node with next, it will link current to next (i.e. will do nothing)

Fourth - it still fails to remove first element because of mysterious operations with last...

Correct implementation of remove would be something like this:

public boolean remove(String data){
 Node previous = head;
 Node current = head.getNext();
 while (current != null) {
 String dataOld = current.getData();
 if ((dataOld == null && data == null) || (dataOld != null && dataOld.equals(data))) {
 Node afterRemoved = current.getNext();
 previous.setNext(afterRemoved);
 if (afterRemoved == null) { // i.e. removing last element
 last = previous;
 }
 size--;
 return true;
 } else {
 previous = current;
 current = current.getNext();
 }
 }
 return false;
}

• Alex Abdugafarov: Yes, it's Java 7 shortcut. I've edited the answer, now it should work for you.

Answer 2

Here we can see the simple implementation of LinkedList with iterator

 class LinkedList implements Iterable{
 private Node node;
 public void add(Object data){
 if(!Optional.ofNullable(node).isPresent()){
 node = new Node();
 node.setData(data);
 }else{
 Node node = new Node();
 node.setData(data);
 Node lastNode = getLastNode(this.node);
 lastNode.setNext(node);
 }
 }
 private Node getLastNode(Node node){
 if(node.getNext()==null){
 return node;
 }else{
 return getLastNode(node.getNext());
 }
 } 
 class Node{
 private Object data;
 private Node next;
 public Object getData() {
 return data;
 }
 public void setData(Object data) {
 this.data = data;
 }
 public Node getNext() {
 return next;
 }
 public void setNext(Node next) {
 this.next = next;
 }
 }
 public Iterator iterator() {
 return new NodeIterator();
 }
 class NodeIterator implements Iterator{
 private Node current;
 public boolean hasNext() {
 if(current == null){
 current = node;
 return Optional.ofNullable(current).isPresent();
 }else{
 current = current.next;
 return Optional.ofNullable(current).isPresent();
 }
 }
 public Node next() {
 return current;
 }
 }
 }
 public class LinkedListImpl {
 public static void main(String[] args) {
 LinkedList linkedList = new LinkedList();
 linkedList.add("data1");
 linkedList.add("data2");
 linkedList.add("data3");
 for(LinkedList.Node node: linkedList){
 System.out.println(node.getData());
 }
 }
 }

Answer 3

Here is Full Implementaion of Linked List

including insertion,deletion,searching,reversing,swaping,size,display and various important operations of linked list

import java.util.NoSuchElementException;
import java.util.Scanner;
class Node<T> {
 public Node<T> next;
 public T data;
 public Node() {
 }
 public Node(T data, Node<T> next) {
 this.data = data;
 this.next = next;
 }
 @Override
 public String toString() {
 return "Node [next=" + next + ", data=" + data + "]";
 }
}
class LinkedList<T> {
 Node<T> start = null;
 Node<T> end = null;
 public void insertAtStart(T data) {
 Node<T> nptr = new Node<T>(data, null);
 if (empty()) {
 start = nptr;
 end = start;
 } else {
 nptr.next = start;
 start = nptr;
 }
 display();
 }
 public void insertAtEnd(T data) {
 Node<T> nptr = new Node<T>(data, null);
 if (empty()) {
 insertAtStart(data);
 return;
 } else {
 end.next = nptr;
 end = nptr;
 }
 display();
 }
 public void insertAtPosition(int position, T data) {
 if (position != 1 && empty())
 throw new IllegalArgumentException("Empty");
 if (position == 1) {
 insertAtStart(data);
 return;
 }
 Node<T> nptr = new Node<T>(data, null);
 if (position == size()) {
 Node<T> startPtr = start;
 Node<T> endPtr = startPtr;
 while (startPtr.next != null) {
 endPtr = startPtr;
 startPtr = startPtr.next;
 }
 endPtr.next = nptr;
 nptr.next = end;
 } else {
 position -= 1;
 Node<T> startPtr = start;
 for (int i = 1; i < size(); i++) {
 if (i == position) {
 Node<T> temp = startPtr.next;
 startPtr.next = nptr;
 nptr.next = temp;
 }
 startPtr = startPtr.next;
 }
 }
 display();
 }
 public void delete(int position) {
 if (empty())
 throw new IllegalArgumentException("Empty");
 if (position == 1) {
 start = start.next;
 } else if (position == size()) {
 Node<T> startPtr = start;
 Node<T> endPtr = start;
 while (startPtr.next != null) {
 endPtr = startPtr;
 startPtr = startPtr.next;
 }
 endPtr.next = null;
 end = endPtr;
 } else {
 position -= 1;
 Node<T> startPtr = start;
 for (int i = 1; i <= position; i++) {
 if (i == position) {
 Node<T> temp = startPtr.next.next;
 startPtr.next = temp;
 }
 startPtr = startPtr.next;
 }
 }
 display();
 }
 public int index(T data) {
 if (empty())
 throw new IllegalArgumentException("Empty");
 return index(start, data, 0);
 }
 private int index(Node<T> link, T data, int index) {
 if (link != null) {
 if (link.data == data) {
 return index;
 }
 return index(link.next, data, ++index);
 }
 return -1;
 }
 public void replace(int position, T data) {
 if (empty())
 throw new IllegalArgumentException("Empty");
 if (position == 1)
 start.data = data;
 else if (position == size())
 end.data = data;
 else {
 Node<T> startPtr = start;
 for (int i = 1; i <= position; i++) {
 if (i == position)
 startPtr.data = data;
 startPtr = startPtr.next;
 }
 }
 display();
 }
 public void replaceRecursively(int position, T data) {
 replaceRecursively(start, position, data, 1);
 display();
 }
 private void replaceRecursively(Node<T> link, int position, T data, int count) {
 if (link != null) {
 if (count == position) {
 link.data = data;
 return;
 }
 replaceRecursively(link.next, position, data, ++count);
 }
 }
 public T middle() {
 if (empty())
 throw new NoSuchElementException("Empty");
 Node<T> slowPtr = start;
 Node<T> fastPtr = start;
 while (fastPtr != null && fastPtr.next != null) {
 slowPtr = slowPtr.next;
 fastPtr = fastPtr.next.next;
 }
 return slowPtr.data;
 }
 public int occurence(T data) {
 if (empty())
 throw new NoSuchElementException("Empty");
 return occurence(start, data, 0);
 }
 private int occurence(Node<T> link, T data, int occurence) {
 if (link != null) {
 if (link.data == data)
 ++occurence;
 return occurence(link.next, data, occurence);
 }
 return occurence;
 }
 public void reverseRecusively() {
 reverseRecusively(start);
 swapLink();
 display();
 }
 private Node<T> reverseRecusively(Node<T> link) {
 if (link == null || link.next == null)
 return link;
 Node<T> nextLink = link.next;
 link.next = null;
 Node<T> revrseList = reverseRecusively(nextLink);
 nextLink.next = link;
 return revrseList;
 }
 public void reverse() {
 if (empty())
 throw new NoSuchElementException("Empty");
 Node<T> prevLink = null;
 Node<T> currentLink = start;
 Node<T> nextLink = null;
 while (currentLink != null) {
 nextLink = currentLink.next;
 currentLink.next = prevLink;
 prevLink = currentLink;
 currentLink = nextLink;
 }
 swapLink();
 display();
 }
 private void swapLink() {
 Node<T> temp = start;
 start = end;
 end = temp;
 }
 public void swapNode(T dataOne, T dataTwo) {
 if (dataOne == dataTwo)
 throw new IllegalArgumentException("Can't swap " + dataOne + " and " + dataTwo + " both are same");
 boolean foundDataOne = false;
 boolean foundDataTwo = false;
 Node<T> dataOnePtr = start;
 Node<T> dataOnePrevPtr = start;
 while (dataOnePtr.next != null && dataOnePtr.data != dataOne) {
 dataOnePrevPtr = dataOnePtr;
 dataOnePtr = dataOnePtr.next;
 }
 Node<T> dataTwoPtr = start;
 Node<T> dataTwoPrevPtr = start;
 while (dataTwoPtr.next != null && dataTwoPtr.data != dataTwo) {
 dataTwoPrevPtr = dataTwoPtr;
 dataTwoPtr = dataTwoPtr.next;
 }
 if (dataOnePtr != null && dataOnePtr.data == dataOne)
 foundDataOne = true;
 if (dataTwoPtr != null && dataTwoPtr.data == dataTwo)
 foundDataTwo = true;
 if (foundDataOne && foundDataTwo) {
 if (dataOnePtr == start)
 start = dataTwoPtr;
 else if (dataTwoPtr == start)
 start = dataOnePtr;
 if (dataTwoPtr == end)
 end = dataOnePtr;
 else if (dataOnePtr == end)
 end = dataTwoPtr;
 Node<T> tempDataOnePtr = dataOnePtr.next;
 Node<T> tempDataTwoPtr = dataTwoPtr.next;
 dataOnePrevPtr.next = dataTwoPtr;
 dataTwoPtr.next = tempDataOnePtr;
 dataTwoPrevPtr.next = dataOnePtr;
 dataOnePtr.next = tempDataTwoPtr;
 if (dataOnePtr == dataTwoPrevPtr) {
 dataTwoPtr.next = dataOnePtr;
 dataOnePtr.next = tempDataTwoPtr;
 } else if (dataTwoPtr == dataOnePrevPtr) {
 dataOnePtr.next = dataTwoPtr;
 dataTwoPtr.next = tempDataOnePtr;
 }
 } else
 throw new NoSuchElementException("Either " + dataOne + " or " + dataTwo + " not in the list");
 display();
 }
 public int size() {
 return size(start, 0);
 }
 private int size(Node<T> link, int i) {
 if (link == null)
 return 0;
 else {
 int count = 1;
 count += size(link.next, 0);
 return count;
 }
 }
 public void printNthNodeFromLast(int n) {
 if (empty())
 throw new NoSuchElementException("Empty");
 Node<T> main_ptr = start;
 Node<T> ref_ptr = start;
 int count = 0;
 while (count < n) {
 if (ref_ptr == null) {
 System.out.println(n + " is greater than the no of nodes in the list");
 return;
 }
 ref_ptr = ref_ptr.next;
 count++;
 }
 while (ref_ptr != null) {
 main_ptr = main_ptr.next;
 ref_ptr = ref_ptr.next;
 }
 System.out.println("Node no " + n + " from the last is " + main_ptr.data);
 }
 public void display() {
 if (empty())
 throw new NoSuchElementException("Empty");
 display(start);
 }
 private void display(Node<T> link) {
 if (link != null) {
 System.out.print(link.data + " ");
 display(link.next);
 }
 }
 public boolean empty() {
 return start == null;
 }
}
public class LinkedListTest {
 public static void main(String[] args) {
 LinkedList<Integer> linkedList = new LinkedList<Integer>();
 boolean yes = true;
 Scanner scanner = new Scanner(System.in);
 do {
 System.out.println("\n1. Insert At Start");
 System.out.println("2. Insert At End");
 System.out.println("3. Insert at Position");
 System.out.println("4. Delete");
 System.out.println("5. Display");
 System.out.println("6. Empty status");
 System.out.println("7. Get Size");
 System.out.println("8. Get Index of the Item");
 System.out.println("9. Replace data at given position");
 System.out.println("10. Replace data at given position recusively");
 System.out.println("11. Get Middle Element");
 System.out.println("12. Get Occurence");
 System.out.println("13. Reverse Recusively");
 System.out.println("14. Reverse");
 System.out.println("15. Swap the nodes");
 System.out.println("16. Nth Node from last");
 System.out.println("\nEnter your choice");
 int choice = scanner.nextInt();
 switch (choice) {
 case 1:
 try {
 System.out.println("Enter the item");
 linkedList.insertAtStart(scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 2:
 try {
 System.out.println("Enter the item");
 linkedList.insertAtEnd(scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 3:
 try {
 System.out.println("Enter the position");
 int position = scanner.nextInt();
 if (position < 1 || position > linkedList.size()) {
 System.out.println("Invalid Position");
 break;
 }
 System.out.println("Enter the Item");
 linkedList.insertAtPosition(position, scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 4:
 try {
 System.out.println("Enter the position");
 int position = scanner.nextInt();
 if (position < 1 || position > linkedList.size()) {
 System.out.println("Invalid Position");
 break;
 }
 linkedList.delete(position);
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 5:
 try {
 linkedList.display();
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 6:
 System.out.println(linkedList.empty());
 break;
 case 7:
 try {
 System.out.println(linkedList.size());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 8:
 try {
 System.out.println(linkedList.index(scanner.nextInt()));
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 9:
 try {
 System.out.println("Enter the position");
 int position = scanner.nextInt();
 if (position < 1 || position > linkedList.size()) {
 System.out.println("Invalid Position");
 break;
 }
 linkedList.replace(position, scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 10:
 try {
 System.out.println("Enter the position");
 int position = scanner.nextInt();
 if (position < 1 || position > linkedList.size()) {
 System.out.println("Invalid Position");
 break;
 }
 System.out.println("Enter the item");
 linkedList.replaceRecursively(position, scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 11:
 try {
 System.out.println(linkedList.middle());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 12:
 try {
 System.out.println("Enter the item");
 System.out.println(linkedList.occurence(scanner.nextInt()));
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 13:
 try {
 linkedList.reverseRecusively();
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 14:
 try {
 linkedList.reverse();
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 15:
 try {
 System.out.println("Enter the nodes");
 linkedList.swapNode(scanner.nextInt(), scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 case 16:
 try {
 System.out.println("Enter which node do you want from last");
 linkedList.printNthNodeFromLast(scanner.nextInt());
 } catch (Exception e) {
 System.out.println(e.getMessage());
 }
 break;
 default:
 System.out.println("Invalid Choice");
 break;
 }
 } while (yes);
 scanner.close();
 }
}

Answer 4

Consider another possible implementation of a working non-recursive Linked List with generic T placeholder. It works out of the box and the code is a more simple one:

import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedList<T> implements Iterable<T> {
 private Node first;
 private Node last;
 private int N;
 public LinkedList() {
 first = null;
 last = null;
 N = 0;
 }
 public void add(T item) {
 if (item == null) { throw new NullPointerException("Null object!"); }
 if (!isEmpty()) {
 Node prev = last;
 last = new Node(item, null);
 prev.next = last;
 }
 else {
 last = new Node(item, null);
 first = last;
 }
 N++;
 }
 public boolean remove(T item) {
 if (isEmpty()) { throw new IllegalStateException("Empty list!"); }
 boolean result = false;
 Node prev = first;
 Node curr = first;
 while (curr.next != null || curr == last) {
 if (curr.data.equals(item)) {
 // remove the last remaining element
 if (N == 1) { first = null; last = null; }
 // remove first element
 else if (curr.equals(first)) { first = first.next; }
 // remove last element
 else if (curr.equals(last)) { last = prev; last.next = null; }
 // remove element
 else { prev.next = curr.next; }
 N--;
 result = true;
 break;
 }
 prev = curr;
 curr = prev.next;
 }
 return result;
 }
 public int size() {
 return N;
 }
 public boolean isEmpty() {
 return N == 0;
 }
 private class Node {
 private T data;
 private Node next;
 public Node(T data, Node next) {
 this.data = data;
 this.next = next;
 }
 }
 public Iterator<T> iterator() { return new LinkedListIterator(); }
 private class LinkedListIterator implements Iterator<T> {
 private Node current = first;
 public T next() {
 if (!hasNext()) { throw new NoSuchElementException(); }
 T item = current.data;
 current = current.next;
 return item;
 }
 public boolean hasNext() { return current != null; }
 public void remove() { throw new UnsupportedOperationException(); }
 }
 @Override public String toString() {
 StringBuilder s = new StringBuilder();
 for (T item : this)
 s.append(item + " ");
 return s.toString();
 }
 public static void main(String[] args) {
 LinkedList<String> list = new LinkedList<>();
 while(!StdIn.isEmpty()) {
 String input = StdIn.readString();
 if (input.equals("print")) { StdOut.println(list.toString()); continue; }
 if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
 if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
 break;
 }
 }
}

For more LinkedList examples, your can check out the article.