Мои шаги:
1
2
pop_back()
mLast
теперь nullptrnext
первого узла хранит мусорное значение вместо nulltpr
LinkedList.h
template<typename T>
class LinkedList
{
public:
struct Node
{
T value;
struct Node* next = nullptr;
};
Node *mFirst = nullptr;
Node *mLast = nullptr;
public:
LinkedList();
void push_back(const T& value);
T pop_back();
bool isEmpty() const;
void increaseSize();
void decreaseSize();
unsigned long mSize;
private:
void moveNode(Node **node);
private:
friend std::ostream& operator<<(std::ostream& os, LinkedList<T>& list)
{
if (list.isEmpty())
return os << std::string();
// While there is a next node,
// write it's value to the output stream
os << "[";
Node *current = list.mFirst;
while (current)
{
os << current->value;
if (current->next)
os << ", ";
current = current->next;
}
os << "]";
return os;
}
};
template<typename T>
inline LinkedList<T>::LinkedList()
: mFirst(nullptr),
mLast(nullptr),
mSize(0)
{
}
template<typename T>
inline void LinkedList<T>::push_back(const T& value)
{
// Create a node
Node *node = new Node
{
value,
nullptr
};
if (!isEmpty())
{
// Last existed node points to the new created node
// and then new becomes the last
mLast->next = node;
mLast = node;
}
else
{
// The first node is the last if the list is empty
mLast = mFirst = node;
}
increaseSize();
}
template<typename T>
inline T LinkedList<T>::pop_back()
{
if (isEmpty())
return NULL;
// Getting the last value
T lastValue = mLast->value;
moveNode(&mLast);
decreaseSize();
return lastValue;
}
template<typename T>
inline void LinkedList<T>::moveNode(Node **node)
{
if (!node || !(*node))
return;
delete *node;
*node = nullptr;
}
template<typename T>
inline bool LinkedList<T>::isEmpty() const
{
return (mFirst) ? false : true;
}
template<typename T>
inline void LinkedList<T>::increaseSize()
{
++mSize;
}
template<typename T>
inline void LinkedList<T>::decreaseSize()
{
if (mSize <= 0)
return;
--mSize;
}
main.cpp
LinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.pop_back();
cout << list;
return 0;
Я могу сделать что-то вроде этого:
Node **current = &mFirst;
while (*current)
{
if (*current != mLast)
{
current = &((*current)->next);
continue;
}
delete *current;
*current = nullptr;
current = nullptr;
mLast = nullptr;
break;
}
... но это кажется неправильным, потому что что, если у меня есть 1000 элементов в списке: c Или это правильный способ работы LinkedList? Даже если да, я все равно хочу знать, как решить проблему
Я также пытался использовать std::shared_ptr вместо обычных указателей, но столкнулся с той же проблемой (это был первый раз, когда я использовал умные указатели, может быть, я просто сделал это неправильно. Я просто заменил все указатели на std::shared_ptr)
Одним из основных недостатков односвязного списка является объем обхода, который вам нужно выполнить для определенных вещей, например, получить узел перед последним узлом или сам последний узел, если вы не сохраняете указатель на него.
Но если вы удалите этот последний узел и сможете заменить его кешированным указателем на узел до этого, вы застрянете, заменив кешированный узел перед хвостом. И с чем? Кэш третий последний хорошо? А как насчет обновления? К тому времени, когда вы выполните все необходимое кэширование, у вас будет двусвязный список.
@ user4581301 да, как Влад упомянул ниже, я должен использовать std::optional<T>
вместо NULL
@RetiredNinja кажется, что я пытаюсь усложнить LinkedList, чего мне не следует делать
Ваши функции pop_back и moveNode неправильно сбрасывают элемент данных mLast
То есть после вызова этих функций для члена данных mLast устанавливается значение nullptr вместо того, чтобы указывать на узел, предшествующий удаленному последнему узлу, и изменяя его член данных следующим.
Так как вы используете односвязный список, то метод pop_back
в любом случае будет неэффективен. Вам нужно будет пройти весь список, чтобы найти узел, который предшествует последнему удаленному узлу.
Также обратите внимание на то, что этот оператор возврата
template<typename T>
inline T LinkedList<T>::pop_back()
{
if (isEmpty())
return NULL;
....
тоже не имеет смысла. Вместо этого вы должны либо выдать исключение, либо вернуть объект типа std::optional<T>
(соответственно изменив возвращаемый тип функции).
Также определение класса будет более читабельным, если функция друга будет перемещена в общедоступный раздел. И его второй параметр должен быть объявлен с квалификатором const
friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);
И член данных mSize
не должен быть объявлен общедоступным.
unsigned long mSize;
Вместо этого вы должны написать для него публичный геттер.
И, по крайней мере, вы должны явно определить деструктор.
Эти общедоступные функции-члены
template<typename T>
inline void LinkedList<T>::increaseSize()
{
++mSize;
}
template<typename T>
inline void LinkedList<T>::decreaseSize()
{
if (mSize <= 0)
return;
--mSize;
}
не имеют смысла и должны быть удалены.
О, спасибо за обзор кода, я не знал о std::Optional<T>. И спасибо за упоминание функций, которые не имеют смысла, я уберу это.
Сначала у меня в функции moveNode
было что-то вроде этого: 1) Node *prev = (*node); 2) (*узел) = (*узел)->следующий; 3) удалить предыдущую; 4) предыдущая = nullptr; - но это все еще не влияет на значение мусора
Я догадался, что пытаюсь установить для переменной prev
значение nullptr, чтобы это не повлияло на реальную переменную next
, которую я изначально хотел изменить. Есть ли способ сделать это без повторения всего списка?
@MikelGrenlou Нет возможности получить доступ к узлу, предшествующему хвостовому узлу, без обхода всего списка. Посмотрите на std::forward_list. У него нет метода pop_back. В вашем списке должны быть функции, которые добавляют узлы в начало списка и удаляют их из начала списка.
@MikelGrenlou Вовсе нет. Пожалуйста.:)
Примечание:
pop_back
возвратNULL
с пустым списком позже приведет к фатальным последствиям. Подумайте, что произойдет сLinkedList<std::string>
, когда он попытается сконструироватьstring
для возврата из нулевого указателя.