C Doubly-Linked List Rough-In

2024-11-15

Nov 15, 2024

When thinking about creating data in C, I create pictures of byte arrays (RAM) in my mind. I’ve tried to capture some of what I “see”. When first learning C, I drew such diagrams on paper, but, learned to intuit this stuff.

The following is incomplete and needs to be further detailed-in, but, for this overview, a rough-in is “good enough”.

Struct

A struct is just a template.

The above typedef defines a new type called Node based on a struct def called _Node.

Abstract

A pointer called Dll (for Doubly-linked-list) is an index into RAM.

The memory defined by the struct is contiguous, but, the actual bytes that make up the string (yellow) can be anywhere in memory, not necessarily contiguous as shown here.

Here, I’ve shown a doubly-linked list consisting of two Nodes, allocated in the heap. The struct portion could be allocated as a locals - on the stack.

When you allocate bytes in the heap, you have to worry about memory management (garbage collection). When you allocate bytes as locals on the stack, the hardware does automatic, stack-oriented, garbage collection.

More Concrete

In this example, we have a pointer called Dll, allocated in local memory (stack). The heap-allocated Nodes and associated char* data is allocated on the heap. The heap contains more bytes than needed for this example, shown here as uncoloured.

Note that this is just a rough sketch of what I am thinking when I think about data in RAM. There are problems with these sketches. For example “00000000” is probably a bad choice for the first struct. We probably want to reserve “00000000” to denote NIL (no pointer) and NUL (end of string, also written as ‘\0’). Furthermore, the pointer Dll is, also, in RAM somewhere, maybe far in front of the bytes shown above or far behind. Such details need to be handled to make the code and these diagrams viable.

Programming Simplicity

Discussion about this post

Ready for more?