A linked list is is a data structure that consists of a sequence of nodes, each pointing to the next node in the list. This allows for efficient insertion and deletion of elements at any position in the list.
How it works:
- Each node typically contains two items: a value (or "data") and a reference (i.e., a "link") to the next node in the list.
- The last node in the list has a null or undefined reference, indicating the end of the list.
- To insert a new element at a specific position, you simply need to create a new node and update the links between nodes accordingly.
class Node:
def __init__(self, data):
self.data = data # Data stored in the node
self.next = None # Pointer to the next node
class LinkedList:
def __init__(self):
self.head = None # The head of the linked list
# Add 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
return
current = self.head
while current.next: # Traverse to the last node
current = current.next
current.next = new_node
# Display the list
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Search for an element
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
# Delete a node by value
def delete(self, key):
current = self.head
# If the head node is to be deleted
if current and current.data == key:
self.head = current.next
current = None
return
# Search for the node to delete
prev = None
while current and current.data != key:
prev = current
current = current.next
# If the node was not found
if not current:
return
# Unlink the node
prev.next = current.next
current = None
# Create a linked list
ll = LinkedList()
# Append elements
ll.append(10)
ll.append(20)
ll.append(30)
# Display the linked list
ll.display() # Output: 10 -> 20 -> 30 -> None
# Search for an element
print(ll.search(20)) # Output: True
print(ll.search(40)) # Output: False
# Delete an element
ll.delete(20)
ll.display() # Output: 10 -> 30 -> None
# Add more elements
ll.append(40)
ll.append(50)
ll.display() # Output: 10 -> 30 -> 40 -> 50 -> None- Append: If you're appending a new node to the end of the list, the runtime complexity is O(1), because you simply need to update the next reference of the last node in the list.
- Insert at specific position: If you want to insert a new node at a specific position within the list (e.g., between two existing nodes), the runtime complexity is O(n), where n is the distance from the head of the list to the insertion point. This is because you need to traverse the list to find the correct position, which takes linear time.
- Delete at specific position: If you want to delete a node at a specific position within the list (e.g., between two existing nodes), the runtime complexity is O(n), where n is the distance from the head of the list to the deletion point. This is because you need to traverse the list to find the correct node, which takes linear time.
- Delete last node: If you're deleting the last node in the list (i.e., the tail of the list), the runtime complexity is O(1), because you simply need to update the next reference of the second-to-last node.
- Traversing the entire list: The runtime complexity for traversing the entire list is O(n), where n is the number of nodes in the list.
- Searching for a specific node: The runtime complexity for searching for a specific node within the list is O(n), where n is the number of nodes in the list.
- 141 Linked List Cycle
- 142 Linked List Cycle II
- 287 Find the Duplicate Number
- 160 Intersection of Two Linked Lists