¿Es posible o no la implementación de una lista vinculada sin utilizar punteros?

Mi pregunta es muy simple: ¿puede uno usar C ++, implementar una estructura de datos de listas de enlaces sin usar punteros (nodos siguientes)? Para calificar aún más mi pregunta, me refiero a que se puede crear una estructura de datos de la Lista Vinculada utilizando solo instancias de clase.

Una definición de nodo común podría ser así:

template struct node { T t; node* next; node* prev; }; 

Estoy al tanto de std::list , etc., solo tengo curiosidad por saber si es posible o no, y si es así, ¿cómo? Los ejemplos de código serán muy apreciados.

Más aclaraciones:

  1. Las inserciones deben ser O (1).
  2. La travesía no debe ser más que O (n).
  3. Un nodo real y un nodo nulo deben ser diferenciables.
  4. El tamaño de la lista vinculada solo debe estar limitado por la cantidad de memoria disponible.

Claro, si no le importa que la lista enlazada tenga un tamaño máximo, puede asignar estáticamente una matriz de nodos de lista, y luego usar índices enteros en la matriz como sus valores “anterior” y “siguiente” para cada nodo, en lugar de punteros. He hecho esto en el pasado para guardar un poco de memoria (ya que un entero puede ser de 2 o 4 bytes, mientras que en un sistema de 64 bits, un puntero será de 8 bytes)

Si es posible. Use índices de matriz en lugar de punteros.

De la Wikipedia :

En ciencias de la computación, una lista vinculada es una estructura de datos que consiste en una secuencia de registros de datos tal que en cada registro hay un campo que contiene una referencia (es decir, un enlace) al siguiente registro de la secuencia.

Nada en esa definición especifica la manera en que se guarda o utiliza la referencia. Si no almacena una referencia, no es una lista vinculada, es otra cosa.

Si su objective es simplemente evitar el uso de un puntero (o referencia de objeto), entonces el uso de un vector con un índice es una implementación común. (Una de las razones para usar la implementación de vector / índice es la persistencia: es realmente difícil persistir correctamente las referencias de punteros / objetos fuera del espacio de memoria activo).

Sí:

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

Inspirado por un comentario sobre los orígenes de las listas vinculadas

Se podría crear una lista de células cons usando temporarios, referencias de referencia y herencia. Pero tendrías que tener mucho cuidado de no guardar ninguna referencia más allá de su tiempo de vida. Y probablemente no puedas salirte con nada mutable.

Esto se basa aproximadamente en la implementación de Scala de estas listas (en particular, la idea de usar herencia y una subclase NilList en lugar de utilizar punteros nulos).

 template struct ConsList{ virtual T const & car() const=0; virtual ConsList const & cdr() const=0; } template struct ConsCell:ConsList{ ConsCell(T const & data_, ConsList const & next_): data(data_),next(next_){} virtual T const & car() const{return data;} virtual ConstList const & cdr() const{return next;} private: T data; ConsList const & next; } template struct NilList:ConsList{ // replace std::exception with some other kind of exception class virtual T const & car() const{throw std::exception;} virtual ConstList const & cdr() const{throw std::exception;} } void foo(ConsList const & l){ if(l != NilList()){ //... foo(NilList.cdr()); } } foo(ConsList(1,ConsList(2,ConsList(3,NilList())))); // the whole list is destructed here, so you better not have // any references to it stored away when you reach this comment. 

Aunque no estoy seguro de cuál es el contexto detrás de tu pregunta, si lo haces un poco de la caja pensando que estoy seguro de que puedes.

DVK sugirió arreglos, lo cual es bastante cierto, pero los arreglos son simplemente envoltorios delgados alrededor de la aritmética del puntero.

¿Qué tal algo completamente diferente: utilice el sistema de archivos para hacer el almacenamiento por usted!

por ejemplo, el archivo /linked-list/1 contiene los datos:

Datos 1!

5

y /linked-list/5 es el siguiente nodo en la lista …

Si estás dispuesto a hackear lo suficiente, todo es posible :-p

Tenga en cuenta que la complejidad / velocidad de dicha implementación depende completamente de su sistema de archivos (es decir, no es necesariamente O (1) para todo)

Supongo que usar referencias es trampa y, técnicamente, esto causa UB, pero aquí tienes:

 // Beware, un-compiled code ahead! template< typename T > struct node; template< typename T > struct links { node& prev; node& next; link(node* prv, node* nxt); // omitted }; template< typename T > struct node { T data; links linked_nodes; node(const T& d, node* prv, node* nxt); // omitted }; // technically, this causes UB... template< typename T > void my_list::link_nodes(node* prev, node* next) { node* prev_prev = prev.linked_nodes.prev; node* next_next = next.linked_nodes.next; prev.linked_nodes.~links(); new (prev.linked_nodes) links(prev_prev, next); next.linked_nodes.~links(); new (next.linked_nodes) links(next, next_next); } template< typename T > void my_list::insert(node* at, const T& data) { node* prev = at; node* next = at.linked_nodes.next; node* new_node = new node(data, prev, next); link_nodes(prev, new_node); link_nodes(new_node, next); } 

Sí puede, no es necesario usar punteros para una lista de enlaces. Es posible vincular una lista sin usar punteros. Puede asignar estáticamente una matriz para los nodos, y en lugar de usar el puntero siguiente y anterior, puede usar índices. Puede hacerlo para ahorrar memoria, si su lista de enlaces no es mayor que 255, por ejemplo, puede usar ‘char sin signo’ como índice (haciendo referencia a C) y guardar 6 bytes para las indicaciones siguientes y anteriores.

Es posible que necesite este tipo de matriz en la progtwigción integrada, ya que las limitaciones de la memoria pueden ser problemáticas a veces.

También tenga en cuenta que los nodos de su lista de enlaces no serán necesariamente contiguos en la memoria.

Digamos que su lista de enlaces tendrá 60000 nodos. La asignación de un nodo libre de la matriz con una búsqueda lineal debería ser ineficiente. En cambio, puede mantener el siguiente índice de nodo libre cada vez:

Simplemente inicialice su matriz ya que cada índice siguiente muestra el índice de matriz actual + 1 y firstEmptyIndex = 0.

Al asignar un nodo libre desde la matriz, tome el primer nodoEmptyIndex, actualice el primerEmptyIndex como siguiente índice del índice de matriz actual (no olvide actualizar el siguiente índice como nulo o vacío o lo que sea después de esto).

Al desasignar, actualice el siguiente índice del nodo de desasignación como firstEmptyIndex, luego haga firstEmptyIndex = desasignando el índice del nodo.

De esta forma, se crea un atajo para asignar nodos libres desde la matriz.

Podría hacer una lista vinculada usando referencias , pero eso probablemente sería más complicado de lo necesario. tendrías que implementar una lista enlazada inmutable que sería complicada sin un recolector de basura incorporado.

Los idiomas que no admiten ningún tipo de referencia aún pueden crear enlaces al reemplazar punteros con índices de matriz. El enfoque es mantener una matriz de registros, donde cada registro tiene campos enteros que indican el índice del nodo siguiente (y posiblemente anterior) en la matriz. No todos los nodos en la matriz necesitan ser utilizados. Si los registros tampoco son compatibles, a menudo se pueden usar matrices paralelas.

Como ejemplo, considere el siguiente registro de lista vinculada que utiliza matrices en lugar de punteros:

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

Crea una matriz con un número alto. Y lista de puntos Visita el primer elemento de índice en la matriz

 integer listHead; Entry Records[10000]; 

Consulte la página wiki: http://en.wikipedia.org/wiki/Linked_list para obtener detalles, busque “Listas enlazadas usando matrices de nodos”

Wow, ¿NO? Seguramente ustedes no hablan en serio?

Todo lo que necesita una lista vinculada es un enlace. Nada dice que tiene que ser un puntero. Considere el caso de querer almacenar una lista vinculada en la memoria compartida, donde la base addr es dinámica. La respuesta es simplemente, almacenar el enlace como un desplazamiento desde el inicio del bloque de memoria (o alguna otra constante) y redefinir el iterador para que haga la lógica real de agregar el addr base. Obviamente, insertar, etc. tendría que ser cambiado también.

¡Pero bastante trivial!

Alano

Un posible enfoque sería usar una matriz de Nodes donde cada nodo almacena un índice (matriz) en el prev y el next Node . Por lo tanto, su Node se vería algo así como:

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

Además, probablemente tendrá que asignar dinámicamente la matriz de Node , implementar algunos registros para obtener espacio libre en la matriz: por ejemplo, una matriz bool que almacena los índices desocupados en la matriz de Node , junto con dos funciones que la actualizarán cada vez se agrega o elimina un nuevo Node / índice (se fragmentará ya que los nodos no siempre estarán contiguos); encuentre un índice de un Node en la matriz: por ejemplo, restando la dirección del Node de la primera dirección de la matriz.

Así es como se vería una posible interfaz de una lista doblemente vinculada usando la técnica anterior:

 template  // 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 (ie 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; } }; 

Podría usar eso como punto de referencia e implementar algo por su cuenta.

 template  void DList::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; } 

¿Puede alguien usar C ++, implementar una estructura de datos de listas de enlaces sin usar punteros (próximos nodos)?
No.