Week 2: Analysis of Algorithms, Dynamic Data Structures (76)

Modifying a Linked List (cont)

Delete the first element:

deleteHead(L):
|  Input  non-empty linked list L
|  Output L with head deleted
|
|  return L.next    // move to second element

Time complexity: O(1)

Delete a specific element (recursive version):

deleteLL(L,d):
|  Input  linked list L, value d
|  Output L with element d deleted
|
|  if L=NULL then            // element not in list
|     return L
|  else if L.value=d then    // d found at front
|     return deleteHead(L)   // delete first element 
|  else                      // delete element in tail list
|     L.next=deleteLL(L.next,d)
|  end if
|  return L

Time complexity: O(|L|)