nitesh.11911687's blog

Most Underrated Data Structure
By nitesh.11911687, history, 2 years ago, In English

Which is the Most Underrated Data Structure you know and reason for that.
This will help us to learn that and will help in future.

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it

linked list for sure. Reason : don't know

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    it's not underrated, it's just useless.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Everything has its uses, for example linked lists are quite nice for stuff like euler circles, and also linked list is very simple and cool to implement on your own

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Then implement LRU cache without linked list in O(1) complexity

      → Reply
      • »
        »
        »
        »
        5 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Solution

        is the time complexity the same as Linkedlist solution?

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      While they are not super useful, I would definitely agree that they are underrated.

      One nice trick is to combine them with maps to iterators std::map<T, std::list<T>::iterator>, in this way you can get benefits of both map and list. Example: 110657402 (although I don't understand this solution anymore so I am not sure whether that was really necessary).

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      bfs with list is delicious

      list q = {0};
for(int v : q) for(int i : g[v]) if(d[i] == -1) {
	q.push(i);
	d[i] = d[v] + 1;
}
      → Reply
»
2 years ago, # |
  Vote: I like it +137 Vote: I do not like it

A single integer

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Umm..stack and deque. They can be pretty useful sometimes!

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

set with custom comparator

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

the rope. It does string operations in O(logN) time complexity and I think it can be very useful sometimes

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's actually very useful, but sadly Splay Tree does almost everything it can do :(

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its actually just a splay tree/rb tree/skip list/any dynamic O(logN) data structure with strings in fact

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        one advantage) rope can be used like this:

        Code
        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

unordered_map and reason is it cause TLE due to collision problems .

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I'd say maps but everyone uses maps xd

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

STL std::list<..>, it's sometime useful when we need insertions and deletions in O(1).

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Cartesian tree

→ Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

bitset

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Trie

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maps. They are the best

→ Reply