Additional Linked List Practice

Problem 1: "Generic" Linked Lists

Observe that our linked list implementations all have fixed carrier types. That is, the type of the values of the lists are hardcoded, e.g., to int or char. If we wanted a list of type float or char*, we would need to duplicate our entire implementation, substituting our desired carrier type throughout.

If you inspect your linked list implementations, you'll see that (in most cases) your code does not dependent on the carrier type of the list. If there existed a "generic" type, a type that could stand in for all types, you could use that as the carrier types of your list and have one implementation!

a. What type can you use as this "generic" type? (Hint: it is a pointer type!) b. If you made this change to your code, which list functions would not work as expected? How would you modify these functions to make them work with your new generic type? (Hint: this is where function pointers save the day!)

You don't need to change your code for this problem. Brainstorming is fine, but feel free to make a copy of your list implementation and attempt this refactoring for additional practice!

Problem 2: The Problem with "Generic" Linked Lists

There is a big problem with our "generic" linked list! To explore this problem, consider the following memory diagram representing a linked list l over the integers.

stack     heap
-----     ----
l [o]---->[o]--->[0][o]-->[1][o]--->[2][o]-->[3][/]

Can you create this memory layout with your "generic" linked list representation from problem 1? What is the problem you encounter when trying to do so?

Emebdded Linked Lists

Memory locality is an important property of performant code. In short, our hardware performs best when data that is related to each other, e.g., a node's next field and its data, are physically close to each other in memory. With your "generic" implementation, this is, unfortunately, no longer guaranteed.

To regain this guarantee, we need to do some fancy pointer tricks that you could only do in a low-level language like C. Ultimately, our goal is to create "nodes" that look as follows in memory:

|------------|
| Node data  |
|------------|
|            |
| Value data |
|            |
|------------|

In other words, a node is a singular chunk of memory that is the result of "glueing" together both node and "value" data. In our integer example, the "value data" is simply an int, but if we wanted to store structs in our embedded linked list, the value data may contain many fields corresponding to the fields of the struct.

Let's suppose our node data is simply pointer to the next node in the list, i.e., a singular linked list:

typedef struct embedded_node {
    struct embedded_node *next;
} embedded_node;

Where is the data connected to the node? Our embedded_node itself won't know about the data. However, we will allocate node data in such a way that the value data always follows the node data. From there, we can use pointer arithmetic to manufacture pointers to the correct locations.

For example, if we want to access the node portion of this block, we just need to get a pointer to the top of the structure.

n o---> |------------|
        | Node data  |
        |------------|
        |            |
        | Value data |
        |            |
        |------------|

In contrast, if we wish to access the value portion of the block, we need to manufacture an interior pointer to somewhere in the middle of the structure.

        |------------|
        | Node data  |
v o---> |------------|
        |            |
        | Value data |
        |            |
        |------------|

Problem 3: Constructing and Navigating Embedded Nodes

With this description in mind, write the following functions which allow us to make and access the various portions of an embedded linked list.

  • void* linked_malloc(size_t sz) allocates space for an embedded node on the heap. The size of this node is the size of value data portion of the chunk, sz, plus the size of an embedded_node. linked_malloc returns a pointer to the value data portion of the code!

    (Hint 1: what is the byte offset of the value data from the top of the block?)

    (Hint 2: normally, adding/subtracting from a pointer increments/decrements the pointer in whole type units. In other words, if p is a pointer to an int (4 bytes), then p+1 is a pointer 4 bytes offset from p, p+2 is a pointer 8 bytes offset from p, etc. What pointer type can you cast to in order to increment your malloc pointer to the start of the value data region of the block?)

  • embedded_node* get_embedded_node(void *v) returns a pointer to the node data of a chunk of memory allocated by linked_malloc. It is assumed that v is a pointer to the value data portion of this chunk.

  • void* get_value_data(embedded_node *n) returns a pointer to the value data of a chunk of memory allocated by linked_malloc. It is assumed that v is a pointer to the node data portion of this chunk.

Problem 4: Embedded Linked List Operations

With these three functions, you can now create and manipulate embedded linked lists where the node data is "embedded" alongside the value data! This variant of linked lists is both generic and memory local because the node and value data are next to each other in memory. Implement the following standard linked list functions over embedded linked lists to exercise your implementation.

In all cases, the passed void* pointer lst is assumed to be pointing to a chunk allocated by linked_malloc. The pointer is pointing to the value data portion of the chunk.

  • size_t length(void *lst) returns the length of the embedded linked list.
  • void insert_end(void *lst, void *value) inserts value onto the end of list. value is assumed to also be pointing to the value data portion of a a chunk allocated by linked_malloc.
  • void print(void *lst) prints all the values of embedded linked list lst to the console.
  • void free_embedded_list(void *lst): frees the embedded linked list. (Hint: for free to work correctly, you must give it a pointer to the top of each linked_malloc` block!)