In che modo i programmatori hanno implementato le idee delle liste collegate prima del paradigma orientato agli oggetti?

L'elenco collegato non ha nulla a che fare con OOP, anzi anticipano di molto l'OOP. La lista collegata è implementata semplicemente avendo una struttura ricorsiva, questo è a mio avviso concettualmente più facile da capire in assembly - allocate della memoria, ei primi byte di quella memoria servono da puntatore al prossimo / precedente. In assemblea non devi preoccuparti del "tipo" e pensarlo come un altro puntatore, quindi il fatto che sia ricorsivo non è qualcosa a cui devi pensare - non devi pensare a come qualcosa può riferirsi a se stesso nella sua definizione.

Hanno usato, per esempio in C, struct per simulare un nodo; e puntatori per collegare i nodi

Linked lists, as far as I have seen, are largely implemented using object-oriented ideas. (having an object that holds some information and the address of the next link).

Che cosa hai visto che non è orientato agli oggetti? Se le uniche cose che hai visto sono OO, non sorprende che le uniche implementazioni di strutture dati semplici che hai visto siano OO.

Were they only invented(?) once the OOP was developed?

Gli elenchi collegati precedono la programmazione OO di molti decenni.

How were Linked-lists implemented before the object-oriented paradigm came out?

Negli anni '50 il linguaggio di programmazione Lisp è stato implementato su IBM 704. La struttura dei dati fondamentali di Lisp è la cons cell , che è un raggruppamento di due valori. La dimensione della parola della macchina dell'IBM 704 era di 36 bit e c'erano istruzioni speciali, CAR e CDR che estraevano i valori di 15 bit da una parola a 36 bit. Il valore memorizzato nei bit CAR era il capo dell'elenco e il valore memorizzato nel CDR era la coda, quindi in questo modo una cella CONS poteva essere utilizzata come nodo in una lista collegata.

Per una discussione più dettagliata su come sono stati implementati gli elenchi collegati su IBM 704 negli anni '50, vedi link .

Bene, puoi sempre tradurre il codice OOP in codice non-OOP (o piuttosto, codice non-OOP). In realtà puoi codificare in modo OOP in qualsiasi lingua, ma non sarà così conveniente come le lingue OOP.

class Node {
    int data;
    Node *next, *prev;
    public:
    void remove() { // example method
        next->prev = prev;
        prev->next = next;
    }
};

diventa, nel primo passaggio:

struct Node {
    int data;
    Node *next, *prev;
};

void remove(Node* self) {
    self->next->prev = prev;
    self->prev->next = next;
}

o, se non hai le strutture:

void remove(int *data, int **nextdata, int **prevdata) { // etc.

Non so se è sembrato così, ma potrebbe benissimo.

Gli elenchi collegati sono stati in circolazione almeno per il tempo di OS e ben prima che fossero inventati gli HLL. Posso solo indovinare quale importanza Knuth ha posto su di loro, ma sono stati il primo concetto che ha discusso in The Art of Computer Programming (Vol 1, Capitolo 2). Se vuoi veramente sapere la risposta a, "Come sono state implementate le liste di collegamenti prima che venisse fuori il paradigma orientato agli oggetti?" Suggerirei di acquistare almeno il volume 1 di TAOCP. L'intero lavoro è inestimabile.

(FWIW - Non lavoro per il Dr. Knuth, o il suo editore)

La risposta di jmoreno è accurata.

Male, soprattutto.

Era piuttosto comune vedere un codice sciatto e soggetto a errori come questo:

struct Node {
  int data;
  Node *next;
  Node* prev;
};

\ ...

Node* pWotsit = findBestCheese(pHead);
pWotsit->pNext->pPrev = pWotsit->pPrev;
pWotsit->pPrev->pNext = pWotsit->pNext;

remove , insert , ecc. sono state utilizzate in alcuni casi ma poiché generalmente c'era una buona profusione di diverse strutture di elenchi, in genere le funzioni non erano tutte per tutti o una singola classe con void* data element o union 'd set di tipi di dati.

In molti casi la struttura delle liste è stata inserita nella classe nell'elenco, quindi è possibile ottenere qualcosa come:

struct Cat
{
  int breed;
  int age;
  // ... etc.
  Cat* pNext;
  Cat* pPrev;
};

In breve, mentre tutto potrebbe orientato agli oggetti potrebbe essere implementato in modo pulito, orientato agli oggetti, in pratica molte liste sono state implementate in un ad hoc e errore modo incline in C e lingue simili.