Подтвердить что ты не робот

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

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

Общее определение node может быть таким:

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

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

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

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

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

Ответ 3

От Wikipedia:

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

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

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

Ответ 4

Да:

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

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

Ответ 5

Можно создать список cons-cells, используя временные ссылки, ссылки на 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.

Ответ 6

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

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

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

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

Данные 1!

5

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

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

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

Ответ 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);
}

Ответ 8

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

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

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

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

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

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

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

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

Ответ 9

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

Ответ 10

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

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

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

Создайте массив с большим числом. И point listHead для первого элемента индекса в массиве

integer listHead;
Entry Records[10000];

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

Ответ 11

Ничего себе, НЕТ? Неужели вы, ребята, не серьец?

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

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

Аллана

Ответ 12

Возможным подходом было бы использовать массив Nodes, где каждый node хранит индекс (массив) в prev и next Node. Таким образом, ваш Node будет выглядеть примерно так:

struct Node 
{
    T data;
    int prev;    // index of the previous Node of the list
    int next;    // index of the next Node of the list
}

Кроме того, вам, вероятно, придется динамически выделять массив Node, реализовать некоторую бухгалтерию для получения и свободного пространства в массиве: например, массив bool, который хранит незанятые индексы в массиве Node, вдоль с двумя функциями, которые будут обновлять его каждый раз, когда добавляется или удаляется новый Node/index (он будет фрагментирован, поскольку узлы не будут всегда смежными); найдите индекс a Node в массиве: например, вычитая адрес Node из первого адреса массива.

Вот как выглядит возможный интерфейс двусвязного списка с использованием вышеупомянутого метода:

template <typename T>                          // T type Node in your case
class DList
{
    T** head;                                  // array of pointers of type Node
    int first;                                 // index of first Node
    int last;                                  // index of last Node

    bool* available;                           // array of available indexes 
    int list_size;                             // size of list

    int get_index();                           // search for index with value true in bool available
    void return_index(int i);                  // mark index as free in bool available

    std::ptrdiff_t link_index(T*& l) const;    // get index of Node

    void init();                               // initialize data members
    void create();                             // allocate arrays: head and available

    void clear();                              // delete array elements
    void destroy();                            // delete head

public:
    DList();                                   // call create() and init()
    ~DList();                                  // call clear() and destroy()

    void push_back(T* l);
    void push_front(T* l);
    void insert(T*& ref, T* l);                // insert l before ref

    T* erase(T* l);                            // erase current (i.e. l) and return next
    T* advance(T* l, int n);                   // return n-th link before or after currnet

    std::size_t size() const;
    int capacity () const { return list_size; }
};

Вы можете использовать это как тест и реализовать что-то самостоятельно.

template <typename T>
void DList<T>::push_back(T* l)
{
    if (l == nullptr)
    {
        throw std::invalid_argument("Dlist::push_back()::Null pointer as argument!\n");
    }

    int index = get_index();
    head[index] = l;

    if (last != -1)
    {
        head[last]->next = index;
        head[index]->prev = last;
    }
    else
    {
        first = index;
        head[index]->prev = -1;
    }

    last = index;
    head[index]->next = -1;
}

Ответ 13

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