L’implementazione di una lista collegata è ansible senza utilizzare i puntatori o no?

La mia domanda è molto semplice, si può usare C ++, implementare una struttura di dati dell’elenco di collegamenti senza utilizzare i puntatori (nodes successivi)? Per qualificare ulteriormente la mia domanda, intendo si può creare una struttura di dati dell’elenco collegato utilizzando solo le istanze di class.

Una definizione di nodo comune potrebbe essere così:

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

Sono a conoscenza di std::list ecc, sono solo curioso di sapere se è ansible o meno – e se sì, come? Gli esempi di codice saranno molto apprezzati.

Altri chiarimenti:

  1. Gli inserimenti devono essere O (1).
  2. Traversal non dovrebbe essere più di O (n).
  3. Un nodo reale e un nodo null dovrebbero essere differenziabili.
  4. La dimensione della lista collegata dovrebbe essere limitata solo dalla quantità di memoria disponibile.

Certo, se non ti dispiace che l’elenco collegato abbia una dimensione massima, puoi allocare staticamente un array di nodes elenco e quindi utilizzare gli indici interi nell’array come valori “precedenti” e “successivi” per ciascun nodo, piuttosto che puntatori. Ho fatto questo in passato per risparmiare un po ‘di memoria (dato che un intero può essere 2 o 4 byte, mentre su un sistema a 64 bit un puntatore sarà 8 byte)

Si è ansible. Usa indici di array invece di puntatori.

Da Wikipedia :

In informatica, una lista collegata è una struttura di dati che consiste in una sequenza di record di dati tale che in ogni record c’è un campo che contiene un riferimento (cioè un collegamento) al record successivo nella sequenza.

Niente in quella definizione specifica il modo in cui il riferimento viene archiviato o utilizzato. Se non memorizzi un riferimento, non è un elenco collegato: è qualcos’altro.

Se il tuo objective è semplicemente quello di evitare l’uso di un puntatore (o riferimento a un object), l’utilizzo di un vettore con un indice è un’implementazione comune. (Uno dei motivi per utilizzare l’implementazione vettoriale / indice è la persistenza: è davvero difficile perseguire correttamente i riferimenti di puntatori / oggetti al di fuori dello spazio di memoria attivo).

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

Ispirato da un commento sulle origini delle liste collegate

Si potrebbe creare un elenco di celle cons usando temporaries, riferimenti const ed ereditarietà. Ma dovresti stare molto attento a non lasciare riferimenti ad esso oltre la sua vita. E probabilmente non potresti cavarcanvas con qualcosa di mutabile.

Questo è basato approssimativamente sull’implementazione Scala di questi elenchi (in particolare l’idea di usare l’ereditarietà e una sottoclass NilList piuttosto che usare i puntatori nulli).

 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. 

Anche se non sono sicuro di quale sia il contesto dietro la tua domanda, se fai un po ‘fuori dagli schemi pensando che sia sicuro che puoi.

DVK ha suggerito matrici, il che è abbastanza vero, ma gli array sono semplicemente involucri sottili attorno all’aritmetica del puntatore.

Che ne dici di qualcosa di completamente diverso: usa il filesystem per fare lo storage per te!

ad esempio, il file /linked-list/1 contiene i dati:

Dati 1!

5

e /linked-list/5 è il prossimo nodo nell’elenco …

Se sei disposto a hackerare abbastanza, tutto è ansible :-p

Nota che la complessità / velocità di detta implementazione dipende interamente dal tuo filesystem (cioè non è necessariamente O (1) per tutto)

Suppongo che l’utilizzo di riferimenti sia un imbroglio e, tecnicamente, ciò causa UB, ma qui vai:

 // 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ì, è ansible, non è necessario utilizzare i puntatori per un elenco di collegamenti. È ansible colbind un elenco senza utilizzare i puntatori. È ansible allocare staticamente un array per i nodes e invece di utilizzare il puntatore successivo e precedente, è sufficiente utilizzare gli indici. È ansible farlo per risparmiare un po ‘di memoria, ad esempio se l’elenco dei collegamenti non è superiore a 255, è ansible utilizzare’ char unsigned ‘come indice (facendo riferimento a C) e salvare 6 byte per le indicazioni successive e precedenti.

Potrebbe essere necessario questo tipo di array nella programmazione incorporata, poiché a volte i limiti di memoria possono essere fastidiosi.

Inoltre, tieni presente che i nodes dell’elenco di collegamenti non saranno necessariamente contigui nella memoria.

Supponiamo che la tua lista di link abbia 60000 nodes. L’allocazione di un nodo libero dall’array utilizzando una ricerca lineare dovrebbe essere inefficiente. Invece, puoi sempre mantenere il prossimo indice del nodo libero ogni volta:

Basta inizializzare la matrice come ogni indice successivo mostra l’indice dell’array corrente + 1 e firstEmptyIndex = 0.

Quando si assegna un nodo libero dall’array, afferrare il primo nodo EmptyIndex, aggiornare il primoEmptyIndex come indice successivo dell’indice dell’array corrente (non dimenticare di aggiornare l’indice successivo come Null o vuoto o altro dopo).

Quando si effettua la deallocazione, aggiornare il prossimo indice del nodo deallocating come firstEmptyIndex, quindi fare FirstEmptyIndex = deallocating index del nodo.

In questo modo crei te stesso una scorciatoia per allocare i nodes liberi dall’array.

Potresti creare una lista collegata usando i riferimenti , ma probabilmente sarebbe più complicata del necessario. dovresti implementare una lista collegata immutabile che sarebbe complicata senza un garbage collector integrato.

Le lingue che non supportano alcun tipo di riferimento possono ancora creare collegamenti sostituendo puntatori con indici di array. L’approccio consiste nel mantenere un array di record, in cui ogni record ha campi interi che indicano l’indice del nodo successivo (e possibilmente precedente) nell’array. Non è necessario utilizzare tutti i nodes dell’array. Se anche i record non sono supportati, è ansible utilizzare spesso array paralleli.

Ad esempio, considera il seguente record dell’elenco collegato che utilizza matrici anziché puntatori:

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

Crea una matrice con un numero elevato. E l’elenco dei punti Applica al primo elemento indice dell’array

 integer listHead; Entry Records[10000]; 

Controlla la pagina wiki: http://en.wikipedia.org/wiki/Linked_list per i dettagli, cerca “Elenchi collegati usando matrici di nodes”

Wow, NO? Sicuramente voi ragazzi non siete seri?

Tutto ciò di cui ha bisogno un elenco collegato è un collegamento. Niente dice che deve essere un puntatore. Considera il caso di voler memorizzare un elenco collegato in mem condiviso, dove l’addr di base è dinamico? La risposta è semplicemente, memorizzare il collegamento come Offset dall’inizio del blocco mem, (o qualche altra costante) e ridefinire l’iteratore per fare la logica effettiva di aggiungere l’addr di base. Ovviamente, anche l’inserimento etc dovrebbe essere modificato.

Ma abbastanza banale!

Allan

Un ansible approccio sarebbe quello di utilizzare un array di Nodes cui ogni nodo memorizza un indice (array) sul Node prev e next . Quindi, il tuo Node dovrebbe assomigliare a qualcosa:

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

Inoltre, sarà probabilmente necessario allocare dynamicmente l’array Node , implementare un po ‘di contabilità per ottenere e liberare spazio nell’array: ad esempio un array bool che memorizza gli indici non occupati nell’array Node , insieme a due funzioni che lo aggiorneranno ogni volta un nuovo Node / indice viene aggiunto o rimosso (sarà frammentato in quanto i nodes non saranno sempre contigui); trova un indice di un Node nella matrice: ad esempio sottraendo l’indirizzo del Node dal primo indirizzo dell’array.

Ecco come una ansible interfaccia di una lista doppiamente collegata utilizzando la tecnica sopra sarebbe simile a:

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

Potresti usarlo come benchmark e implementare qualcosa da solo.

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

È ansible utilizzare C ++, impiantare una struttura dati dell’elenco di collegamenti senza utilizzare i puntatori (nodes successivi)?
No.