Jeel Shah Jeel Shah - 2 months ago 6
Java Question

linked list implementation java

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

}

Answer

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 current = head.getNext();
    Node previous = null;
    while (current != null) {
        String dataOld = current.getData();
        if ((dataOld == null && data == null) || (dataOld != null && dataOld.equals(data))) {
            Node afterRemoved = current.getNext();
            if (previous == null) {
                head.setNext(afterRemoved);
            } else {
                previous.setNext(afterRemoved);
            }
            if (afterRemoved.getNext() == null) {
                last = afterRemoved;
            }
            size--;
            return true;
        } else {
            previous = current;
            current = current.getNext();
        }
    }
    return false;
}
Comments