给定链表中的特定节点时如何使用 insertAfter()

Question

// insert a new data after the given onepublic 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 datapublic 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 givenData以及如果它不是节点如何访问它。第一次在这里发帖，希望我提供了足够的信息:)public class LinkedListTemplate {Node head;// inserts data to the end of the list only using the head pointerpublic 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 listpublic 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 elementspublic 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);}我包含了其余的链表代码，还有另一个类可以测试列表并允许它运行。

Answer 1

将插入方法更改为：

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 2

好的，您可能需要稍微增强您的代码。首先，你需要一个清单。所以让我们从那个开始。

public class MyLinkedList {

    public Node *head = NULL;

}

head 指向列表的前面。

现在， insertAfter 的基本算法很简单：

查找包含“插入位置”值的节点

创建一个新节点并在之后插入。

可爱吧？

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);

如果您随后转储列表的内容（您需要从 head 遍历 next 指针），您将看到列表按 1、10、17 的顺序包含。

Answer 3

我试了一下。

请注意，我实际上并不知道 remove 真正应该做什么。

您的代码正在寻找具有给定索引的节点，因此我坚持使用该节点（第一个删除版本）。

但评论建议，您需要删除具有给定数据的节点。所以我添加了第二个版本，就是这样做的（第二个删除版本）。

    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;

        }

    }