nitesh.11911687's blog

Most Underrated Data Structure
By nitesh.11911687, history, 23 months 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 (25)
| Write comment?
»
23 months ago, # |
  Vote: I like it +52 Vote: I do not like it

linked list for sure. Reason : don't know

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

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

    → Reply
    • »
      »
      »
      23 months 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
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      23 months 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
    • »
      »
      »
      23 months 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
»
23 months ago, # |
  Vote: I like it +137 Vote: I do not like it

A single integer

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

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

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

set with custom comparator

→ Reply
»
23 months 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
  • »
    »
    23 months 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
    • »
      »
      »
      23 months 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
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        one advantage) rope can be used like this:

        Code
        → Reply
»
23 months 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
»
23 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I'd say maps but everyone uses maps xd

→ Reply
»
23 months 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
»
23 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Cartesian tree

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

bitset

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

Trie

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maps. They are the best

→ Reply