Linked List: Representation of linked list in memory

Definition

A linked list is a dynamic data structure made up of nodes, where each node contains two parts: one part stores the data, and the other part stores the address of the next node in the sequence. The first node is called the head node, and the last node points to NULL, indicating the end of the list.

Main Content

1. Node Structure in Memory

• Each node of a linked list is usually represented using a record or structure containing at least two fields:
• data: stores the actual value
• next: stores the memory address of the next node
• In a singly linked list, each node points only to the next node, forming a one-way chain.

Example node representation:

+-------+--------+
| data  | next   |
+-------+--------+
| 10    | 1040   |
+-------+--------+

Here, 10 is the data part, and 1040 is the address of the next node.

A more complete node structure in C-like notation:

struct node {
    int data;
    struct node *next;
};

This structure shows that a node is not just a value; it is a combination of stored information and a pointer that connects it to another memory location.

2. Memory Layout of a Linked List

• Linked list nodes are allocated in non-contiguous memory locations, meaning they do not need to be placed one after another in memory.
• Each node stores the address of the next node, so the list can be traversed even though the nodes are scattered.

Example memory representation:

Head
  |
  v
[1000 | 1020] -> [1020 | 1055] -> [1055 | 1200] -> [1200 | NULL]

In this example:

• The first node is stored at address 1000
• It points to the second node at address 1020
• The second node points to the third node at address 1055
• The third node points to the fourth node at address 1200
• The last node points to NULL

This representation demonstrates that a linked list is not dependent on contiguous memory like arrays. The list exists logically as a sequence, even if physically its nodes are separate.

A table view of the same structure:

3. Types of Linked List Representation

Singly linked list

• each node contains one link to the next node only.

Doubly linked list

• each node contains two links:
• one link to the next node
• one link to the previous node

Circular linked list

• the last node does not point to NULL; instead, it points back to the first node, forming a circle.

Singly linked list memory view:

Head -> [Data | Next] -> [Data | Next] -> [Data | NULL]

Doubly linked list memory view:

NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL

Circular linked list memory view:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next]
          ^-----------------------------------------|

These variations change how memory is represented and how traversal is done:

• Singly linked lists are simple and use less memory.
• Doubly linked lists provide backward traversal but require more memory.
• Circular lists are useful where continuous cycling through elements is needed.

Working / Process

1. Creation of nodes in memory

• When a new element is added, memory is dynamically allocated for a node.
• The node is created with a data field and a link field.
• Example: if a node is created for value 50, a memory block is reserved somewhere in RAM, and its data field stores 50.

2. Linking nodes using addresses

• After a node is created, its next field stores the address of the next node.
• If it is the first node, the head pointer stores its address.
• Example:
  • head = 1000
  • node at 1000 points to node at 1030
  • node at 1030 points to node at 1100

3. Traversal of the list

• To access the list, start from head.
• Read the data in the current node.
• Move to the next node using the address stored in the link field.
• Continue until NULL is reached.
• This process reconstructs the logical order of elements from physically separate memory blocks.

Example traversal:

Head -> [12 | 2000] -> [18 | 3000] -> [27 | NULL]

Traversal order:

• Visit 12
• Move to address 2000, visit 18
• Move to address 3000, visit 27
• Stop at NULL

Advantages / Applications

• Dynamic memory usage: memory is allocated only when needed, so there is no need to predefine the size of the data structure.
• Efficient insertion and deletion: nodes can be inserted or removed without shifting large amounts of data, especially when the position is known.
• Useful in real-world applications: linked lists are used in implementing stacks, queues, graph adjacency lists, polynomial manipulation, memory management systems, and navigation histories.

Summary

• A linked list stores data in nodes connected by addresses rather than in contiguous memory.
• Each node contains data and a link to the next node, making the structure dynamic and flexible.
• The head pointer starts the list, and the last node points to NULL in a singly linked list.
• Linked list representation in memory allows efficient use of scattered memory blocks and supports easy growth.