current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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?

share|improve this question
2  
Searching google for linked list in c . Or linked list in pascal. or fortran or MIPS assembly. –  MichaelT Apr 26 at 23:43
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. –  delnan Apr 26 at 23:48
43  
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 ;-) –  delnan Apr 26 at 23:57
8  
How were Linked-lists implemented before the object-oriented paradigm came out? -- Using raw pointers to actual memory addresses. –  Robert Harvey Apr 27 at 0:40
6  
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 at 10:11
show 7 more comments

6 Answers

up vote 25 down vote accepted

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.

share|improve this answer
add comment
up vote 6 down vote

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

share|improve this answer
add comment
up vote 4 down vote

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.

share|improve this answer
    
"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 at 19:18
add comment
up vote 4 down vote

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.

share|improve this answer
add comment
up vote 1 down vote

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.

share|improve this answer
add comment
up vote -12 down vote

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.

share|improve this answer
12  
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.) –  delnan Apr 27 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 at 16:50
    
Also, I didn't deride injected linked lists, I merely pointed out that they were common. –  Jack Aidley Apr 27 at 18:08
2  
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 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 at 17:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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