Linked List in Memory

Computer Memory

Computer memory is the space where your program stores and manipulates data while it’s running. It’s like the workspace where your variables, arrays, and linked lists reside during the execution of your program.

Arrays in Memory

Arrays store elements consecutively in memory, meaning each element resides immediately after the preceding one. Arrays in memory represent contiguous blocks of memory used to store elements of the same data type.

Linked Lists in Memory

Linked lists offer advantages over arrays in various applications, including dynamic data storage, implementing stacks and queues, or representing graphs.

In a linked list, nodes contain data and pointers to other nodes, enabling flexible data organization.

One significant advantage of linked lists is their non-contiguous memory allocation. Unlike arrays, where elements must be stored consecutively, linked list nodes can be placed in any available memory space. This flexibility allows efficient use of memory without the need for contiguous blocks.

Additionally, linked lists facilitate efficient insertion and deletion operations. When adding or removing nodes, there’s no need to shift other nodes as in arrays. Each node simply adjusts its pointer to maintain connectivity within the list.

In summary, linked lists offer flexibility in memory allocation and efficient operations, making them valuable in a variety of scenarios where dynamic data structures are required.

Linked list implementation in c

In the provided code, we create a linked list in C to demonstrate how linked lists are structured in memory.

We define a struct Node that represents each node in the linked list. Each node contains an integer data element and a pointer to the next node.

The createNode() function allocates memory for a new node, initializes its data field with the provided integer value, and returns a pointer to the newly created node.

The printList() function traverses the linked list and prints the data elements of each node.

Inside the main() function, four nodes are created, linked together, and their values are printed. After using the linked list, memory is freed using the free() function to avoid memory leaks.

Memory leaks occur when memory allocated dynamically is not deallocated after use, gradually consuming more memory. It’s essential to free dynamically allocated memory when it’s no longer needed to prevent memory leaks and ensure efficient memory usage.

#include <stdio.h>
#include <stdlib.h>

// Define the Node struct
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create a new 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;
}

// Print the linked list
void printList(Node* node) {
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    // Explicitly creating and connecting nodes
    Node* node1 = createNode(7);
    Node* node2 = createNode(4);
    Node* node3 = createNode(3);
    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;
}

Output:

7 -> 4 -> 3 -> 2 -> null

Code Explanation

1. Define the Node Structure

typedef struct Node {
    int data;
    struct Node* next;
} Node;

• Purpose: This defines the structure of a node in the linked list.
• Fields:
  • int data: Stores the value of the node.
  • struct Node* next: A pointer to the next node in the linked list.
• typedef: The typedef keyword is used to create an alias Node for struct Node, making it easier to use.

2. Create a New 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;
}

• Purpose: This function dynamically allocates memory for a new node and initializes it.
• Steps:
  1. Allocate memory for a new node using malloc.
  2. Check if memory allocation was successful. If not, print an error message and exit the program.
  3. Set the data field of the node to the provided value.
  4. Set the next pointer to NULL (indicating the end of the list).
  5. Return the newly created node.

3. Print the Linked List

void printList(Node* node) {
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

• Purpose: This function traverses the linked list and prints the value of each node.
• Steps:
  1. Start from the given node (usually the head of the list).
  2. Use a while loop to iterate through the list until the current node becomes NULL.
  3. Print the data of the current node.
  4. Move to the next node by updating the pointer (node = node->next).
  5. After the loop ends, print null to indicate the end of the list.

4. Main Function

int main() {
    // Explicitly creating and connecting nodes
    Node* node1 = createNode(7);
    Node* node2 = createNode(4);
    Node* node3 = createNode(3);
    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;
}

• Purpose: The main function creates a linked list, connects the nodes, prints the list, and frees the allocated memory.
• Steps:
  1. Create Nodes:
     • Four nodes are created using the createNode function:
       • node1 with data 7
       • node2 with data 4
       • node3 with data 3
       • node4 with data 2
  2. Connect Nodes:
     • The next pointer of each node is set to connect them in the following order:
       • node1 -> node2 -> node3 -> node4 -> null
  3. Print the Linked List:
     • The printList function is called with node1 (the head of the list) to print the entire list.
  4. Free Memory:
     • The memory allocated for each node is freed using free to avoid memory leaks.
  5. Return 0:
     • The main function returns 0, indicating successful execution.

How the Linked List Works

1. Creation:
   • Nodes are created and initialized with data.
   • The next pointer of each node is set to connect them in the desired order.
2. Traversal:
   • Starting from the head (node1), the next pointer is followed to access each node in sequence.
3. Termination:
   • The last node’s next pointer is set to NULL to indicate the end of the list.