Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Now consider the case where we need to store data in a linked list (because the number of nodes in a linked list will equal the number of data items actually stored, that is, there is no extra space like an array) but we are not allowed to heap data for each node over and over again. This may seem like a hypothetical situation to some, but it’s not a very uncommon requirement in embedded systems. Basically, in several embedded programs, memory allocation via malloc(), etc., is not allowed for a variety of reasons. One obvious reason is performance, which is expensive in terms of time complexity through malloc() allocation, because your embedded program requires determinism in most cases. Another reason could be module-specific memory management, where each module in an embedded system might manage its own memory. In short, if we need to do our own memory management, we don’t have to rely on the system-provided apis of Malloc () and free(), but we can choose to use arrays to simulate linked lists. I hope you know why we might need to use arrays to simulate linked lists. Now, let’s first look at how to do this. Suppose that the nodes in the list (that is, the underlying array) are declared as follows:

struct sllNode
{
int dataInt;

int nextIndex;
};

struct sllNode arrayLL[5].
Copy the code

If we initialize the linked list (which is actually an array), it will look like this in memory:

[(0),- 1] [(0),- 1] [(0),- 1] [(0),- 1] [(0),- 1]
0x500 0x508 0x510 0x518 0x520
Copy the code

It is important to note that all nodes of the linked list are contiguous in memory (each takes up 8 bytes), and the nextIndex of each node is set to -1. This is done (that is, -1) to indicate that each node of the list is empty so far. This list is represented by the header index 0.

Now, if the linked list were continuously updated with four elements of the data sections 4, 3, 2, and 1, it would look like this in memory. The linked list can be viewed as 0x500 -> 0x508 -> 0x510 -> 0x518.

[(1),1] [(2),2] [(3),3] [(4),2 -] [(0),- 1]
 0x500 0x508 0x510 0x518 0x520
Copy the code

The important thing to note is that the nextIndex of the last node (the fourth node) is set to -2. This is done (-2) to indicate the end of the list. In addition, the head node of the list is index 0. If we remove the second node from the list above, the concept of using arrays to simulate lists looks more interesting. In this case, the linked list will look like this in memory:

[(1),2] [(0),- 1] [(3),3] [(4),2 -] [(0),- 1]
 0x500 0x508 0x510 0x518 0x520
Copy the code

The resulting linked list is 0x500 -> 0x510 -> 0x518. Note here that even though we have removed the second node from the list, the memory of that node is still there because the underlying array is still there. But the nextIndex of the first node now points to the third node (index 2).

Hopefully, the above example gave us some idea. For simulating linked lists, we need to write our own apis like malloc() and free(), which are basically used for inserting and removing nodes. Now, this is called your own memory management. Let’s see how this is done algorithmically.

There are several ways to do this. If we take the simple approach of creating linked lists using arrays, we can use the following logic. For inserting nodes, traverse the underlying array and find the node with nextIndex -1. This means that this node is empty. Use this node as a new node. Update the data portion of this new node and set the nextIndex of this node to the current node (the header index) in the linked list. Finally, the index of this new node is used as the head index of the linked list. To visualize, let’s take an example. Assume that the linked list is as follows, where a header index of 0 indicates that the linked list is 0x500 -> 0x508 -> 0x518 -> 0x520

[(1),1] [(2),3] [(0),- 1] [(4),4] [(5),2 -]
 0x500 0x508 0x510 0x518 0x520
Copy the code

After inserting a new node with data 8, the linked list will look like the following, with a header index of 2.

[(1),1] [(2),3] [(8),0] [(4),4] [(5),2 -]
 0x500 0x508 0x510 0x518 0x520
Copy the code

So the linked list node will be located at the address 0x510 -> 0x500 -> 0x508 -> 0x518 -> 0x520

For deleting a node, we need to set the nextIndex of the node to -1 to mark the node as empty. Before we do that, however, we need to make sure that the nextIndex of the last node is correctly updated to the index of the next node of that node that we want to delete. We can see that we have completed our own memory management to create a linked list from array memory. However, this is one way to insert and remove nodes from the list. It is easy to note that finding an empty node is not very efficient in terms of time complexity. Basically, we’re searching the entire array linearly to find an empty node.

Let’s see if we can optimize it further. Basically, we can also maintain a linked list of empty nodes in the same array. In this case, the linked list will be represented by two indexes — one for the list with actual data values, that is, the nodes that have been inserted so far, and the other indexes for the list of empty nodes. By doing this, we can quickly find an empty node whenever we need to insert a new node into an existing linked list. Let’s take an example:

[(4),2] [(0),3] [(5),5] [(0),- 1] [(0),1] [(9),- 1]
 0x500 0x508 0x510 0x518 0x520 0x528
Copy the code

The linked list above, represented with two indexes (0 and 5), has two linked lists: one for actual values and one for empty nodes. Lists with actual values have nodes at addresses 0x500 -> 0x510 -> 0x528, while lists with empty nodes have nodes at addresses 0x520 -> 0x508 -> 0x518. As you can see, finding empty nodes (i.e., writing our own API like malloc()) should be faster now because we can quickly find free nodes. In real-world embedded programs, a fixed block of memory (often called a memory pool) is allocated only once by the module using malloc(). The management of the memory pool, which is basically an array, is then done by the module itself using the techniques mentioned earlier. Sometimes, there are multiple memory pools, each with nodes of different sizes. Of course, there are several other aspects of your own memory management, but we’ll leave that there. But it’s worth noting that there are several ways to further improve inserts (which require us to allocate memory ourselves) and deletes (which require us to free memory ourselves).

If we look closely, we can notice that the Heap portion of memory is basically a large byte array managed by the underlying operating system (OS). OS is providing this memory management service to programmers through malloc(), free(), and so on. Aha!!!!!

The important contents of this paper are summarized as follows:

A) Arrays represent contiguous memory. It can exist in any part of memory, be it data, stack, or heap. B) Linked lists mean discontinuous linked memory. It can exist in any part of memory, whether heap, data, or stack. C) As programmers, looking at data structures from a memory perspective can give us better insight into selecting specific data structures and even designing new ones. For example, we might create a linked list array and so on.

🥇 past quality articles

Teach you make a small game gobang in Java Single AI minesweeping game using the python list of singly linked list data structure is introduced | first set of singly linked list data structure in the linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure in the fourth set Singly linked list data structure to delete a given location of nodes in the list | 5 sets of taught you how to use Python snake game Taught you how to use the Java AWT to create a simple calculator using HTML, CSS, and JavaScript analog clock using cool dark themes HTML, CSS, JS, and apis to make a great weather Web application

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.