Вставка LinkedList После узла

Question

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

Вот код для insertNodeBefore. Я просто хочу знать, есть ли способ адаптировать это, чтобы иметь возможность вставлять после текущего узла?

// Insert new node nVal to the list before current node curVal 
public void insertNodeBefore(E nVal, E curVal) { 
    Node<E> newNode = new Node<E>(nVal); 

    Node<E> curr = head; 
    Node<E> prev = null; 

    if (head.getNodeValue() == curVal) { 
     newNode.setNext(head); 
     head = newNode; 
     return; 
    } 

    // scan until locate node or come to end of list 
    while (curr != null) { 
     // have a match 
     if (curr.getNodeValue() == curVal) { 
      // insert node 
      newNode.setNext(curr); 
      prev.setNext(newNode); 
      break; 
     } else { 
      // advanced curr and prev 
      prev = curr; 
      curr = curr.getNext(); 
     } 
    } 
} 

Answer 1

В принципе найти узел, а затем:

• установлен следующий нового узла равен току
• установить следующий тока на новый узел

что-то как это должно работать:

public void insertNodeBeAfter(E nVal, E curVal) { 
    Node<E> newNode = new Node<E>(nVal); 

    Node<E> curr = head; 

    // scan until locate node or come to end of list 
    while (curr != null) { 
     // have a match 
     // Replaced == with .equals 
     if (curr.getNodeValue().equals(curVal)) { 
      // insert node 
      newNode.setNext(curr.getNext()); 
      curr.setNext(newNode); 
      break; 
     } else { 
      curr = curr.getNext(); 
     } 
    } 
} 

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

Примечание: может быть интересно обрабатывать NOT молча, если список пуст или если curVal не найден, например, выбрасывает RuntimeException.

Answer 2

Вставка после данного узла на самом деле проще, чем вставка перед данным узлом:

// Insert new node nVal to the list after current node curVal 
public void insertNodeAfter(E nVal, E curVal) { 
    Node<E> newNode = new Node<E>(nVal); 
    Node<E> curr = head; 

    // scan until curValnode is found or the end of the list is reached 
    while (curr != null) { 
     // have a match 
     if (curr.getNodeValue().equals(curVal)) { 
      // insert node 
      newNode.setNext(curr.getNext()); 
      curr.setNext(newNode); 
      break; 
     } else { 
      // advanced curr 
      curr = curr.getNext(); 
     } 
    } 
} 

Answer 3

Я пытался отделить код обхода и код вставки, все это взято из прилагаемого кода в вашем вопросе.

private void insert(Node<E> prev, Node<E> after, Node<E> newNode) { 
    newNode.setNext(after); 
    if (prev != null) { 
     prev.setNext(newNode); 
    } else { 
     head = newNode; 
    } 
} 
public Node<E> findPrevOf(E curVal) { 
    Node<E> curr = head; 
    Node<E> prev = null; 
    // scan until locate node or come to end of list 
    while (curr != null) { 
     // have a match 
     if (curr.getNodeValue() == curVal) { 
      return prev; 
     } else { 
      // advanced curr and prev 
      prev = curr; 
      curr = curr.getNext(); 
     } 
    } 
    throw new Exception("throw an exception to indicate that value does not exist"); 
} 
public void insertNodeAfter(E nVal, E curVal) { 
    Node<E> prev = findPrevOf(curVal); 
    Node<E> curr = null; 
    if (prev == null) { 
     curr = head; 
    } else { 
     curr = prev.getNext(); 
    } 
    Node<E> newNode = new Node<E>(nVal); 
    insert(curr, (curr == null ? curr: curr.getNext()), newNode); 
} 
// Insert new node nVal to the list before current node curVal 
public void insertNodeBefore(E nVal, E curVal) { 
    Node<E> prev = findPrevOf(curVal); 
    Node<E> newNode = new Node<E>(nVal); 
    insert(prev, (prev == null ? head : prev.getNext()), newNode); 
}