A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.

Linked lists can be singly or doubly linked.

### Singly linked list

A singly linked list would use a node with data and only one reference (link) to the next node.

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
```

#### Full implementation

### Doubly linked list

A doubly linked list would use a node with data and two references (links) which would point to the next and previous nodes.

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
```

#### Full implementation

```
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class LinkedList():
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
else:
next_node = self.head
while next_node.next:
next_node = next_node.next
next_node.next = Node(data)
def push(self, data):
if not self.head:
self.head = Node(data)
else:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert(self, data, index):
if not self.head and index > 0 or index < 0:
return "Index out of range."
else:
next_node = self.head
prev_node = None
curr_index = 0
while curr_index != index:
prev_node = next_node
next_node = next_node.next
curr_index += 1
new_node = Node(data)
if prev_node:
prev_node.next = new_node
new_node.next = next_node
else:
new_node.next = next_node
self.head = new_node
def pop(self):
next_node = self.head
prev_node = None
while next_node.next:
prev_node = next_node
next_node = next_node.next
prev_node.next = None
return next_node.data
def remove(self, index):
if not self.head and index > 0 or index < 0:
return "Index out of range."
else:
next_node = self.head
prev_node = None
curr_index = 0
while curr_index != index:
prev_node = next_node
next_node = next_node.next
curr_index += 1
if prev_node:
prev_node.next = next_node.next
else:
self.head = next_node.next
def reverse(self):
prev_node = None
current = self.head
while current:
next_node = current.next
current.next = prev_node
prev_node = current
current = next_node
self.head = prev_node
def search(self, data):
if not self.head:
return "Not Found"
else:
next_node = self.head
index = 0
while next_node.data != data:
next_node = next_node.next
index += 1
if not next_node:
return "Not Found"
return index
def sort(self):
current_node = self.head
next_node = None
if not self.head:
return
else:
while current_node:
next_node = current_node.next
while next_node:
if current_node.data > next_node.data:
current_node.data, next_node.data = next_node.data, current_node.data
next_node = next_node.next
current_node = current_node.next
def print_list(self):
next_node = self.head
while next_node:
print(next_node.data)
next_node = next_node.next
```

**Time Complexity**

**Singly Linked List**

Operation | Best Case | Average Case | Worst Case | Space Complexity |
---|---|---|---|---|

Insertion (Front) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Insertion (Back) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Insertion (Middle) | (O(1)) | (O(n)) | (O(n)) | (O(1)) |

Deletion (Front) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Deletion (Back) | (O(n)) | (O(n)) | (O(n)) | (O(1)) |

Deletion (Middle) | (O(1)) | (O(n)) | (O(n)) | (O(1)) |

Search | (O(1)) | (O(n)) | (O(n)) | (O(1)) |

Access | (O(1)) | (O(n)) | (O(n)) | (O(1)) |

Length | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Explanation:

**Insertion (Front)**: Inserting a new node at the front of a linked list involves creating a new node and updating the head pointer to point to the new node. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Insertion (Back)**: Inserting a new node at the back of a linked list involves traversing the entire list to reach the last node and then appending the new node to the end. In the best and average cases, when a reference to the last node is maintained, this operation has a constant time complexity of (O(1)). However, in the worst case, when the reference to the last node is not available, traversal to the last node takes linear time (O(n)).**Insertion (Middle)**: Inserting a new node in the middle of a linked list involves traversing to the desired position and updating the pointers of the adjacent nodes to include the new node. In the best case, when the insertion position is known, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when traversal is required, this operation takes linear time (O(n)).**Deletion (Front)**: Deleting the first node of a linked list involves updating the head pointer to point to the second node. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Deletion (Back)**: Deleting the last node of a linked list involves traversing the entire list to reach the second-to-last node and updating its next pointer to None. In the best and average cases, when a reference to the last node is maintained, this operation takes linear time (O(n)). However, in the worst case, when the reference to the last node is not available, traversal to the second-to-last node also takes linear time (O(n)).**Deletion (Middle)**: Deleting a node from the middle of a linked list involves traversing to the node to be deleted and updating the pointers of the adjacent nodes to bypass the deleted node. In the best case, when the deletion position is known, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when traversal is required, this operation takes linear time (O(n)).**Search**: Searching for a node with a given value in a linked list involves traversing the entire list until the target node is found. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when the target node is not found until the end of the list, this operation takes linear time (O(n)).**Access**: Accessing the value of a node at a given index in a linked list involves traversing the list until the target node is reached. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when the target node is at the end of the list or not found, this operation takes linear time (O(n)).**Length**: Determining the length of a linked list involves traversing the entire list and counting the number of nodes. This operation has a constant time complexity of (O(1)) in all cases because a reference to the last node can be maintained to avoid traversal.

**Doubly Linked List**

Operation | Best Case | Average Case | Worst Case | Space Complexity |
---|---|---|---|---|

Insertion (Front) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Insertion (Back) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Insertion (Middle) | (O(1)) | (O(n/2)) | (O(n)) | (O(1)) |

Deletion (Front) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Deletion (Back) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Deletion (Middle) | (O(1)) | (O(n/2)) | (O(n)) | (O(1)) |

Search | (O(1)) | (O(n/2)) | (O(n)) | (O(1)) |

Access | (O(1)) | (O(n/2)) | (O(n)) | (O(1)) |

Length | (O(1)) | (O(1)) | (O(1)) | (O(1)) |

Explanation:

**Insertion (Front)**: Inserting a new node at the front of a doubly linked list involves creating a new node, updating pointers, and updating the head pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Insertion (Back)**: Inserting a new node at the back of a doubly linked list involves creating a new node, updating pointers, and updating the tail pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Insertion (Middle)**: Inserting a new node in the middle of a doubly linked list involves traversing to the desired position and updating pointers. In the best case, when the insertion position is known, this operation has a constant time complexity of (O(1)). However, in the average case, when the insertion position is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the insertion position is at the end of the list.**Deletion (Front)**: Deleting the first node of a doubly linked list involves updating pointers and updating the head pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Deletion (Back)**: Deleting the last node of a doubly linked list involves updating pointers and updating the tail pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.**Deletion (Middle)**: Deleting a node from the middle of a doubly linked list involves traversing to the desired position and updating pointers. In the best case, when the deletion position is known, this operation has a constant time complexity of (O(1)). However, in the average case, when the deletion position is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the deletion position is at the end of the list.**Search**: Searching for a node with a given value in a doubly linked list involves traversing the list until the target node is found. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average case, when the target node is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the target node is at the end of the list.**Access**: Accessing the value of a node at a given index in a doubly linked list involves traversing the list until the target node is reached. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average case, when the target node is in the middle of the list