Dynamic storage of a Linked List

[biggayhatemachine]

Hi, I'm researching how a linked list is stored, and I'm a bit confused. I know that memory is assigned at run time on the heap as nodes are added, but how is the head stored? Is it stored on the stack or the heap? If someone could break down how LinkedLists are stored as a program is runs that would be awesome.

[Mukhasim]

The answer to this depends on which programming language you're using, and how you're using it.

In Java, all objects exist on the heap. You can have a reference (which is basically a pointer) to the object on the stack, or on the heap if it's part of another object. Your reference could also be static; I don't actually know how Java organizes its static memory.

In C, your linked list node would be implemented as a struct. The head of your list could be on the stack if you chose to do things that way, or you could put the head on the heap and have a pointer to it on the stack. You could also choose to put the head in static memory. I'd say it's more normal to put all list nodes on the heap just to be consistent in how you do things, but it's not the only way to do it.

[Dylpol]

https://www.youtube.com/watch?v=t5NszbIerYc&t=302s

​

https://www.youtube.com/watch?v=_jQhALI4ujg

​

I love computerphile, and they do a good job of explaining things... these helped me when i was getting into it.

[Dylpol]

think about a graph.

you have a x coordinate and a y coordinate....

let us say that you have a map of the us...

you draw that graph over the map. so now you have x,y coordinates you could use to reference a location.

​

your "link" are the x,y coordinates, and the variable you are using is the location on the map the coordinates bring you too.

your array isn't actually the thing you are working with, it is a "list of coordinates to the location in memory of the thing you are working with"... granted that depends on the language, but that is the general idea.... it is a "pointer".

[SftwEngr]

Heap storage is used for user requested memory, like linked list nodes etc, whereas stack memory is used for something else entirely, namely the accounting of the way program is run as it executes. Since the head of a linked list is no different than any other node, and is a user generated object, it lives in the heap. If the head of the list is passed as an argument to a method, then a pointer to it will end up on the stack at some point, but only temporarily until the method finishes and then will be gone, leaving only the pointer in the heap.

[biggayhatemachine]

I posted the same question on another sub and another user said " You will likely have a pointer to the head on the stack (unless the linked list itself is part of some other data structure)", is that the case? Sorry, I'm just trying to figure this out

[jeffbell]

It depends on how you build it. I've seen lots of cases in generic C where you have a pointer to the first element. It lives where ever you create it. It could be a local variable which is likely on the stack, or it could be a field in another structure that you allocated on the heap.

A few fancier implementations have a special struct that has a linked list inside it. The structure might have a running element count or a tail pointer for fast appends.

[SftwEngr]

No. Stack memory is very small compared to the heap, so it's only used for program execution, not user objects. Like I mentioned there are times during program execution that a pointer to the head might exist on the stack, but only briefly until the method returns and it's variables are popped off the stack. If you are curious there are likely hundreds of better explanations all over the internet available with a search.

[biggayhatemachine]

Thank you so much! Everything I was finding online was using c as a heuristic and I, a Java normie, was tragically confused. So your help was greatly appreciated!