Возможна ли реализация Linked-List без использования указателей или нет?

Question

Мой вопрос очень прост, можно ли с помощью C ++ реализовать структуру данных списка ссылок без использования указателей (следующих узлов)?Чтобы уточнить мой вопрос, я имею в виду, можно ли создать структуру данных Linked-List, используя только экземпляры классов.

Общее определение узла может выглядеть так:

template<typename T>
struct node
{
   T t;
   node<T>* next;
   node<T>* prev;
};

I 'Мне известно о std::list и т.д., мне просто интересно узнать, возможно ли это или нет - и если да, то как?Примеры кода будут с благодарностью.

Дополнительные пояснения:

1. Вставки должны быть O (1).
2. Обход должен быть не более O (n).
3. Реальный узел и нулевой узел должны быть дифференцируемы.
4. Размер связанного списка должен быть толькоограничено объемом доступной памяти.

Answer 1

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

Answer 2

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

Answer 3

Да

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;
  }
};

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

Answer 4

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

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

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

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

Answer 5

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

Это примерно основано на реализации этих списков в 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.

Answer 6

Да, вы можете, нет необходимости использовать указатели для списка ссылок. Можно связать список без использования указателей. Вы можете статически выделить массив для узлов, и вместо использования следующего и предыдущего указателя вы можете просто использовать индексы. Вы можете сделать это, чтобы сэкономить память, если, например, ваш список ссылок не превышает 255, вы можете использовать «unsigned char» в качестве индекса (ссылаясь на C) и сохранить 6 байтов для следующих и предыдущих указаний.

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

Также имейте в виду, что ваши узлы списка ссылок не обязательно должны быть смежными в памяти.

Допустим, в вашем списке ссылок будет 60000 узлов. Выделение свободного узла из массива с использованием линейного поиска должно быть неэффективным. Вместо этого вы можете просто хранить следующий индекс свободных узлов:

Просто инициализируйте ваш массив, так как каждый следующий индекс показывает текущий индекс массива + 1, а firstEmptyIndex = 0.

При выделении свободного узла из массива, захватите узел firstEmptyIndex, обновите firstEmptyIndex как следующий индекс текущего индекса массива (не забудьте обновить следующий индекс как Null или пустой или любой другой после этого).

При освобождении обновите следующий индекс освобождающего узла как firstEmptyIndex, затем выполните firstEmptyIndex = индекс освобождающего узла.

Таким образом, вы создаете себе ярлык для выделения свободных узлов из массива.

Answer 7

Полагаю, использование ссылок - это мошенничество и, технически, это вызывает 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);
}

Answer 8

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

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

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

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

Данные 1!

5

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

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

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

Answer 9

Языки, которые не поддерживают ссылки любого типа, могут создавать ссылки, заменяя указатели индексами массива. Подход заключается в том, чтобы хранить массив записей, где каждая запись имеет целочисленные поля, указывающие индекс следующего (и, возможно, предыдущего) узла в массиве. Не все узлы в массиве должны быть использованы. Если записи также не поддерживаются, часто можно использовать параллельные массивы.

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

record Entry {
integer next; // index of next entry in array
string data; // can be anything a struct also. }

Создать массив с большим номером. И укажите listHead на первый элемент индекса в массиве

integer listHead;
Entry Records[10000];

Проверьте страницу вики: http://en.wikipedia.org/wiki/Linked_list для получения подробной информации, выполните поиск по запросу «Связанные списки с использованием массивов узлов»

Answer 10

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