what is singly linked list? explain with example
A **singly linked list** is a data structure used in computer science to represent a collection of elements, where each element (commonly called a "node") contains two main components:
1. **Data**: The information or value that the node holds.
2. **Next Pointer**: A reference (or address) that points to the next node in the sequence.
In a singly linked list, each node points to the next node in the list, and the list ends with a node that points to `null` (or `None` in Python), indicating that it is the last node. One of the most significant characteristics of a singly linked list is that it allows for efficient insertions and deletions, as these operations don't require the elements to be contiguous in memory.
### Key Characteristics:
- **Dynamic Size**: A singly linked list can grow or shrink in size dynamically with no need for pre-allocation of memory.
- **Non-contiguous Memory Allocation**: Nodes can be allocated in different memory locations.
### Structure of a Node:
In a singly linked list, a node is usually structured in the following way (example in Python):
```python
class Node:
def __init__(self, data):
self.data = data # The data the node will hold
self.next = None # The pointer to the next node
```
### Example of a Singly Linked List:
Let's consider an example of a singly linked list containing three integers: 10, 20, and 30.
1. Create nodes for each data:
- Node1 holds 10
- Node2 holds 20
- Node3 holds 30
2. Link the nodes together:
- Node1's next pointer points to Node2
- Node2's next pointer points to Node3
- Node3's next pointer points to `null`
Here’s how it looks visually:
```
Node1 -> Node2 -> Node3 -> None
```
Where:
- Node1: stores 10, points to Node2
- Node2: stores 20, points to Node3
- Node3: stores 30, points to None
### Operations:
Here are some common operations that can be performed on a singly linked list:
1. **Insertion**: Adding a new node to the list (at the beginning, end, or in the middle).
2. **Deletion**: Removing a node from the list.
3. **Traversal**: Accessing each node in the list to read or modify the data.
4. **Search**: Finding a node with a specific value.
### Insertion Example:
Here’s a simple way to insert a new node with the value `25` after the first node (which holds `10`):
```python
class LinkedList:
def __init__(self):
self.head = None # Initialize the head of the list
def insert(self, value):
new_node = Node(value) # Create a new node with the given value
if not self.head:
self.head = new_node # If the list is empty, set the head to the new node
return
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.next = new_node # Link the new node at the end
# Usage
linked_list = LinkedList()
linked_list.insert(10)
linked_list.insert(20)
linked_list.insert(30)
linked_list.insert(25) # This will add 25 at the end
# Traversing the list to print values
current = linked_list.head
while current:
print(current.data)
current = current.next
```
### Conclusion:
A singly linked list is a fundamental data structure useful for various applications where dynamic size and efficient insertions/deletions are required. It forms the basis for more complex structures like stacks, queues, and graphs.