我在Java中实现了一个链表。我已经创建了一切，但我很难删除具有特定数据的特定节点。它抛出了一个NullPointerException。我相信，我得到了NullPointerException因为下一个节点是空的。如果有人能给我指个方向就太好了。
anything
one
two
three
Exception in thread "main" java.lang.NullPointerException
at LinkedList.remove(LinkedList.java:28)
at Main.main(Main.java:29)
类:链表类
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());
}
}
}
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());
}
}
节点
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;
}
}
首先，你的头部只是一个before-first标记，所以你不应该从它开始删除检查。
第二，如果节点数据为null，则remove方法失败
第三-你的实现是坏的，因为last.getNext().setNext(current) -它不会链接前一个节点与下一个，它将链接当前到下一个(即什么也不做)
第四个-由于last的神秘操作，它仍然无法删除第一个元素…
remove的正确实现应该是这样的:
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;
}
这里我们可以看到带有迭代器的LinkedList的简单实现
<>之前类LinkedList实现Iterable{private Node节点;public void add(Object data)如果(! Optional.ofNullable(节点).isPresent ()) {node = new node ();node.setData(数据);其他}{Node = new Node();node.setData(数据);节点lastNode = getLastNode(this.node);lastNode.setNext(节点);｝｝私有节点getLastNode(节点节点){如果(node.getNext () = = null) {返回节点;其他}{返回getLastNode (node.getNext ());｝｝{类节点私有对象数据;私有节点next;getData() {返回数据;｝公共无效setData(对象数据){这一点。Data =数据;｝公共节点getNext() {返回下一个;｝public void setNext(节点下一个){这一点。Next =下一个;｝｝公共迭代器迭代器(){返回新的NodeIterator();｝类NodeIterator实现迭代器{private节点电流;public boolean hasNext() {If (current == null){Current = node;返回Optional.ofNullable(当前).isPresent ();其他}{Current = Current .next;返回Optional.ofNullable(当前).isPresent ();｝｝public Node next() {返回当前;｝｝｝公共类LinkedListImpl {public static void main(String[] args) {LinkedList = new LinkedList();linkedList.add("data1");linkedList.add("data2");linkedList.add("data3");(LinkedList。节点节点:linkedList){System.out.println (node.getData ());｝｝｝这里是链表的完整实现
包括链表的插入、删除、查找、反转、交换、大小、显示等各种重要操作
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();
}
}
考虑另一种具有通用T占位符的工作非递归链表的可能实现。它开箱即用，代码更简单:
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;
}
}
}
更多LinkedList的例子，你可以查看文章