Implementation of Singly Linked List 23-34

3.3 Introduction to Singly Linked List

A singly linked list is a fundamental data structure in computer science, particularly useful for dynamic memory allocation and efficient management of data. Unlike arrays, which require contiguous memory allocation, a singly linked list consists of nodes that are connected sequentially, where each node contains two fields: data and a pointer to the next node in the sequence. The first node is referred to as the 'head' of the list, and the last node points to NULL, indicating the end of the list. This structure allows for efficient insertion and deletion of elements, as it does not require shifting of elements like in arrays. The primary advantage of a singly linked list is its dynamic size, meaning it can grow or shrink during program execution. However, it does not allow direct access to elements by index, requiring traversal from the head node to reach a specific element. Singly linked lists are widely used in applications such as implementation of stacks, queues, and other abstract data types.

• A singly linked list is a collection of nodes connected sequentially.
• Each node contains data and a pointer to the next node.
• The head node is the starting point of the list.
• The last node points to NULL, marking the end of the list.
• Singly linked lists allow dynamic memory allocation.
• Insertion and deletion operations are more efficient compared to arrays.
• 📌 Node: A basic unit of a linked list containing data and a pointer.
• 📌 Head: The first node in a linked list.
• 📌 NULL: A special pointer value indicating the end of the list.

3.4 Memory Representation of Singly Linked List

The memory representation of a singly linked list is different from that of an array. In an array, elements are stored in contiguous memory locations, but in a singly linked list, each node can be located anywhere in memory. Each node contains two parts: the data field, which stores the actual value, and the next pointer, which stores the address of the next node. The head pointer stores the address of the first node. When a new node is created, memory is dynamically allocated for it, and the next pointer of the previous node is updated to point to this new node. The last node's next pointer is set to NULL, indicating the end of the list. This structure allows for efficient use of memory, as nodes can be created and deleted as needed without reallocating the entire structure. The linked nature of the nodes also means that elements can be inserted or deleted without shifting other elements, as is necessary in arrays.

• Nodes in a singly linked list are not stored in contiguous memory.
• Each node contains a data field and a next pointer.
• The head pointer stores the address of the first node.
• Dynamic memory allocation is used to create new nodes.
• The last node's next pointer is set to NULL.
• Efficient memory usage as nodes can be added or removed as needed.
• 📌 Dynamic Memory Allocation: Allocating memory at runtime as needed.
• 📌 Pointer: A variable that stores the memory address of another variable.
• 📌 Contiguous Memory: Memory locations that are next to each other.