Как использовать insertAfter (), когда указан определенный узел в связанном списке

Question

// insert a new data after the given one
public void insertAfter(int givenData, int newData){
   // Your code here
   Node previous = new Node(givenData);
    if (previous == null) {
        //System.out.println("The given previous node cannot be null.");
        return;
    }

    Node newNode = new Node(newData);
    newNode.next = previous.next;
    previous.next = newNode;
}

// Removes the Node with the given data
public void remove(int current) {
  // Your code here
  Node previous = new Node(current);
    int count = 1;
    int position = 0;
    while (count < position -1) {
        previous = previous.next;
        count++;
    }
    Node curNode = previous.next;
    previous.next = curNode.next;
    curNode.next = null;
}

Этот код не дает никаких сообщений об ошибках, но узлы не будут добавлены или удалены.Я полагаю, что моя путаница заключается в int дали данные и как получить к нему доступ, если это не узел.Первый пост здесь, надеюсь, я дал достаточно информации:)

public class LinkedListTemplate {
Node head;


// inserts data to the end of the list only using the head pointer
public void append(int data){
    Node newNode = new Node(data);
    if(head == null){           
        head = newNode;

    } else {            
        Node currentNode = head;
        while(currentNode.next != null){
            currentNode = currentNode.next;
        }
        currentNode.next = newNode;             
    }
}

// inserts data to the beginning of the list
public void prepend(int data){
    if(head == null){
        Node newNode = new Node(data);
        head = newNode;
        return;
    }
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

// print the linked list elements
public void print() {
    Node currentNode = head;
    System.out.printf("[");
    while (currentNode.next != null) {
        System.out.printf("%d, ", currentNode.data);
        currentNode = currentNode.next;
    }
    System.out.printf("%d]%n", currentNode.data);
}

// counts the length of the list
public int length(){
   int length = 0;
   Node currentNode = head;
    while(currentNode != null){
        length++;
        currentNode = currentNode.next;
    }   
    return length;
}

// get an item from the list specified by the index
public int get(int index){
   int len = length();
   if(index > len){
      return -1;
   }

 Node currentNode = head;
 int currentIndex = 0;
 while(currentNode != null){
    if(index == currentIndex){
       return currentNode.data;
    }
    else{
       currentNode = currentNode.next;
       currentIndex++;
     }
  }
  return -1;
}

Я включил остальную часть кода связанного списка, есть также другой класс, который проверяет список и позволяет ему работать.

Answer 1

Я попробовал.

Обратите внимание, что я на самом деле не знал, что должна делать действительности удаления.

Ваш код искал узел с данным индексомтак что я придерживался этого (первая версия удаления).

Но комментарий предполагает, что вам нужно удалить узел с заданными данными.Поэтому я добавил вторую версию, которая делает это (2-я версия удаления).

    public void insertAfter(int givenData, int newData) {
        // Your code here
        Node previous = head;
        while (null != previous && previous.data != givenData) {
            previous = previous.next;
        }
        // this prevents insertion if given Data was not found 
        if (previous == null) {
            System.out.println("the given data doesn't exist");
            return;
        }
        Node newNode = new Node(newData);
        newNode.next = previous.next;
        previous.next = newNode;
    }

Версия, которая удаляет узел с заданным индексом:

    // Removes the Node with the given index
    public void remove(int current) {

        Node previous = head;
        for (int i = 0; i < current - 1; i++) {
            if (null == previous) {
                System.out.println("the given position doesn't exist");
                return;
            }
            previous = previous.next;
        }
        if (current == 0) {
            head = head.next;
        } else if (previous.next == null) {
            System.out.println("the given position is after the end - nothing to do!");
        } else {
            previous.next = previous.next.next;
        }
    }

Версия, которая удаляет элемент сданные

   // Removes the Node with the given data
    public void remove(int data) {
        Node previous = head;
        if(head == null){
            System.out.println("Empty list - nothing to remove!");
            return;
        } if (head.data == data){
            head = head.next;
            return;
        }

        while(previous.next != null && previous.next.data != data){
            previous = previous.next;
        }
        if (previous.next == null) {
            System.out.println("the given element was not found - nothing to do!");
        } else {
            previous.next = previous.next.next;
        }
    }

Answer 2

изменить метод вставки на это:

public void insertAfter(int givenData, int newData) {
    Node n = head;
    while (n != null && n.data != givenData) {
        n = n.next;
    }
    if (n != null) return;
    Node newNode = new Node(newData);
    newNode.next = n.next;
    n.next = newNode;
}

и метод удаления с помощью этого:

public void remove(int current) {

    Node prev = head;
    if(head == null) return;
    if(head.data == current){head = null; return;}
    Node n = prev.next;
    while( n != null && n.data != current){
      prev = n;
      n = n.next;   
    }
    if (n == null) return;
    prev.next = n.next;

}

Answer 3

Хорошо, возможно, вам нужно немного улучшить свой код.Во-первых, вам нужен список.Итак, начнем с этого.

public class MyLinkedList {
    public Node *head = NULL;
}

заголовок указывает на начало списка.

Теперь основной алгоритм для insertAfter прост:

1. Найтиузел, содержащий значение «куда вставлять после»
2. Создайте новый узел и вставьте его после.

Мило, да?

void insertAfter(int beforeData, int valueToInsert) {
    Node *ptr = head;
    Node *lastPtr = NULL;
    while (ptr != NULL && ptr->value != beforeData) {
        lastPtr = ptr;
        ptr = ptr->next;
    }

    // At this point, ptr COULD be null, if the data is never found.
    // Insertion is at the end, and lastPtr helps with that.
    Node * newNode = new Node(valueToInsert);
    if (ptr == NULL) {
        # At the end of the list.
        if (lastPtr != NULL) {
            lastPtr->next = newNode;
            newNode->previous = lastPtr;
        }
        else {
            // The entire list is null
            head = newNode;
        }
    }
    else {
        // ptr points to the data we were searching for, so insert after.
        newNode->next = ptr->next;
        newNode->previous = ptr;
        ptr->next = newNode;
    }
}

Тогда, вы можете сделать что-то вроде этого:

MyLinkedList list;
list.insertAfter(0, 1);
list.insertAfter(1, 17);
list.insertAfter(1, 10);

Если вы затем сбросите содержимое списка (вам нужно будет выполнить итерацию от головы до следующих указателей), вы увидите, что список содержит в порядке1, 10, 17.