0
Я работаю над LinkedList, и я хотел бы напечатать все значения со своими предыдущими значениями списка. Я получаю NullPointerException. Как я могу исправить программу?Структура данных LinkedList в Java
У меня есть несколько дополнительных методов, но я могу удалить их, если они чувствуют себя неактуальными в контексте программы. Метод, который печатает вперед в списке Linked, называется display и тот, который печатает значения со своими предыдущими значениями, называемыми displayInDetails.
спасибо.
import java.util.* ;
class Node {
public int data;
public Node next;
public Node previous;
public Node(int data){
this.data = data;
}
public Node(){
}
public void display(int data){
System.out.print(Integer.toString(data));
}
}
class Result {
public Node node;
public int count;
public Result(Node n, int c) {
node = n;
count = c;
}
}
class IntWrapper {
public int value = 0;
}
public class LinkedList {
public Node head;
public Node tail;
public Node current;
LinkedList(){
head = null;
tail = null;
current = null;
}
public boolean isEmpty(){
return(head == null);
}
public void insertToTail(int data){
Node newNode = new Node(data);
Node tmp = tail;
//
if (head == null){
head = newNode;
tail = head;
}
else {
tail.next = newNode;
tail = newNode;
}
tail.previous = tmp;
head.previous = null;
}
public Node removeFirst(){
Node linkReference = head;
if(!isEmpty()){
// Removes the Link from the List
head = head.next;
} else {
System.out.println("Empty LinkedList");
}
return linkReference;
}
public void display(){
Node current = head;
List<Node> myNodeList = new ArrayList<Node>();
System.out.println();
while(current != null){
System.out.print(current.data);
if (myNodeList.contains(current))
break;
myNodeList.add(current);
if (current.next != null)
System.out.print(" -> ");
current = current.next;
}
System.out.println();
}
public void displayInDetails(){
Node current = head;
List<Node> myNodeList = new ArrayList<Node>();
System.out.println();
while(current != null){
if (current.previous != null || current != null)
System.out.println(current.previous.data + " <-"+ current.data) ;
if (myNodeList.contains(current))
break;
myNodeList.add(current);
current = current.next;
}
System.out.println();
}
public int getLength (){
int length = 0;
// LinkedList ll = this;
if (this== null)
return -1;
Node current = this.head;
while(current != null){
length += 1;
current = current.next;
}
return length;
}
public Node getNode(int data){
Node theLink = head;
if(!isEmpty()){
while(theLink.data != data){
// Checks if at the end of the LinkedList
if(theLink.next == null){
// Got to the end of the Links in LinkedList
// without finding a match
return null;
} else {
// Found a matching Link in the LinkedList
theLink = theLink.next;
}
}
} else {
System.out.println("Empty LinkedList");
}
return theLink;
}
public Node removeLink(int data){
Node currentLink = head;
Node previousLink = head;
// Keep searching as long as a match isn't made
while(currentLink.data != data){
// Check if at the last Link in the LinkedList
if(currentLink.next == null){
// bookName not found so leave the method
return null;
} else {
// We checked here so let's look in the
// next Link on the list
previousLink = currentLink;
currentLink = currentLink.next;
}
}
if(currentLink == head){
// If you are here that means there was a match
// in the reference stored in head in the
// LinkedList so just assign next to head
head = head.next;
}
else {
// If you are here there was a match in a Link other
// than the head. Assign the value of next for
// the Link you want to delete to the Link that's
// next previously pointed to the reference to remove
System.out.println("FOUND A MATCH");
System.out.println("currentLink: " + currentLink);
System.out.println("head: " + head);
previousLink.next = currentLink.next;
}
return currentLink;
}
/* question 2-1 */
/* remove the duplicates from an unsorted linked list */
public static void deleteDupsB(Node head) {
if (head == null) return;
Node current = head;
while (current != null) {
/* Remove all future nodes that have the same value */
Node runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
current = current.next;
}
}
public static void deleteDupsA(Node n) {
HashSet<Integer> set = new HashSet<Integer>();
Node previous = null;
while (n != null) {
if (set.contains(n.data)) {
previous.next = n.next;
} else {
set.add(n.data);
previous = n;
}
n = n.next;
}
}
public static void deleteDupsC(Node head) {
if (head == null) return;
Node previous = head;
Node current = previous.next;
while (current != null) {
// Look backwards for dups, and remove any that you see.
Node runner = head;
while (runner != current) {
if (runner.data == current.data) {
Node tmp = current.next;
previous.next = tmp;
current = tmp;
/*
We know we can't have more than one dup preceding
our element since it would have been removed
earlier.
*/
break;
}
runner = runner.next;
}
/* If runner == current, then we didn't find any duplicate
* elements in the previous for loop. We then need to
* increment current.
* If runner != current, then we must have hit the ‘break’
* condition, in which case we found a dup and current has
* already been incremented.*/
if (runner == current) {
previous = current;
current = current.next;
}
}
}
/* end of question 2-1 */
/* question 4-2 */
/* get the n-th number from last in a linked list */
public static Node nthToLast(Node head, int n) {
Node p1 = head;
Node p2 = head;
if (n <= 0) return null;
// Move p2 n nodes into the list. Keep n1 in the same position.
for (int i = 0; i < n - 1; i++) {
if (p2 == null) {
return null; // Error: list is too small.
}
p2 = p2.next;
}
if (p2 == null) { // Another error check.
return null;
}
// Move them at the same pace. When p2 hits the end,
// p1 will be at the right element.
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
public static Result nthToLastR3Helper(Node head, int k) {
if (head == null) {
return new Result(null, 0);
}
Result res = nthToLastR3Helper(head.next, k);
if (res.node == null) {
res.count++;
if (res.count == k) {
res.node = head;
}
}
return res;
}
public static Node nthToLastR3(Node head, int k) {
Result res = nthToLastR3Helper(head, k);
if (res != null) {
return res.node;
}
return null;
}
public static int nthToLastR1(Node head, int n) {
if (n == 0 || head == null) {
return 0;
}
int k = nthToLastR1(head.next, n) + 1;
if (k == n) {
System.out.println(n + "th to last node is " + head.data);
}
return k;
}
/* question 4-2 end */
/* question 2-3 */
/* write an algorithm to delete a node to middle of a singly linked list given only access to that node */
public static boolean deleteNode(Node n) {
if (n == null || n.next == null) {
return false; // Failure
}
Node next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}
/* question 2-4 */
/* add values in two linked list */
public int addListsHelper(Node first, Node second ){
int addvalue = 0 ;
if(first != null){
addvalue += first.data;
}
if (second!= null){
addvalue += second.data;
}
return addvalue;
}
private void addLists(LinkedList l1, LinkedList l2) {
if (l1 == null && l2 == null) {
return;
}
int carry = 0 ;
Node curr1 = l1.head;
Node curr2 = l2.head;
// Node res1 = result.head;
int [] f_result = null;
while (curr1 != null ||curr2 != null) {
int ll = addListsHelper(curr1 , curr2);
System.out.println("carry = "+ carry);
int tt = (ll+carry) % 10;
// carry =0;
if (ll >= 10)
carry =1;
curr1 = curr1.next;
curr2 = curr2.next;
System.out.println(" "+ tt);
}
}
/* end of addLists */
public static Node findBeginning(Node head) {
Node slow = head;
Node fast = head;
// Find meeting point
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
// Error check - there is no meeting point, and therefore no loop
if (fast == null || fast.next == null) {
return null;
}
/* Move slow to Head. Keep fast at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// Both now point to the start of the loop.
return fast;
}
public void createLoop(int disToTail){
if (this.getLength() < disToTail)
return;
else {
Node curr = nthToLast(head, disToTail);
tail.next = curr;
}
}
public static void main(String[] args) {
LinkedList myLL = new LinkedList();
int length = 10;
// insert values (int) to the tail of the linked list
for (int j=0; j < length; j++){
myLL.insertToTail(j*2);
}
myLL.display();
System.out.println();
/* display the linked list with it's previous, current and the next values */
myLL.displayInDetails();
System.out.println();
// int list_length = 100;
// int k = 10;
// LinkedListNode[] nodes = new LinkedListNode[list_length];
// for (int i = 0; i < list_length; i++) {
// nodes[i] = new LinkedListNode(i, null, i > 0 ? nodes[i - 1] : null);
// }
/*int nToLast = 4;
System.out.println(myLL.nthToLastR3(myLL.head, nToLast).data);
int test = myLL.nthToLastR1(myLL.head, nToLast);*/
/* question 2-1 */
/* remove the duplicates from an unsorted linked list */
/*myLL.deleteDupsC(myLL.head);
myLL.display();
System.out.println();*/
/* find the node with it's int value */
/*
int getNode = 12;
System.out.println(myLL.getNode(getNode).data);
*/
/* question 2-3 */
/* write an algorithm to delete a node to middle of a singly linked list given only access to that node */
/*int deleteNode = 12;
myLL.deleteNode(myLL.getNode(deleteNode));
myLL.display();
System.out.println();*/
/* question 2-4 */
/*
System.out.println("the length of the linked list = "+ myLL2.getLength());
myLL.addLists(myLL1, myLL2);
*/
/* question 2-5 */
/* find the head of the circular linked list */
/*myLL.createLoop(15);
myLL.display();
System.out.println();
if (myLL.findBeginning(myLL.head) == null){
System.out.println("No cycle");
}
else
System.out.println("head of the loop is = "+ myLL.findBeginning(myLL.head).data);*/
}
}
опубликовать LogCat так, что я могу выяснить, на котором происходит ошибка линии. – RajSharma
Мне интересно, почему вы реализуете свой собственный связанный список ... (я могу подумать о одной возможной причине для этого - если вам нужен список, итераторы которого не являются аннулированными при изменении списка, но почему-то я сомневаюсь вот здесь.) – celticminstrel
@celticminstrel, единственная веская причина для этого - лучше узнать, как работают основные структуры ... Я бы предположил, что это школьное задание, так как оно очень похоже на меня. Однако для приложений, основанных на приложениях, на любом предприятии, я согласен, вы должны использовать коллекции java или расширять их с помощью шаблона проектирования, если у вас есть что-то, что требует дополнительного поведения. – anonymous