5

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?

  • 3
    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 '14 at 23:48
  • 48
    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 '14 at 23:57
  • 9
    How were Linked-lists implemented before the object-oriented paradigm came out? -- Using raw pointers to actual memory addresses. – Robert Harvey Apr 27 '14 at 0:40
  • 7
    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 '14 at 10:11
  • 3
    @delnan: See en.wikipedia.org/wiki/CAR_and_CDR. – Eric Lippert Apr 28 '14 at 7:10
27

Linked list have nothing to do with OOP, on 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.

6

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

4

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;
    public:
    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 '14 at 19:18
-14

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 '14 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. – Jack Aidley Apr 27 '14 at 16:50
  • Also, I didn't deride injected linked lists, I merely pointed out that they were common. – Jack Aidley Apr 27 '14 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 '14 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. – Jack Aidley Apr 28 '14 at 17:21
2

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.

6

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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