È un'implementazione di elenco collegato senza utilizzare i puntatori possibili o no?

Question

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

Una definizione nodo comune come potrebbe essere così:

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

Sono consapevole di std::list ecc, sono solo curioso di sapere se il suo possibile o no - e se sì, come? Gli esempi di codice saranno molto apprezzati.

Ulteriori chiarimenti:

1. inserimenti devono essere O (1).
2. L'attraversamento dovrebbe essere non più di O (n).
3. Un nodo reale e un nodo null devono essere differenziabili.
4. La dimensione dell'elenco collegato deve essere limitata solo dalla quantità di memoria disponibile.

Answer 1

Uno che utilizza C++, impone una struttura di dati dell'elenco di collegamenti senza utilizzare i puntatori (nodi successivi)?

Answer 2

Sì, è possibile. Usa indici di array invece di puntatori.

Answer 3

Certo, se non ti dispiace che l'elenco collegato abbia una dimensione massima, puoi allocare staticamente un array di nodi elenco e quindi utilizzare gli indici interi nell'array come valori "precedenti" e "successivi" per ogni nodo, piuttosto che puntatori. Ho fatto in passato questo 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)

Answer 4

Si potrebbe fare un collegamento -list utilizzando references, ma che sarebbe probabilmente più complicato del necessario. dovresti implementare una lista collegata immutable che sarebbe complicata senza un garbage collector incorporato.

Answer 5

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

Questo è basato approssimativamente sull'implementazione Scala di questi elenchi (in particolare l'idea di utilizzare l'ereditarietà e una sottoclasse NilList piuttosto che l'utilizzo di puntatori nulli).

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

Mentre io non sono sicuro solo ciò che il contesto dietro la domanda è, se si fa un po 'fuori del pensiero scatola sono sicuro che si può.

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

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

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

Dati 1!

e /linked-list/5 è il nodo successivo nella lista ...

Se siete disposti a incidere a sufficienza, tutto è possibile :-p

nota che ha detto di implementazione complessità/velocità dipende interamente dal tuo filesystem (ovvero non è necessariamente O (1) per tutto)

Answer 7

da Wikipedia:

In informatica, una lista collegata è una struttura di dati che consiste in una sequenza di set di dati tale che in ogni record è un campo che contiene un riferimento (cioè, un link) per il prossimo record nella sequenza.

Nulla in questa 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 obiettivo è semplicemente di evitare l'uso di un puntatore (o di un riferimento a un oggetto), utilizzare un vettore con un indice è un'implementazione comune. (Uno dei motivi per usare l'implementazione vettoriale/indice è la persistenza: è davvero difficile persistere puntatori/riferimenti di oggetti al di fuori dello spazio di memoria attivo.)

Answer 8

Suppongo che l'uso di riferimenti sia un imbroglio e, tecnicamente, ciò causa UB , ma qui si va:

// 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 9

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 di liste collegate

Answer 10

Wow, NO? Sicuramente voi ragazzi non siete seri?

Tutto ciò di cui un elenco collegato necessita è 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

Answer 11

lingue che non supportano alcun tipo di riferimento può ancora creare legami 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 nodi dell'array. Se anche i record non sono supportati, è possibile utilizzare spesso array paralleli.

Come esempio, si consideri il seguente record elenco collegato che utilizza array invece di puntatori:

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

Creata una matrice con un numero elevato. E punto listHead al primo elemento indice alla matrice

integer listHead; 
Entry Records[10000]; 

Controllare pagina wiki: http://en.wikipedia.org/wiki/Linked_list per i dettagli, cercare "Le liste concatenate utilizzando matrici di nodi"

Answer 12

Sì, è possibile, non è necessario utilizzare puntatori per una lista di link. È possibile collegare un elenco senza utilizzare i puntatori. È possibile allocare staticamente un array per i nodi e invece di utilizzare il puntatore successivo e precedente, è sufficiente utilizzare gli indici. È possibile farlo per risparmiare un po 'di memoria, ad esempio se l'elenco dei collegamenti non è superiore a 255, è possibile 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 problematici.

Inoltre, tenere presente che i nodi dell'elenco di collegamenti non saranno necessariamente contigui nella memoria.

Diciamo che il tuo elenco di collegamenti avrà 60000 nodi. L'allocazione di un nodo libero dall'array utilizzando una ricerca lineare dovrebbe essere inefficiente. Invece, si può semplicemente tenere il prossimo libera dell'indice nodo ogni volta:

Basta inizializzare l'array come ogni indice successiva mostra l'indice di matrice corrente + 1, e firstEmptyIndex = 0.

Nell'assegnazione un nodo libera dalla matrice , prendi il primo nodo EmptyIndex, aggiorna il primoEmptyIndex come indice successivo dell'indice dell'array corrente (non dimenticare di aggiornare l'indice successivo come Null o vuoto o altro dopo).

In caso di deallocating, aggiornare il prossimo indice del nodo deallocating come firstEmptyIndex, quindi fare FirstEmptyIndex = deallocating index del nodo.

In questo modo si crea un collegamento per allocare i nodi liberi dall'array.

Answer 13

Un possibile approccio potrebbe essere quello di utilizzare una matrice di Nodes dove ogni nodo memorizza un (array) indice del prev e nextNode. Così, il vostro Node sarebbe qualcosa di simile:

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, probabilmente si dovrà allocare dinamicamente la matrice Node, implementare alcune contabilità per ottenere e libera spazio nella matrice: per esempio una matrice bool che memorizza gli indici non occupati nell'array Node, insieme a due funzioni che lo aggiornano ogni volta che viene aggiunto o rimosso un nuovo indice Node/index (sarà frammentato in quanto i nodi non saranno sempre contigui); trovare un indice di Node nella matrice: ad esempio sottraendo l'indirizzo di Node dal primo indirizzo dell'array.

Ecco come una possibile interfaccia di una lista doppiamente collegata con la tecnica di cui sopra sarebbe simile:

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

Si potrebbe utilizzare che come un punto di riferimento e implementare qualcosa per conto proprio.

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