5

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; } }
Improve this question
1
  • 1
    Question: why does an empty list imply size -1? Isn't the initial list (size 0) also empty? Commented Dec 19, 2011 at 5:19

4 Answers 4

Reset to default
5

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; }
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Yes, it's Java 7 shortcut. I've edited the answer, now it should work for you.
0

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

Comments

0

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

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.