One Way Solution

key data next →

key data next →

key data next  NIL

 

Chained-Hash-Insert (T: Hash_Table, x: Node_Ptr)    -- pre: ∀y: Node_Ptr, y ∈ T's nodes: x ≠ y    -- post: node referenced by x is    --         inserted at the head of the list at T[ h( x.key ) ] Node_Ptr head ← T[ h( x.key ) ] x.next ← head T[ h( x.key ) ] ← x

Chained-Hash-Search (T: Hash_Table, k:U ) : Node_Ptr    -- post: NIL is returned if k is not found in any    --         of the nodes in the list at T[ h(k) ]    --         x is returned where x is the address of    --         a node in T where x.key = k Node_Ptr x ← T[ h(k) ]; while x ≠ NIL and x.key ≠ k do x ← x.next return x

Chained-Hash-Delete (T: Hash_Table, x: Node_Ptr)    -- pre: ∃y: Node_Ptr, y ∈ T's nodes: x = y    --        Node_Ptr is singly linked    -- post: node referenced by x is deleted    --          from the list at T[ h( x.key ) ] if T[ h( x.key ) ] = x      then T[ h( x.key ) ] ← x.next     else        p ← T[ h( x.key ) ]                           -- parent        c ← p.next                                       -- child        while c ≠ x do            p ← c            c ← c.next        p.next ← c.next

Question - Delete k₇.