Conteúdo do Curso
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
Basic List Operations Time Complexity
The next table shows the time complexity of basic operations for linked lists.
Search Operation
Searching in a linked list involves traversing the list from the beginning until the desired element is found. This operation has a time complexity of O(n)
in both the worst and average cases. Unlike arrays, linked lists do not support direct access to elements based on their index, resulting in linear time complexity for searching.
def search_linked_list(head, target):
current = head
while current:
if current.val == target:
return True
current = current.next
return False
Insert Operation
Inserting an element into a linked list can be done efficiently by updating only a few pointers. Specifically, we need to update the pointer of the element after which we are inserting the new element, ensuring it points to the new element, and the pointer of the new element must point to the next element in the list. This operation has a time complexity of O(1)
.
def insert_node(head, val, position):
if position == 0:
new_node = ListNode(val)
new_node.next = head
return new_node
current = head
for _ in range(position - 1):
if current is None:
raise ValueError("Position out of range")
current = current.next
new_node = ListNode(val)
new_node.next = current.next
current.next = new_node
return head
Delete Operation
Just like in inserting operation we need toupdate the pointers of the adjacent nodes to bypass the deleted node. As a result we have O(1)
time complexity for deleting operation.
def delete_node(head, target):
# If the list is empty, return None
if not head:
return None
# If the target is at the head, move the head to the next node
if head.val == target:
return head.next
# Search for the target value while keeping track of the previous node
prev = head
current = head.next
while current:
if current.val == target:
prev.next = current.next
return head
prev = current
current = current.next
return head
Note
When inserting or deleting an element in a linked list, the process involves adjusting pointers accordingly. In contrast, when working with arrays, to achieve the same operation, a segment of the array must be rewritten.
Obrigado pelo seu feedback!