Конструктор копирования для односвязного списка

Question

написал реализацию односвязного списка. Но никак не получается реализовать в нём конструктор копирования. Мучаюсь уже третий день, помогите, пожалуйста!

#include <iostream>
using namespace std;


template<typename T>
class List
{
public:
    List();
    ~List();
    List(const List& other);
    //удаление первого элемента в списке
    void pop_front();

    //добавление элемента в конец списка
    void push_back(T data);

    // очистить список
    void clear();

    // получить количество элементов в списке
    int GetSize() { return Size; }

    // перегруженный оператор [] 
    T& operator[](const int index);
    
    //добавление элемента в начало списка
    void push_front(T data);

    //добавление элемента в список по указанному индексу
    void insert(T data, int index);

    //удаление элемента в списке по указанному индексу
    void removeAt(int index);
    
    //удаление последнего элемента в списке
    void pop_back();

private:


    template<typename T>
    class Node
    {
    public:
        Node * pNext;
        T data;

        Node(T data = T(), Node *pNext = nullptr)
        {
            this->data = data;
            this->pNext = pNext;
        }
    };
    int Size;
    Node<T> *head;
};


template<typename T>
List<T>::List()
{
    Size = 0;
    head = nullptr;
}


template<typename T>
List<T>::~List()
{
    clear();
}


template<typename T>
void List<T>::pop_front()
{
    Node<T> *temp = head;

    head = head->pNext;

    delete temp;

    Size--;

}

template<typename T>
void List<T>::push_back(T data)
{
    if (head == nullptr)
    {
        head = new Node<T>(data);
    }
    else
    {
        Node<T> *current = this->head;

        while (current->pNext != nullptr)
        {
            current = current->pNext;
        }
        current->pNext = new Node<T>(data);

    }

    Size++;
}

template<typename T>
void List<T>::clear()
{
    while (Size)
    {
        pop_front();
    }
}


template<typename T>
T & List<T>::operator[](const int index)
{
    int counter = 0;

    Node<T> *current = this->head;

    while (current != nullptr)
    {
        if (counter == index)
        {
            return current->data;
        }
        current = current->pNext;
        counter++;
    }
}

template<typename T>
void List<T>::push_front(T data)
{
    head = new Node<T>(data, head);
    Size++;
}

template<typename T>
void List<T>::insert(T data, int index)
{

    if (index == 0)
    {
        push_front(data);
    }
    else
    {
        Node<T> *previous = this->head;

        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }

        Node<T> *newNode = new Node<T>(data, previous->pNext);

        previous->pNext = newNode;

        Size++;
    }





}

template<typename T>
void List<T>::removeAt(int index)
{
    if (index == 0)
    {
        pop_front();
    }
    else
    {
        Node<T> *previous = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }

        
        Node<T> *toDelete = previous->pNext;

        previous->pNext = toDelete->pNext;

        delete toDelete;

        Size--;
    }

}

template<typename T>
void List<T>::pop_back()
{
    removeAt(Size - 1);
}

/*template<typename T> List<T>::List(const List& other) 
{
    head = new Node<T>(other.head);
    Size = 1;
    while (Size !=other.Size)
    {
        this->push_back(other[Size]);
        Size++;
    }        
}*/

/*template<typename T>
List<T>::List(const List& other)
{
    Size = 0;
    while (this->Size != other.Size) {
        this->push_back(&other[Size]);
        this->Size++;
    }
}*/
int main()
{

    setlocale(LC_ALL, "ru");


    List<int> lst;
    lst.push_front(5);
    lst.push_front(7);
    lst.push_front(101);

    for (int i = 0; i < lst.GetSize(); i++)
    {
        cout << lst[i] << endl;
    }

    cout << endl << "pop_back " << endl << endl;

    lst.pop_back();

    for (int i = 0; i < lst.GetSize(); i++)
    {
        cout << lst[i] << endl;
    }

    return 0;
}

Answer 1

Конструктор копирования - конструирует объект на основе другого ранее созданного. Здесь вы не только копируете, но и конструируете объект, как это не парадоксально. Это значит что как и в любом конструкторе все поля объекта должны быть инициализированы - у вас этого нет. В методе push_back вы обращаетесь к неинициализированному полю head, это сразу неопределенное поведение то есть программа может делать все что угодно, а не то что вы написали в исходниках.

Второе, само копирование. В двух вариантах вы добавляете в конец списка одно и то же значение - здесь нужно последовательно обходить исходный список и каждый его элемент копировать в новый. Еще вы добавляете значение из-за переделов исходного списка: индексация с 0 поэтому other[Size] за пределами памяти, да еще в List::operator[] вы не проверяете корректность индекса.

// правильный вариант
template<typename T>
List<T>::List(const List& other)
    : Size(0)
    , head(nullptr)
{
    for(int i = 0; i < other.Size; ++i)
    {
         this->push_back(other[i]);
    }
}

Вообще доступ по индексу (читай случайный доступ) в односвязном списке не лучшая затея, так как сложность случайного доступа у списка O(n), а сложность вашего копирования будет O(n^3).

Можно добавлять в начало списка, сложность такого копирования будет O(n^2), только тогда исходный список нужно будет обходит с конца:

template<typename T>
List<T>::List(const List& other)
    : Size(0)
    , head(nullptr)
{
    for(int i = other.Size - 1; i > 0; --i)
    {
         this->push_front(other[i]);
    }
}

Ну а лучший вариант совсем без индексов, тогда будет O(n)

template<typename T>
List<T>::List(const List& other)
    : Size(0)
    , head(nullptr)
{
    Node * last = nullptr;
    for(Node * n = other.head; n != nullptr; n = n->pNext)
    {
         Node * item = new Node(n->data);
         if(!head)
         {
             head = item;
         }
         else
         {
             last->pNext = item;
         }
         last = item;
         ++Size;
    }
}

Answer 2

Можно так:

template<typename T> 
List<T>::List(const List& other) {
    if(!other.head) {
        Size = 0;
        head = nullptr;
        return;
    }

    head = new Node<T>(*other.head);
    Node<T>* cur = head;
    Size = 1;

    for(Node<T>* t = other.head->pNext; t != nullptr; t = t->pNext) {
        cur->pNext = new Node<T>(*t);
        cur = cur->pNext;
        ++Size;
    }
    cur->pNext = nullptr;
}

БЛОГ НА HUSL

Конструктор копирования для односвязного списка

Ответы (2 шт):