gozeloglu
Store in map
Keys and values(as an object) can be stored in a map to access in O(1) time complexity. Also, updates can be done faster.
Hi @nottrif. In the current implementation, data is stored in a linked list. But, we search for a key in O(n) time complexity. We can improve the performance by using a map which has a key in string type and value in Item type with linked list. We can get the key in O(1) time complexity.
@gozeloglu Thank you for the explanation. Instead of storing a List< Item > we would be storing a List<Map<ItemKey, Item>? ItemKey -> String. What about the extra memory that adding a map data structure would introduce?
I am not sure about List<Map<ItemKey, Item>>. Let me tell you the idea in my mind in detail. In the current implementation, we are storing data as Item in the linked list's nodes. This has O(n) time complexity for searching, deleting, or updating the keys. We need to traverse the linked list. To decrease the time complexity, we can use a map as well. The trick point is storing nodes as values in the map. In that way, we can reach the nodes directly by key search in the map. Then, we can update or delete node(s) in O(1).
map = {
"1": Item{ key: "1", val: 23, exp: 1111111, prev: *Item{}, next: *Item{}}
"2": Item{ key"2", val:"value1", exp: 2222222, prev: *Item{}, next: *Item{} }
....
}
Linked list: head <--> Item{ key: "1", val: 23, exp: 1111111} <--> Item{ key"2", val:"value1", exp: 2222222} <--> tail
Probably, you need to store next and prev pointers as well. Make sure that while implementing. Also, please do not hesitate to rename the variable names. If you have any questions, please let me know.