I am new to "modern" C++ and decided to learn about smart pointers by implementing a doubly linked list.
I have a few problems with this code: Should the tail pointer be a weak pointer? Should the head pointer be a unique pointer (If yes, then the node after head will have a weak_ptr to the head node, causing a unique_ptr and a weak pointer pointing to the same object)?
#include <iostream>
#include <memory>
template <typename T>
class LinkedList {
public:
LinkedList();
int GetLength() const;
void Print() const;
// TODO: Implement and return an iterator.
void Append(T data);
// TODO: Implement and return an iterator.
void Prepend(T data);
bool Delete(T data);
private:
struct ListNode {
T data;
std::shared_ptr<ListNode> next;
std::weak_ptr<ListNode> prev;
ListNode(T data) : data(data) {}
};
int length;
std::shared_ptr<ListNode> head;
std::shared_ptr<ListNode> tail;
void Delete(std::shared_ptr<ListNode> ptr);
};
template <typename T>
LinkedList<T>::LinkedList()
: length(0) {}
template <typename T>
int LinkedList<T>::GetLength() const {
return length;
}
template <typename T>
void LinkedList<T>::Print() const {
std::shared_ptr<ListNode> h(head);
std::cout << "List (length = " << length << "): ";
while (h) {
std::cout << h->data << " ";
h = h->next;
}
std::cout << std::endl;
}
template <typename T>
void LinkedList<T>::Append(T data) {
std::shared_ptr<ListNode> node_ptr(std::make_shared<ListNode>(data));
node_ptr->prev = tail;
if (tail) {
tail->next = node_ptr;
tail = std::move(node_ptr);
} else {
tail = std::move(node_ptr);
head = tail;
}
length++;
}
template <typename T>
void LinkedList<T>::Prepend(T data) {
std::shared_ptr<ListNode> node_ptr(std::make_shared<ListNode>(data));
node_ptr->next = head;
if (head) {
head->prev = node_ptr;
head = std::move(node_ptr);
} else {
head = std::move(node_ptr);
tail = head;
}
length++;
}
template <typename T>
bool LinkedList<T>::Delete(T data) {
std::shared_ptr<ListNode> ptr = head;
while (ptr) {
if (ptr->data == data) {
Delete(ptr);
return true;
}
ptr = ptr->next;
}
return false;
}
template <typename T>
void LinkedList<T>::Delete(std::shared_ptr<ListNode> ptr) {
auto shared_prev = (ptr->prev).lock();
if (head == ptr) {
head = ptr->next;
}
if (tail == ptr) {
tail = shared_prev;
}
if (shared_prev) {
shared_prev->next = ptr->next;
}
if (ptr->next) {
ptr->next->prev = ptr->prev;
}
length--;
}
Smart Pointers
andContainers
. You usually don't implement the containers in terms ofSmart Pointers
the whole point is that theContainer
is doing its own resource management. \$\endgroup\$NULL
everywhere. \$\endgroup\$