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.

Could anyone give an overview of how list structures which are composed of a head and a tail which references the rest of the list i.e linked list are represented in memory of the computer? Does the computer make use of cpu registers to hold the pointers the head and rest of the list?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

Could anyone give an overview of how list structures which are composed of a head and a tail which references the rest of the list i.e linked list are represented in memory of the computer?

In a naive implementation, each node is allocated separately, so the nodes would be spread more or less randomly through the heap memory, wherever the memory allocator found some free space.

In practice, implementations typically try to improve cache locality by allocating space in bulk for a reasonable number of nodes at a time and keep track of that preallocated space.

Does the computer make use of cpu registers to hold the pointers the head and rest of the list?

Any good compiler, when compiling code that iterates over the list, will almost certainly produce machine code that does this, but that's implementation detail that has nothing to do with the concept of the data structure.

share|improve this answer
    
+1: I think it should be noted that the first block of memory is stored relative to the base address of the compiled program being run, and it is allocated with enough space to store the data type and the accompanying addresses it needs to traverse. –  Joel Etherton Jun 6 '12 at 14:04
    
The optimization you describe is sometimes called an unrolled linked list. It indeed improves the cache behavior and memory consumption, but makes most operations (along with the interface, I fear) more complicated and increases the constants (e.g. need to copy some elements when inserting or removing). So it's a double-edged sword, and not always done even in highly optimized programs like the Lua interpreter. –  delnan Jun 6 '12 at 14:10
    
@delnan not if you allow the nodes to be out of order (and just keep a free node linked stack using the next pointer alread baked in the nodes) –  ratchet freak Jun 6 '12 at 14:14
    
@ratchetfreak I may have misunderstand the optimization. I assumed it's about storing multiple values in each node. Now I'm not so sure, are you simply talking about allocating the nodes close to each other in an arena? That's indeed more viable, though probably less so (you still pay a pointer or two per value, and cache misses may still occur unless you know your allocations very well). –  delnan Jun 6 '12 at 15:08
    
@deinan: no what I meant was indeed just allocating memory for, say, 20 nodes and using that for any new nodes until it runs out, at which point you allocate another 20. When you remove nodes, you get gaps and can either deallocate that memory or reuse it via the method indicated by ratchet freak. The point is not to prevent all cache misses, just to reduce them a lot. –  Michael Borgwardt Jun 6 '12 at 15:45

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.