what is Linked list? Explain in the easiest way with examples
A **linked list** is a data structure used in computer science to store a collection of elements in a linear order. Unlike arrays, which store elements in contiguous memory locations, linked lists store each element (called a "node") in separate memory locations. Each node contains two parts:
1. **Data**: This is the value or information stored in the node.
2. **Pointer (or reference)**: This is a link to the next node in the sequence.
### Basic Structure of a Linked List:
- **Node**: A basic unit containing data and a reference to the next node.
- **Head**: The first node in the linked list.
- **Tail**: The last node, which points to null (or None in Python) because it doesn't have a next node.
### Types of Linked Lists:
1. **Singly Linked List**: Each node points to the next node, and the last node points to null.
2. **Doubly Linked List**: Each node has two pointers: one pointing to the next node and another pointing to the previous node.
3. **Circular Linked List**: The last node points back to the first node, forming a circle.
### Visual Example:
Imagine a linked list of numbers: 10, 20, 30.
```
+------+ +------+ +------+
| 10 | -> | 20 | -> | 30 |
+------+ +------+ +------+
```
Here’s what this looks like in terms of nodes:
- **Node 1**: Data = 10, Next = address of Node 2
- **Node 2**: Data = 20, Next = address of Node 3
- **Node 3**: Data = 30, Next = null
### Advantages of Linked Lists:
- **Dynamic Size**: Unlike arrays, which have a fixed size, linked lists can grow or shrink in size as needed.
- **Efficient Insertions/Deletions**: You can easily add or remove nodes without shifting other elements around, as you just need to update pointers.
### Disadvantages of Linked Lists:
- **Memory Overhead**: Each node requires extra memory for storing the pointer/reference.
- **Access Time**: Accessing elements is slower than arrays because you have to traverse from the head to the desired node.
### Simple Example in Code (Python):
Here is a basic example of a singly linked list in Python:
```python
class Node:
def __init__(self, data):
self.data = data # Store data
self.next = None # Pointer to the next node
class LinkedList:
def __init__(self):
self.head = None # Initialize the head of the list
# Method to append a new node at the end
def append(self, data):
new_node = Node(data)
if not self.head: # If the list is empty
self.head = new_node # Set the new node as the head
return
last_node = self.head
while last_node.next: # Traverse to the last node
last_node = last_node.next
last_node.next = new_node # Link the last node to the new node
# Method to print the linked list
def print_list(self):
current_node = self.head
while current_node: # Until you reach the end of the list
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None") # End of the list
# Example usage
linked_list = LinkedList()
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
linked_list.print_list() # Output: 10 -> 20 -> 30 -> None
```
This example defines a simple linked list where you can append new nodes and print the entire list. It helps illustrate how linked lists work in a very straightforward way.