链表实现java
我已经将链接列表实现为Java。 我创建了所有内容，但是我很难删除具有特定数据的特定节点。 它抛出一个NullPointerException 。 我相信，我得到一个NullPointerException因为下一个节点是null。 如果有人能指出我正确的方向，这将是伟大的。
输入
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; } }
首先，你的头只是一个先行标记，所以你不应该从它开始删除检查。
其次，如果节点数据为null ，则remove方法将失败
第三 – 你的实现因为last.getNext().setNext(current)而被破坏了last.getNext().setNext(current) – 它不会将前一个节点与next连接起来，它会将当前链接到next（即什么也不做）
第四 – 它仍然无法删除第一个元素，因为last的神秘操作…
remove正确实现将是这样的：
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; }
在这里我们可以看到LinkedList与iterator的简单实现
class LinkedList实现Iterable {
私有节点节点;
public void add（Object data）{
如果（！Optional.ofNullable（节点）.isPresent（））{
node = new Node（）;
node.setData（数据）;
}其他{
Node node = new Node（）;
node.setData（数据）;
Node lastNode = getLastNode（this.node）;
lastNode.setNext（节点）;
}
}
private Node getLastNode（Node node）{
如果（node.getNext（）== NULL）{
返回节点;
}其他{
return getLastNode（node.getNext（））;
}
}
class Node {
私人对象数据;
私有节点下一个;
public Object getData（）{
返回数据;
}
public void setData（Object data）{
this.data = data;
}
public Node getNext（）{
返回;
}
public void setNext（Node next）{
this.next = next;
}
}
public Iterator iterator（）{
返回新的NodeIterator（）;
}
class NodeIterator实现Iterator {
私有节点电流;
public boolean hasNext（）{
if（current == null）{
current = node;
return Optional.ofNullable（current）.isPresent（）;
}其他{
current = current.next;
return Optional.ofNullable（current）.isPresent（）;
}
}
public Node next（）{
返回电流;
}
}
}
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（））;
}
}
}
这是链表的完整实现
包括插入，删除，搜索，反转，交换，大小，显示和链表的各种重要操作
import java.util.NoSuchElementException; import java.util.Scanner; class Node { public Node next; public T data; public Node() { } public Node(T data, Node next) { this.data = data; this.next = next; } @Override public String toString() { return "Node [next=" + next + ", data=" + data + "]"; } } class LinkedList { Node start = null; Node end = null; public void insertAtStart(T data) { Node nptr = new Node (data, null); if (empty()) { start = nptr; end = start; } else { nptr.next = start; start = nptr; } display(); } public void insertAtEnd(T data) { Node nptr = new Node (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 nptr = new Node (data, null); if (position == size()) { Node startPtr = start; Node endPtr = startPtr; while (startPtr.next != null) { endPtr = startPtr; startPtr = startPtr.next; } endPtr.next = nptr; nptr.next = end; } else { position -= 1; Node startPtr = start; for (int i = 1; i < size(); i++) { if (i == position) { Node 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 startPtr = start; Node endPtr = start; while (startPtr.next != null) { endPtr = startPtr; startPtr = startPtr.next; } endPtr.next = null; end = endPtr; } else { position -= 1; Node startPtr = start; for (int i = 1; i <= position; i++) { if (i == position) { Node 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 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 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 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 slowPtr = start; Node 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 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 reverseRecusively(Node link) { if (link == null || link.next == null) return link; Node nextLink = link.next; link.next = null; Node revrseList = reverseRecusively(nextLink); nextLink.next = link; return revrseList; } public void reverse() { if (empty()) throw new NoSuchElementException("Empty"); Node prevLink = null; Node currentLink = start; Node nextLink = null; while (currentLink != null) { nextLink = currentLink.next; currentLink.next = prevLink; prevLink = currentLink; currentLink = nextLink; } swapLink(); display(); } private void swapLink() { Node 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 dataOnePtr = start; Node dataOnePrevPtr = start; while (dataOnePtr.next != null && dataOnePtr.data != dataOne) { dataOnePrevPtr = dataOnePtr; dataOnePtr = dataOnePtr.next; } Node dataTwoPtr = start; Node 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 tempDataOnePtr = dataOnePtr.next; Node 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 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 main_ptr = start; Node 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 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 linkedList = new LinkedList (); 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(); } }