从 C++ 中的链表中删除元素

Remove an element from a linked list in C++

提问by Alex

I'm trying to learn C++ right now because of a class I'm going to have to take, and am coming from Java. I'm currently going through the book "Jumping into C++" and completing the exercises. After reading the section on linked lists, it tells me to create my own linked list and have a method that will remove an element (using pointers in the exercise).

我现在正在尝试学习 C++，因为我将要上一门课，而且我来自 Java。我目前正在阅读“Jumping into C++”一书并完成练习。在阅读了有关链表的部分后，它告诉我创建自己的链表并拥有一个删除元素的方法（在练习中使用指针）。

So far I've been able to add values to my linked list, and display my linked linked list. After doing my remove element method, and having my program explicitly tell me it has deleted the value at a specific memory address, I display the list again to find that my value still somehow appears at the memory address that has supposedly been deleted.

到目前为止，我已经能够向我的链表添加值，并显示我的链表。在执行我的删除元素方法后，并让我的程序明确告诉我它已删除特定内存地址处的值，我再次显示列表以发现我的值仍然以某种方式出现在据称已被删除的内存地址处。

This is my removeElement method:

这是我的 removeElement 方法：

// remove an element from the linked list
void removeElement(int remValue) {
    // to remove an element, we go through the list, find the value given
    // if we find it, stop
    // to remove, disconnect the link
    // relink the two values now (ie. value 1->2->3->NULL, 2 is removed, 1->3->NULL )
    LinkedList* current = head;
    LinkedList* next = current;
    while(current != NULL) {
        if(current->value == remValue) { // if match
            break; // break out of while
        }
        else {
            cout << "Value " << current->value << " does not match " << remValue << ".\n";
            next = current; // save in case
            current = current->pNextValue; // go to next value
        }
    } // end while
    if(current == NULL) { // if we reached end of list
        cout << "Can't remove value: no match found.\n"; // no match, cant remove
    } else { // found match
        cout << "Deleting: " << current << "\n";
        delete current;
        current = next->pNextValue; // current is updated
    }
}

Here is my entire code for the linked list(including some tests to see where stuff is going):

这是我的链接列表的完整代码（包括一些测试以查看内容的去向）：

http://pastebin.com/cHZr4cBa

http://pastebin.com/cHZr4cBa

I realize that most of my code is not efficient and not normal for a realistic linked list, I'm just trying to figure out pointers and how to use them in a linked list at the most basic level.

我意识到我的大部分代码对于现实的链表来说效率不高，也不正常，我只是想找出指针以及如何在最基本的级别在链表中使用它们。

回答by Some programmer dude

You don't actually unlinkthe node you remove.

您实际上并没有取消链接您删除的节点。

You need to keep track of the previousnode, and make its nextpointer point to the current nodes nextnode. Also think of the special case when the node to remove is the first node.

您需要跟踪前一个节点，并使其next指针指向当前节点next节点。还要考虑要删除的节点是第一个节点时的特殊情况。

回答by Anthony Cooper

@Joachim Pileborg is right, you need to record previous node, not next.

@Joachim Pileborg 是对的，您需要记录上一个节点，而不是next.

try this code:

试试这个代码：

// remove an element from the linked list
void removeElement(int remValue) {
    LinkedList* prev = head; // empty header
    LinkedList* current = head->pNextValue; // the first valid node
    while(current != NULL) {
        if(current->value == remValue) { 
            break; 
        }
        else {
            cout << "Value " << current->value << " does not match " << remValue << ".\n";
            prev = current; 
            current = current->pNextValue; // go to next value
        }
    }
    if(current == NULL) { // if we reached end of list or the list is empty
        cout << "Can't remove value: no match found.\n"; 
    } else {
        cout << "Deleting: " << current << "\n";
        prev->pNextValue = current->pNextValue; // unlink the node you remove
        delete current; // delete the node
    }
}

回答by Code-Apprentice

You need to update the links in your list to remove the node that you deleted.

您需要更新列表中的链接以移除您删除的节点。

Note that using the deleteoperator does not change any values in memory. It simply tells the operating system that you are no longer using that location in memory and it can reclaim it for other uses.

请注意，使用delete运算符不会更改内存中的任何值。它只是告诉操作系统您不再使用内存中的该位置，它可以将其回收用于其他用途。

回答by joepa37

#include <iostream>
#include <cstdlib>

using namespace std;

class Node
{
public:
    Node* next;
    int data;
    Node();
    ~Node();
    void print();
};

class LinkedList
{
public:
    int length;
    Node* head;

    LinkedList();
    ~LinkedList();
    void add(int data);
    void remove(int data);
    Node* search(int data);
    void print();
    void size();
};

Node::Node(){
    //set default values;
}

Node::~Node(){
    cout << "NODE DELETED" <<endl;
}

void Node::print(){
    Node* node = this;
    if(node != NULL){
        cout << "===============================" << endl;
        cout << this->data << endl;
        cout << "===============================" << endl;
    }
}

LinkedList::LinkedList(){
    this->length = 0;
    this->head = NULL;
}

LinkedList::~LinkedList(){
    cout << "LIST DELETED" <<endl;
}

void LinkedList::add(int data){
    Node* node = new Node();
    node->data = data;
    node->next = this->head;
    this->head = node;
    this->length++;
}

void LinkedList::remove(int data){
    if(this->length == 0){
        cout << "The list is empty" << endl;
    }else if(this->head->data == data){
        Node* current = head;
        this->head = this->head->next;
        delete current;
        this->length--;
    }else{
        Node* previous = this->head;
        Node* current = head->next;
        while(current != NULL) {
            if(current->data == data) {
                break;
            }
            else {
                previous = current;
                current = current->next;
            }
        }
        if(current == NULL) {
            cout << "Can't remove value: no match found.\n";
        } else {
            previous->next = current->next;
            delete current;
            this->length--;
        }
    }
}

Node* LinkedList::search(int data) {
    Node* head = this->head;
    while(head){
        if(head->data == data){
            return head;
        }else{
            head = head->next;
        }
    }
    cout << "No match found.\n";
    return NULL;
}

void LinkedList::print(){
    if(this->length == 0){
        cout << "The list is empty" << endl;
    }else{
        Node* head = this->head;
        int i = 1;
        cout << "===============================" << endl;
        while(head){
            cout << i << ": " << head->data << endl;
            head = head->next;
            i++;
        }
        cout << "===============================" << endl;
    }
}

void LinkedList::size(){
    cout << "List Length: " << this->length << endl;
}


int main(int argc, char const *argv[])
{
    LinkedList* list = new LinkedList();

    for (int i = 0; i < 5; ++i)
    {
        if(i == 3){
            list->add(105);
            list->add(106);
        }
        list->add(rand() % 100);
    }

    list->print();
    list->size();

    list->remove(105);

    list->print();
    list->size();

    Node* node = list->search(106);
    node->print();

    delete list;
    return 0;
}