Como os programadores implementaram as idéias da Lista vinculada antes do paradigma orientado a objetos?

Lista vinculada não tem nada a ver com OOP, na verdade eles antecedem o OOP por um pouco. Lista interligada é implementada simplesmente por ter uma estrutura recursiva, isso é, na minha opinião, conceitualmente mais fácil de entender em assembly - você aloca alguma memória, e os primeiros bytes dessa memória servem como um ponteiro para o próximo / anterior. Na montagem você não precisa se preocupar com o "tipo" e apenas pensar nele como outro ponteiro, então o fato de ser recursivo não é algo que você precisa pensar - você não precisa pensar em como algo pode se referir a si mesmo em sua definição.

Eles usaram, por exemplo, em C, struct para simular um nó; e ponteiros para ligar os nós

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).

O que você viu que não é orientado a objetos? Se as únicas coisas que você viu são OO, então não é surpresa que as únicas implementações de estruturas de dados simples que você viu sejam OO.

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

As listas vinculadas antecedem a programação OO por muitas décadas.

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

Na década de 1950, a linguagem de programação Lisp foi implementada no IBM 704. A estrutura de dados fundamental do Lisp é a cons cell , que é um agrupamento de dois valores. O tamanho da palavra da máquina do IBM 704 era de 36 bits e havia instruções especiais, CAR e CDR, que extrairiam 15 valores de bit de uma palavra de 36 bits. O valor armazenado nos bits do CAR era o cabeçalho da lista e o valor armazenado no CDR era a cauda, assim, dessa forma, uma célula de cons poderia ser usada como um nó em uma lista vinculada.

Para uma discussão mais detalhada de como as listas vinculadas foram implementadas no IBM 704 nos anos 50, consulte o link .

Bem, você sempre pode traduzir o código OOP de volta para código não-OOP (ou melhor, código que não seja OOP). Na verdade, você pode codificar de uma maneira OOP em qualquer idioma, mas não será tão conveniente quanto as linguagens OOP.

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

torna-se, no primeiro passo:

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

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

ou, se você não tiver structs:

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

Eu não sei se parecia com isso, mas muito bem poderia.

As listas interligadas existem há pelo menos tanto tempo quanto as do sistema operacional e bem antes da HLL foram inventadas. Eu só posso adivinhar a importância que Knuth colocou sobre eles, mas eles foram o primeiro conceito que ele discutiu em A Arte da Programação de Computadores (Vol 1, Capítulo 2). Se você realmente quer saber a resposta para "Como as listas de links foram implementadas antes que o paradigma orientado a objetos surgisse?" Eu sugiro comprar pelo menos o volume 1 do TAOCP. Todo o trabalho é inestimável.

(FWIW - eu não trabalho para o Dr. Knuth, ou seu editor)

a resposta do jmoreno está correta.

Mal, principalmente.

Era bastante comum ver código desleixado e propenso a erros como este:

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

\ ...

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

remove , insert , etc. foram usadas em alguns casos, mas porque geralmente havia uma profusão justa de diferentes estruturas de lista, geralmente não eram funções de todas elas, ou uma única classe com void* data element ou union 'd conjunto de tipos de dados.

Em muitos casos, a estrutura da lista foi injetada na classe na lista, então você teria algo como:

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

Em suma, enquanto qualquer objeto orientado poderia ser implementado de forma limpa e orientada a objetos, na prática muitas listas foram implementadas em um ad hoc e erro propenso em C e em linguagens similares.