Могут ли ссылки заменить указатели?
В частности, мне интересно, почему мы используем указатели в типичной реализации связанного списка. Есть ли какие-либо проблемы, которые может вызвать следующая реализация узла?
template <typename T>
class Node {
T data;
Node<T>& next;
Node<T>& prev;
};
Есть ли какая-то причина, по которой мы должны использовать указатели здесь вместо ссылок?
Решение
Вы не можете устанавливать ссылки после их создания, что делает реализацию не изменяемого связного списка несколько сложной. (Вам нужно будет обернуть ссылки в объекты, которые вы можете переписать, когда захотите изменить ссылку).
Также нет способа установить значение NULL для ссылки, поэтому для представления концов вашего списка потребуется некоторое воображение.
Вероятно, лучше придерживаться указателей в связанном списке, или даже лучше использовать std::list<>,
Другие решения
Ссылки Lvalue не могут заменить указатели; они делают разные вещи.
Ссылка lvalue должна быть инициализирована lvalue, и ссылка lvalue будет ссылаться на этот объект до конца его жизни. Это не может быть отскок. Это создает две непосредственные проблемы для вашего узла списка.
Как вы начинаете список? Вы хотите построить узел, который не имеет «предыдущего», но prev элемент должен быть инициализирован с Node объект. Вы могли бы использовать Node чья prev Самостоятельно представлять заголовок списка, но это обходит неудачный выбор ссылки на lvalue. (Например. Node<T> emptylist = { T(), emptylist, emptylist }; //eurgh)
Во-вторых, как вы управляете списком? Вы не можете изменить привязки next а также prev Это означает, что единственный способ изменить список — это создать совершенно новый набор узлов и копировать каждый data элемент.