DSA Linked Lists in Memory
Computer Memory
It is necessary to have a rudimentary understanding of computer memory in order to describe linked lists and how they vary from arrays.
The storage that your application uses while it is operating is called computer memory. Your linked lists, arrays, and variables are kept here.
Â
Variables in Memory
Assume for the moment that we wish to keep the number “17” in a variable called myNumber. To keep things simple, we’ll assume that the integer is stored as two bytes (16 bits), and that myNumber location in memory is 0x7F30.
The location of the first of the two bytes of memory, where the integer value of myNumber is kept, is actually 0x7F30. Since integers on this particular computer are two bytes, the computer knows that in order to read an integer value, it must read both the first and the second byte when it reaches to 0x7F30.
The memory location of the variable myNumber = 17 is depicted in the image below.
The aforementioned example demonstrates how an integer value is saved on the straightforward yet well-liked Arduino Uno microcontroller. This microcontroller employs two bytes for memory addresses and two bytes for integers. It has an 8-bit architecture and a 16-bit address bus. In contrast, 32 or 64 bits are used by smartphones and personal computers for addresses and integers, but the fundamental principles of memory management remain the same.
Arrays in Memory
An understanding of array storage in memory is a prerequisite for comprehending linked lists.
An array’s components are kept adjacent to one another in memory. This indicates that each element is kept directly following the one before it.
The memory storage of an array of integers myArray = [3,5,13,2] is depicted in the graphic below. Just to get the idea, we employ a simple type of memory here, with two bytes for each integer, just like in the previous example.
Since the computer only knows the address of the first byte in myArray, it must start at 0x7F28 and skip the first two numbers in order to reach the third element with code myArray[2]. Knowing that an integer is stored in two bytes, the computer begins reading value 13 at location 0x7F32 by jumping 2×2 bytes forward from 0x7F28.
Every subsequent member in an array must be either shifted down to replace the removed element or pushed up to make room for the new element when it is added or removed. These shifting processes take a lot of time and can lead to issues, for instance, in real-time systems.
The following graphic illustrates how the removal of an array element shifts the elements.
If you are writing in C and have to move other elements explicitly while adding or removing an element, you also need to consider manipulating arrays. This does not occur in the background in C.
To add more components later, you must ensure that you have allotted adequate space for the array in C at the outset.
This earlier DSA teaching page contains more information regarding arrays.
Linked Lists in Memory
A linked list can be made in place of storing a set of data as an array.
Linked lists find use in numerous contexts, including dynamic data storage, the development of stack and queue systems, and graph representation, to name a few.
Nodes holding some type of data and at least one pointer, or link, to other nodes make up a linked list.
One major advantage of linked lists is that nodes can be stored anywhere in memory that has empty space; unlike arrays, which need nodes to be stored consecutively after one another, linked lists do not require this. The fact that the remaining nodes in the list do not need to be moved when new or removed from the list is another great feature of linked lists.
The following picture illustrates the process of storing a linked list in memory. Each of the four nodes in the linked list—values 3, 5, 13, and 2—has a pointer pointing to the node after it in the list.
Four bytes are used by each node. An integer value takes up two bytes, and the location of the node after it in the list also takes up two bytes. As previously stated, the computer’s design determines how many bytes are required to store addresses and integers. Similar to the array example before it, this one is compatible with a straightforward 8-bit microcontroller architecture.
We will present nodes in a linked list in a simpler manner, less tied to their memory location, like in the following figure, to make it easier to see how the nodes relate to each other:
Using this new visualization, the same four nodes from the previous example appear as follows:
As you can see, the “Head” is the initial node in a linked list, and the “Tail” is the last node.
The nodes in a linked list are not arranged in chronological order in memory, in contrast to arrays. This is good since it means that other nodes do not need to be moved in order to add or remove a node.
One drawback of linked lists is that nodes cannot be accessed directly, unlike arrays, where we may write myArray[5] to get a node, for example. In a linked list, in order to go to node number 5, we must begin at the first node, referred to as “head,” use its pointer to get to the next node, and continue in this manner until we reach node number 5. We achieve this by keeping track of the number of nodes we have visited.
Gaining knowledge about linked lists improves our comprehension of ideas like pointers and memory allocation.
Before learning about more complicated data structures like trees and graphs, which can be implemented using linked lists, it’s also crucial to comprehend linked lists.
Memory in Modern Computers
In order to make things straightforward and understandable, we have utilized the memory of an 8-bit microcontroller as an example thus far on this page.
The basis of memory in modern computers is the same as that of memory in an 8-bit microcontroller; the only differences are that more memory is used to store memory addresses and more memory is used to store integers.
The code that follows tells us how big an integer and how big of a memory address are on the server that these examples are being run on.
Example
Code written in C:
#include <stdio.h>
int main() {
int myVal = 13;
printf("Value of integer 'myVal': %d\n", myVal);
printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
printf("Address to 'myVal': %p\n", &myVal);
printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes
return 0;
}
Because Java and Python operate at an abstraction level higher than specific/direct memory allocation, the code example above is only executable in C.
Linked List Implementation in C
Now let’s put this prior linked list into practice:
To demonstrate a practical example of how linked lists are kept in memory, let’s put this linked list into C.
The code below creates a node struct, or class, to represent what a node is, which is a node that includes data and a pointer to the next node. This is done after adding the libraries.
The createNode() function sets aside memory for a new node, populates the node’s data section with an integer that is supplied as an argument, and then returns the memory address or pointer to the newly created node.
The value of each node in the linked list is printed using the printList() function.
Four nodes are formed, connected, and printed inside the main() function before the memory is released. In order to prevent memory leaks, it is best practice to release memory after we have finished utilizing it. Memory leaks occur when used memory is not released, progressively consuming more and more memory.
Example
A basic linked list in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void printList(Node* node) {
while (node) {
printf("%d -> ", node->data);
node = node->next;
}
printf("null\n");
}
int main() {
Node* node1 = createNode(3);
Node* node2 = createNode(5);
Node* node3 = createNode(13);
Node* node4 = createNode(2);
node1->next = node2;
node2->next = node3;
node3->next = node4;
printList(node1);
// Free the memory
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}
The printList() method uses the “next” pointers to traverse the linked list, printing the linked list in the code above. This process is known as “traversing” or “traversal” the linked list. The Linked Lists Oprations page has further information about linked list traversal and other linked list operations.
Linked List Implementation in Python and Java
Now, we’ll use Python and Java to implement the identical linked list.
The Node class in the Python code below illustrates what a node is: it is a collection of data and a link to the node after it.
Four nodes are created using the Node class, joined together, and printed at the conclusion.
As you can see, the Python code is significantly shorter than the C code, and it could be preferable if all you want to learn about is linked lists as a concept rather than how they are kept in memory.
There are several similarities between the Python and Java code. To view the Java code, click the “Run Example” button below and select the “Java” tab.
Example
A basic linked list in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
