Удаление в некоторой позиции в двойном списке

У меня возникают некоторые проблемы с этой функцией, которую я написал для удаления в каком-то шаблоне < class T > void DoubleLinkedLists < T > :: deletePosition ( int pos ) { Node * prev = new Node ; Узел * current = head ; for ( int i = 1 ; i < pos ; i ++) { prev = current ; current = current -> next ; } prev -> next = current -> next ; } ition в двойном связанном списке. Я чувствую, что у меня утечка памяти, и я не делаю этого свойства для двойного связанного списка.

Вот код:

    template <class T>
    void DoubleLinkedLists<T>::deletePosition(int pos) {
        Node* temp = nullptr;
        Node* current = head;

        for(int i = 1; i < pos; i++) {
            temp = current;
            current = current->next;
        }
        temp->previous = current->previous;
        temp->next = current->next;
    }

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

РЕДАКТИРОВАТЬ:

Я думаю, что сейчас это работает правильно:

#ifndef DoubleLinkedLists_h
#define DoubleLinkedLists_h

template <class T>
class DoubleLinkedLists {
private:

    struct Node {
        T data;
        Node* next;
        Node* previous;
    };

    Node* head;
    Node* tail;

public:
    // Constructors
    DoubleLinkedLists() : head(nullptr), tail(nullptr) {}                  // empty constructor
    DoubleLinkedLists(DoubleLinkedLists const& value);                     // copy constructor
    DoubleLinkedLists<T>(DoubleLinkedLists<T>&& move) noexcept;            // move constuctor
    DoubleLinkedLists<T>& operator=(DoubleLinkedLists&& move) noexcept;    // move assignment operator
    ~DoubleLinkedLists();                                                  // destructor

    // Overload operators
    DoubleLinkedLists& operator=(DoubleLinkedLists const& rhs);
    friend std::ostream& operator<<(std::ostream& str, DoubleLinkedLists<T> const& data) {
        data.display(str);
        return str;
    }

    // Member functions
    void swap(DoubleLinkedLists& other) noexcept;
    void push(const T& theData);
    void push(T&& theData);
    void display(std::ostream& str) const;
    void insertHead(const T& theData);
    void insertTail(const T& theData);
    void insertPosition(int pos, const T& theData);
    void deleteHead();
    void deleteTail();
    void deletePosition(int pos);
    bool search(const T& x);
};

template <class T>
DoubleLinkedLists<T>::DoubleLinkedLists(DoubleLinkedLists const& value) : head(nullptr), tail(nullptr) {
    for(Node* loop = value->head; loop != nullptr; loop = loop->next) {
        push(loop->data);
    }
}

template <class T>
DoubleLinkedLists<T>::DoubleLinkedLists(DoubleLinkedLists<T>&& move) noexcept : head(nullptr), tail(nullptr) {
    move.swap(*this);
}

template <class T>
DoubleLinkedLists<T>& DoubleLinkedLists<T>::operator=(DoubleLinkedLists<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
DoubleLinkedLists<T>::~DoubleLinkedLists() {
    while(head != nullptr) {
        deleteHead();
    }
}

template <class T>
void DoubleLinkedLists<T>::swap(DoubleLinkedLists<T> &other) noexcept {
    using std::swap;
    swap(head,other.head);
    swap(tail,other.tail);
}

template <class T>
void DoubleLinkedLists<T>::push(const T& theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->previous = tail;

    if(head == nullptr) {
        head = newNode;
    }
    else {
        tail->next = newNode;
    }
    tail = newNode;
}

template <class T>
void DoubleLinkedLists<T>::push(T&& theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->previous = tail;

    if(head == nullptr) {
        head = newNode;
    }
    else {
        tail->next = newNode;
    }
    tail = newNode;
}

template <class T>
void DoubleLinkedLists<T>::display(std::ostream &str) const {
    for(Node* loop = head; loop != nullptr; loop = loop->next) {
        str << loop->data << "    ";
    }
    str << "
";
}

template <class T>
void DoubleLinkedLists<T>::insertHead(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = head;
    head->previous = newNode;
    head = newNode;
}

template <class T>
void DoubleLinkedLists<T>::insertTail(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->previous = tail;
    tail->next = newNode;
    tail = newNode;
}

template <class T>
void DoubleLinkedLists<T>::insertPosition(int pos, const T &theData) {
    if (pos < 0) {
        throw std::invalid_argument("pos is not a valid index");
    }

    Node* current = head;
    Node* previous = nullptr;

    while(pos-- > 0) {
        if(!current) {
            throw std::invalid_argument("pos is not a valid index");
        }
        previous = current;
        current = current->next;
    }

    Node* newNode = new Node;
    newNode->data = theData;

    newNode->previous = previous;
    newNode->next = current;

    if(newNode->previous) {
        newNode->previous->next = newNode;
    }
    else {
        head = newNode;
    }

    if(newNode->next) {
        newNode->next->previous = newNode;
    }
    else {
        tail = newNode;
    }
}

template <class T>
void DoubleLinkedLists<T>::deleteHead() {
    if (head != nullptr) {
        Node* old = head;
        head = head->next;
        delete old;
    }
    else {
        throw std::invalid_argument("the list is empty!");
    }
}

template <class T>
void DoubleLinkedLists<T>::deleteTail() {
    if(head != nullptr) {
        Node* prev = nullptr;
        Node* current =  head;
        while(current->next != nullptr) {
            prev = current;
            current = current->next;
        }
        tail = prev;
        prev->next = nullptr;
        delete current;
    }
    else {
        throw std::invalid_argument("The list is already empty, nothing to delete.");
    }
}

template <class T>
void DoubleLinkedLists<T>::deletePosition(int pos) {
    Node* temp = nullptr;
    Node* current = head;

    for(int i = 1; i < pos; i++) {
        temp = current;
        current = current->next;
    }
    temp->previous = current->previous;
    temp->next = current->next;
}

template <class T>
bool DoubleLinkedLists<T>::search(const T &x) {
    Node* current = head;
    while(current != nullptr) {
        if(current->data == x) {
            return true;
        }
        current = current->next;
    }
    return false;
}
#endif /* DoubleLinkedLists_h */

Вот весь код:

#include <iostream>
#include "DoubleLinkedLists.h"



int main(int argc, const char * argv[]) {



    ///////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////// Double Linked List //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////
    DoubleLinkedLists<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"
--------------------------------------------------
";
    std::cout<<"---------------Displaying All nodes---------------";
    std::cout<<"
--------------------------------------------------
";
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"----------------Inserting At Start----------------";
    std::cout<<"
--------------------------------------------------
";
    obj.insertHead(50);
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"-----------------Inserting At End-----------------";
    std::cout<<"
--------------------------------------------------
";
    obj.insertTail(20);
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"-------------Inserting At Particular--------------";
    std::cout<<"
--------------------------------------------------
";
    obj.insertPosition(5,60);
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"----------------Deleting At Start-----------------";
    std::cout<<"
--------------------------------------------------
";
    obj.deleteHead();
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"----------------Deleting At End-----------------";
    std::cout<<"
--------------------------------------------------
";
    obj.deleteTail();
    std::cout << obj << std::endl;

    std::cout<<"
--------------------------------------------------
";
    std::cout<<"--------------Deleting At Particular--------------";
    std::cout<<"
--------------------------------------------------
";
    obj.deletePosition(5);
    std::cout << obj << std::endl;
    std::cout << std::endl;

    obj.search(8) ? printf("Yes"):printf("No");

    return 0;
}

И вот файл main.cpp, который его тестирует:

current != nullptr

c++,linked-list,

0

Ответов: 1

2 принят

Поэтому вам нужно будет сделать что-то подобное. Обратите внимание, что ваш код не обрабатывает случай индекса вне диапазона (т. Е. Указанная позиция либо отрицательна, либо длиннее списка). Похоже, что вы не поддерживаете подсчет длины списка (в связанном коде), поэтому я добавил проверку posв цикл for, а также после цикла for, чтобы обработать случай, когда длина posбыла длиннее, чем список. В этом случае теперь код ничего не сделает, но вы можете выбросить исключение из диапазона или что-то подобное, чтобы указать недопустимое условие. В случае удаления головы вам также необходимо позаботиться о фиксации указателя головы. Я предполагаю, что у вас может быть указатель на хвост, поэтому вам нужно добавить проверки, чтобы увидеть, удаляете ли вы хвост и исправляете это.

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

void DoubleLinkedLists<T>::deletePosition(int pos) {
    if (pos < 0) {} // Should do something in this case
    Node* current = head;

    // Added null check to keep from continuing past the end of the list
    for(int i = 1; i < pos && current != nullptr; i++) {
        current = current->next;
    }

    if (current != nullptr)
    {
        // If we are at the head, there isn't a previous
        if (current != head)
        {
            current->previous->next = current->next;
        }
        else
        {
            // In this case, we are removing the head, need to reset head to the next Node
            head = current->next;
        }

        if (current->next != nullptr)
        {
            current->next->previous = current->previous;
        }
        else if (current == tail)
        {
            // In this case we are removing the tail, need to reset tail pointer
            tail = current->previous;
        }

        delete current; // Cleans up the node we are deleting
    }
}
C ++, связанный список,
Похожие вопросы
Яндекс.Метрика