Member Avatar for starkk

In chain hashing how can the order of deleting a node in double linked list be O(1) it should first check for the slot which is of O(1)and then it should check for the element to be to be removed in the linked list pointed by that slot which is of order O(n) in the worst case and O(n/m)in avg case considering n total elements and m slots.so the total so the total order of deletion should be O(n/m) which is the same when we implement with singled linked lists.Then,what is the use of double linked list and how will the order for deletion be O(1) as the text book suggests...

some one help me pls..

  • 3 Contributors
  • 3 Replies
  • 127 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by raptr_dflo

Dani AI

Generated

Short answer: the textbook is distinguishing two different costs. Finding the key in a chained hash table costs proportional to the bucket length, while unlinking a node from a linked list (once you have a pointer to it, or to its predecessor) is constant-time.

When you delete by key the total work breaks down into two parts:

  • compute the bucket index (O(1)),
  • scan the chain to locate the node (expected Θ(alpha) where alpha = n/m),
  • unlink the node from the list (Θ(1) if you have the node or its predecessor; doubly linked lists make this trivial when you only hold the node pointer).

So a delete-by-key is Θ(1 + alpha) on average. Texts (including CLRS) often say “O(1)” when they assume either (a) the load factor alpha is kept constant by resizing, or (b) they refer only to the unlink operation once the node is located. That explains ’s comment about amortized/expected bounds and ’s observation that removing a found node is O(1).

Caveats: worst-case deletion is Θ(n) if many keys collide (no uniform hashing). Practical advice: keep alpha bounded (rehash on growth), use a good hash function, and choose singly- vs doubly-linked buckets based on API needs. Doubly linked lists are useful when removals are done from stored node pointers (iterators) without re-scanning the bucket.

For a concise reference on expected vs worst-case hash-table costs see the Hash table overview: Hash table on Wikipedia.

Recommended Answers

All 3 Replies

Member Avatar for Narue

Perhaps the book means amortized O(1) instead of per operation O(1). Though that's the same for single linked lists, so I can't say why your book makes a distinction. Which book is it?

Member Avatar for starkk

introduction to algorithms by cormen

Member Avatar for raptr_dflo

Perhaps the author's intent is: the complexity of finding the node to delete is O(n/m) (on average), but once found, the complexity of deleting that node is O(1)? Since I don't own a copy of the book, and you didn't explicitly quote the author, I can't be sure.

There is a listing of known errata available on his website -- you'll need the edition and printing of your book, and page number of the suspected error, to see if it's already been reported.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.