Borrowing books a library data structure

2
votes

First off, I would like to mention the question is a homework question. I have been pondering about the implementation for long enough.

I have to think and implement a library software that has the following functionalities:

  1. add/remove a new subscriber.
  2. borrow/return a book.
  3. what books the following subscriber have?
  4. which subscriber holds the following book?
  5. list of the subscribers with most books.

I thought of implementing a heap and 2 red black trees, the problem is that the space complexity is high. So I was wondering if I am missing something.

The subscribers are stored by I.Ds, the books have code names. One Red Black tree is for the subscribers and the other is for the borrowed books. The heap is a max heap, in order to implement the last requirement.

I cannot use anything else but data structures.

Thanks for any insights and answers.

1
data-structurescomputer-sciencesoftware-design
Can you expand? Your R-B-trees are one for subscriber and one for books? Maybe hash tables are worth consideration here. Also, a heap just for req 5 seems like overkill, it should be possible to track that in O(1) time overhead per borrow/return operation with a doubly linked list of doubly linked lists. But that will possibly mean your person object needs knowledge of the DLLs, which is not nice from a design point of view. - Ulrich Schwarz
Well, you are right one rb is for the subscribers and one for the books that are borrowed. And it is an overkill just for that but I need to return the list of subscribers O(n) would be nice but it cannot be O(n) like this. I tought about combining the data structures together and do a sort of EAV modeling pattern with a hash table, searches will take longer(possibly O(n). and there may be collisions). - Cu7l4ss

1 Answers

0
votes

I guess you can also use containers, like structs? Use:

  • One hash set/hash table for the books:
    Additionally store a flag which determines whether the book is borrowed and the subscriber it's borrowed to.
  • One hash map from subscriber->linked list of books, to store not only all the subscribers but also which books they have borrowed.

This allows you to perform all listed tasks in O(1), except sorting the subscribers by the count of the books they have borrowed.