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 1 down vote favorite

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 14 hours ago
    
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 14 hours ago
25  
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 14 hours ago
    
haha well I could only think of it being use in an objective environment, I didn't know if it had been pioneered by OOP, that was part of the question. –  Snappawapa 13 hours ago
5  
How were Linked-lists implemented before the object-oriented paradigm came out? -- Using raw pointers to actual memory addresses. –  Robert Harvey 13 hours ago
show 5 more comments

4 Answers

up vote 14 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 5 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 2 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
add comment
up vote -4 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
3  
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 2 hours ago
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.