Реализация Связанного списка, не используя возможные указатели или нет?

Конечно, если вы не возражаете, чтобы связанный список имел максимальный размер, вы можете статически выделить массив узлов списка, а затем использовать целочисленные индексы в массиве в качестве «предыдущего» и "следующие" значения для каждого узла, а не указатели. Я делал это в прошлом, чтобы сэкономить немного памяти (поскольку целое число может быть 2 или 4 байта, тогда как в 64-битной системе указатель будет 8 байтов)

Можно ли, используя C++, реализовать структуру данных link-list без использования указателей (следующих узлов)?
Нет.

Хотя я не уверен в том, какой контекст стоит за вашим вопросом, если вы немного поразмыслите, я уверен, что сможете.

DVK предложил массивы, что совершенно верно, но массивы - это просто тонкая обертка вокруг арифметики указателей.

Как насчет чего-то совершенно иного: использовать файловую систему для хранения данных!

например, файл /linked-list/1 содержит данные:

Данные 1!

5

а /linked-list/5 - это следующий узел в списке...

Если вы готовы взломать достаточно, все возможно :-p

Обратите внимание, что сложность / скорость реализации полностью зависит от вашей файловой системы (т.е. это не обязательно O(1) для всего)

Я полагаю, что использование ссылок является обманом и, технически, это вызывает UB, но вот, пожалуйста:

// Beware, un-compiled code ahead!
template< typename T >
struct node;

template< typename T >
struct links {
  node<T>& prev;
  node<T>& next;
  link(node<T>* prv, node<T>* nxt); // omitted
};

template< typename T >
struct node {
  T data;
  links<T> linked_nodes;
  node(const T& d, node* prv, node* nxt); // omitted
};

// technically, this causes UB...
template< typename T >
void my_list<T>::link_nodes(node<T>* prev, node<T>* next)
{
  node<T>* prev_prev = prev.linked_nodes.prev;
  node<T>* next_next = next.linked_nodes.next;
  prev.linked_nodes.~links<T>();
  new (prev.linked_nodes) links<T>(prev_prev, next);
  next.linked_nodes.~links<T>();
  new (next.linked_nodes) links<T>(next, next_next);
}

template< typename T >
void my_list<T>::insert(node<T>* at, const T& data)
{
  node<T>* prev = at;
  node<T>* next = at.linked_nodes.next;
  node<T>* new_node = new node<T>(data, prev, next);

  link_nodes(prev, new_node);
  link_nodes(new_node, next);
}

Да, это возможно. Используйте индексы массивов вместо указателей.

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

Да:

class node { 
  std::string filenameOfNextNode;
  std::string filenameOfPrevNode;
  std::string data;
  node nextNode() {
    node retVal;
    std::ifstream file(filenameOfNextNode.c_str());
    retVal.filenameOfNextNode = file.getline();
    retVal.filenameOfPrevNode = file.getline();
    retVal.data = file.getline();
    return retVal;
  }
};

Навеяно комментарием о происхождении связанных списков

Можно создать список конс-коллекций, используя временные элементы, const-ссылки и наследование. Но вам придется быть очень осторожным, чтобы не хранить никаких ссылок на него после окончания срока его жизни. И вы, вероятно, не сможете обойтись без чего-либо изменяемого.

Это основано примерно на реализации этих списков в Scala (в частности, идея использования наследования и подкласса NilList вместо использования нулевых указателей).

template<class T>
struct ConsList{
   virtual T const & car() const=0;
   virtual ConsList<T> const & cdr() const=0;
}

template<class T>
struct ConsCell:ConsList{
   ConsCell(T const & data_, ConsList<T> const & next_):
        data(data_),next(next_){}
   virtual T const & car() const{return data;}
   virtual ConstList<T> const & cdr() const{return next;}

   private:
     T data;
     ConsList<T> const & next;
}

template<class T>
struct NilList:ConsList{  
   // replace std::exception with some other kind of exception class
   virtual T const & car() const{throw std::exception;}
   virtual ConstList<T> const & cdr() const{throw std::exception;}
}

void foo(ConsList<int> const & l){
   if(l != NilList<int>()){
      //...
      foo(NilList.cdr());
   }
}

foo(ConsList<int>(1,ConsList(2,ConsList<int>(3,NilList<int>()))));
// the whole list is destructed here, so you better not have
// any references to it stored away when you reach this comment.

Из Википедия :

В информатике связанный список структура данных, состоящая из последовательность записей данных такая, что в в каждой записи есть поле, содержит ссылку (т.е. ссылку) на следующая запись в последовательности.

Ничто в этом определении не определяет способ хранения или использования ссылки. Если вы не храните ссылку, это не связанный список - это что-то еще.

Если ваша цель - просто избежать использования указателя (или ссылки на объект), тогда использование вектора с индексом является обычной реализацией. (Одной из причин использования реализации вектора / индекса является постоянство: действительно сложно правильно сохранить указатели / ссылки на объекты за пределами активной области памяти.)

Вау, НЕТ? Неужто вы, ребята, несерьезно?

Все, что нужно связному списку, - это ссылка. Ничто не говорит о том, что это должен быть указатель. Рассмотрим случай, когда вы хотите сохранить связанный список в общей памяти, где базовый адрес является динамическим? Ответ прост: сохраните ссылку как смещение от начала блока памяти (или какой-либо другой константы) и переопределите итератор, чтобы выполнить фактическую логику добавления базового адреса. Очевидно, также придется изменить вставку и т. Д.

Но довольно тривиально!

Аллан