Thinking About Linked Lists and Process Memory Layout
I've been thinking about process memory layout and how linked lists live in memory. I think its a good idea to think about this, since it's another way of thinking about how linked lists work, and it helps me remember how to make them.
When memory is allocated to a process, the process sees it as one solid chunk, and it sees it as starting at zero. In reality, the physical memory that is allocated to the process is chunked and each chunk can be in different physical locations. Within the memory allocated to a process, we can see two major sections: data and text. Within the data section, we can see two subsections: the heap, and the stack.
Whenever a function in a process gets called, that function gets a section of memory on the stack. This is where local variables, the function's input parameters, and the return address for the next instruction to execute (the function caller's next instruction) get placed. Speaking in terms of C, whenever a function calls malloc, a section of memory in the heap is set aside for that call. The stack grows from high memory address to low, and the heap grows from low memory address to high, so they grow towards each other. How does the concept of process memory layout that we've been talking about relate to linked lists? We can remember how to make a linked list by thinking about those concepts.
Before a linked list is born, a pointer to a node data type first points to NULL. This pointer exists on the stack, and there is nothing related to linked list data on the heap. When we create the first node, that's when we request that memory be allocated for it on the heap, and the pointer can now have the address of the section of memory in the heap when this request for memory is granted.
Of course, the node that was just created will need to have a data member that points to NULL, which represents the next node on the list. We can keep requesting for memory on the heap for our linked list, but this can't go on forever.
When we no longer need the linked list, we remember the process memory layout concept, and we can then remember that we need to clean up the heap and free the memory that we've just allocated for the nodes of the linked list. So, our cleanup routine would just require the pointer to the start of the linked list, and it would just traverse the list and free each node. Remember that if a node consists of pointers to memory locations on the heap, we need to free those individually and then free the node.
Viewing linked lists in terms of how the data structure uses the process stack and heap really helps me remember how it should be coded.
Sources:
1."Using GNU's GDB Debugger: Memory Layout and The Stack". Salzman, P.
http://dirac.org/linux/gdb/02a-Memory_Layout_And_The_Stack.php