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). How were Linked-lists implemented before the object-oriented paradigm came out? Were they only invented(?) once the OOP was developed?

  • 5
    Linked lists predate not only OOP, but also structured programming and C. The very first LISP implementation in the fifties probably already used them, or if not, one that followed soon after did.
    – user7043
    Apr 26, 2014 at 23:48
  • 55
    The more I think about it, the stranger it gets that you seem to think grouping two values together was pioneered by OOP. This is what Java-only curricula do to the world ;-)
    – user7043
    Apr 26, 2014 at 23:57
  • 10
    How were Linked-lists implemented before the object-oriented paradigm came out? -- Using raw pointers to actual memory addresses. Apr 27, 2014 at 0:40
  • 8
    OOP is probably the worst possible way to deal with polymorphic data structures. Stepanov nailed it down: stlport.org/resources/StepanovUSA.html
    – SK-logic
    Apr 27, 2014 at 10:11
  • 4
    @delnan: See en.wikipedia.org/wiki/CAR_and_CDR. Apr 28, 2014 at 7:10

7 Answers 7


Linked list have nothing to do with OOP, in fact they predate OOP by quite a bit. Linked list are implemented simply by having a recursive structure, this is in my opinion conceptually easiest to understand in assembly -- you allocate some memory, and the first bytes of that memory serve as a pointer to the next/previous. In assembly you don't have to worry about the "type" and just think of it as another pointer, so the fact that it is recursive is not something you need to think about -- you don't have to think about how something can refer to itself in its definition.


They used, for example in C, struct for simulating a node; and pointers to link the nodes


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

What have you seen that is not object-oriented? If the only things you've seen are OO then it is not surprising that the only implementations of simple data structures you've seen are OO.

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

Linked lists predate OO programming by many decades.

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

In the 1950's the Lisp programming language was implemented on the IBM 704. The fundamental data structure of Lisp is the cons cell, which is a grouping of two values. The machine word size of the IBM 704 was 36 bits and there were special instructions, CAR and CDR that would extract 15 bit values from a 36 bit word. The value stored in the CAR bits was the head of the list and the value stored in CDR was the tail, so in that way a cons cell could be used as a node in a linked list.

For a more detailed discussion of how linked lists were implemented on the IBM 704 in the 1950s, see http://en.wikipedia.org/wiki/CAR_and_CDR.


Well you can always translate OOP code back into non-OOP code (or rather, non OOP-looking code). Actually you can code in an OOP way in any language, but it will not be as convenient as OOP languages.

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

becomes, in the first step:

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

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

or, if you don't have structs:

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

I don't know if it did look like this, but it very well could.

  • 1
    "Actually you can code in an OOP way in any language" except polymorphism, right? Unless you give every struct a vtable, but then you just reimplement OOP.
    – wchargin
    Apr 27, 2014 at 19:18

Linked lists have been around at least as long as OS's and well before HLL's were invented. I can only guess what importance Knuth placed on them, but they were the first concept he discussed in The Art of Computer Programming (Vol 1, Chapter 2). If you really want to know the answer to, "How were Linked-lists implemented before the object-oriented paradigm came out?" I'd suggest purchasing at least volume 1 of TAOCP. The entire work is invaluable.

(FWIW - I don't work for Dr. Knuth, or his publisher)

jmoreno's answer is accurate.


My Data Structures course back in the 70s was taught with Fortran IV as the implementation language. Fortran has a paucity of data structures built into the language so a linked list was built by allocating a large array of ints and then mapping meaning to sub-sets of the array. So if the array was named A then A(n) held the array index for the node's data and A(n+1) held the index for the next element in the list. Doubly linked lists were done by extending this idea with A(n) still pointing to the data, A(n+1) held the back pointer (i.e. the subscript of the array), and A(n+2) was the index of the next node. Similarly you could define trees, graphs, and even dictionaries.

In the era of punched cards for programs, the program to implement one of these data structures the thickness of the program deck could get to a significant percent of a box of cards. Therefore most programs developed for practical considerations did not use such "advanced" structures.


Badly, mostly.

It was pretty common to see sloppy, error-prone code like this:

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. functions were used in some cases but because there was generally a fair profusion of different list structs there generally ended not being functions for all of them, or a single class with a void* data element or a union'd set of datatypes.

In many cases the list structure was injected into the class in the list, so you'd get something like:

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

In short, while anything object orientated could be implemented in a clean, object-orientated fashion, in practice a lot of lists were implemented in an ad hoc and error prone manner in C and similar languages.

  • 13
    As if using an object oriented language somehow prevented bad code... (Also, intrusive linked lists, which you deride near the end, have some very real advantages, both semantically and performance-wise.)
    – user7043
    Apr 27, 2014 at 11:35
  • It doesn't prevent bad code but it does help with things like this. Object orientation is an inherently cleaner way to do things, and having a language which expresses it as a natural paradigm helps with that. Apr 27, 2014 at 16:50
  • Also, I didn't deride injected linked lists, I merely pointed out that they were common. Apr 27, 2014 at 18:08
  • 3
    It seems like what you're saying C misses is generic programming, not OOP. Some non-OOP languages (e.g. Haskell) can deal with this as well as any modern OOP language.
    – svick
    Apr 28, 2014 at 17:03
  • It's not a comment on C, it's a comment on how lists were implemented before Object Orientation became common in the workplace. I can't comment on how programmers were doing in Haskell, etc. since I've never been paid to work in them. Apr 28, 2014 at 17:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.