resueltos - listas enlazadas en c++ codigo fuente

¿Es posible o no una implementación de lista enlazada sin usar punteros?

Question

Mi pregunta es muy simple, ¿se puede usar C ++ para implementar una estructura de datos de lista 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 lista enlazada utilizando solo instancias de clase.

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

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

Soy consciente 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. El recorrido 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 enlazada solo debe estar limitado por la cantidad de memoria disponible.

Answer 1

Claro, si no le importa que la lista vinculada tenga un tamaño máximo, puede asignar una matriz de nodos de lista de forma estática 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)

Answer 2

De Wikipedia :

En informática, una lista enlazada es una estructura de datos que consiste en una secuencia de registros de datos de manera 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 almacena o utiliza la referencia. Si no almacena una referencia, no es una lista vinculada, es otra cosa.

Si su objetivo es simplemente evitar el uso de un puntero (o referencia de objeto), usar 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 los punteros / referencias de objetos fuera del espacio de memoria activa).

Answer 3

Los idiomas que no admiten ningún tipo de referencia todavía pueden crear enlaces al reemplazar los punteros con índices de matriz. El enfoque es mantener una matriz de registros, donde cada registro tiene campos enteros que indican el índice del siguiente nodo (y posiblemente anterior) en la matriz. No es necesario utilizar todos los nodos de la matriz. 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. }

Creata una matriz con un número alto. Y apunte listHead al 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 más información, busque "Listas enlazadas utilizando matrices de nodos"

Answer 4

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

Answer 5

Sí, puede, no es necesario usar punteros para una lista de enlaces. Es posible vincular una lista sin utilizar punteros. Puede asignar estáticamente una matriz para los nodos, y en lugar de usar el puntero siguiente y anterior, solo puede usar índices. Puede hacer eso para guardar algo de memoria; si su lista de enlaces no supera los 255, por ejemplo, puede usar el ''carácter sin signo'' como índice (referencia a C) y guardar 6 bytes para las indicaciones siguientes y anteriores.

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

También tenga en cuenta que los nodos de la 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 mediante una búsqueda lineal debería ser ineficiente. En su lugar, puedes mantener el siguiente índice de nodo gratuito cada vez:

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

Cuando asigne un nodo libre de la matriz, tome el nodo firstEmptyIndex, actualice firstEmptyIndex como el siguiente índice del índice de la matriz actual (no olvide actualizar el siguiente índice como Null 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 lo siguiente: indexEmptyIndex = desasignar el índice de nodo.

De esta manera, se creará un acceso directo para asignar nodos libres de la matriz.

Answer 6

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 en un comentario sobre los orígenes de las listas enlazadas.

Answer 7

Si bien no estoy seguro de cuál es el contexto detrás de tu pregunta, si haces un poco fuera de la caja, estoy seguro de que puedes hacerlo.

DVK sugirió matrices, lo cual es bastante cierto, pero las matrices son simplemente envolturas finas alrededor de la aritmética de punteros.

¿Qué tal algo completamente diferente: use 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)

Answer 8

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

Answer 9

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<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 10

Un posible enfoque sería utilizar una matriz de Nodes donde cada nodo almacena un índice (matriz) en el Node prev y next . 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 cierta contabilidad para obtener y liberar espacio en la matriz: por ejemplo, una matriz de bool que almacena los índices desocupados en la matriz de Node , junto con dos funciones que lo actualizarán cada vez se agrega o elimina un nuevo Node / índice (se fragmentará, ya que los nodos no siempre serán contiguos); encuentre un índice de un Node en la matriz: por ejemplo, restando la dirección del Node a la primera dirección de la matriz.

Aquí es cómo se vería una posible interfaz de una lista doblemente enlazada utilizando la técnica anterior:

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

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

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

Answer 11

Uno podría crear una lista de celdas de contras usando temporarios, referencias const y herencia. Pero tendrías que tener mucho cuidado de no mantener ninguna referencia a él más allá de su vida útil. Y probablemente no podrías salirte con nada mutable.

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

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 12

Wow no Seguramente ustedes no son serios?

Todo lo que necesita una lista enlazada es un enlace. Nada dice que tiene que ser un puntero. Considere el caso de querer almacenar una lista enlazada en un mem compartido, donde el addr base es dinámico? La respuesta es simplemente, almacene el enlace como un Desplazamiento desde el inicio del bloque mem (o alguna otra constante) y redefina el iterador para hacer la lógica real de agregar el addr base. Obviamente, el inserto, etc., tendría que ser cambiado también.

¡Pero bastante trivial!

Alano

Answer 13

¿Se puede usar C ++, implementar una estructura de datos de lista de enlaces sin usar punteros (nodos siguientes)?
No.