Linked List of Intervals

Question

Hello

I have the following two questions.

1. I'm aware of the concept of a linked list. What is a linked list of intervals?

2. I need to store a very huge (more than 100 bits) number in C/C++ and perform bitwise operations on it. Without using any big number library, what would be the best data structure to handle this scenario ?

Thank You

Answer 1

1. The name doesn't ring any bells. If intervals are objects, then it's just a linked list that stores those objects. Perhaps you mean a skip list?
2. If you're using C++, use a bitset. Otherwise, I would just use a classic table of four 32 bit ints.

Answer 2

For the second part of the question, try std::bitset

Answer 3

If you want to write your own class to handle large bit numbers (I don't know why you would), you could wrap a vector. You'd have to catch your own overflow though. This is a huge pain, and I only bring it up because this was a final project for us for a C++ class I took, lol. I don't recommended this =P

Answer 4

1: ?

2: Consider using std::vector<bool>.

Answer 5

I made a comment on this is another question, which was asked by someone else. This seems to be referring to my comment, so I'll explain what I meant. What I was suggesting was:

struct interval_node {
      int index;
      struct interval_node* next;
}

where index stores all the points where the bit "flips". This is a huge memory advantage if you have something like 11111111111100000000000, because it only needs to store the fact that the first bit is 1 (outside of the struct somewhere), as well as that the bit flips in the 12th index (being 0-based), rather than storing each individual bit itself. This can scale to 100,000 bits without eating up as much memory as long as the sequence doesn't have a ton of things like

1010101010101010101010101010101010101010101010

Because the it flips at every bit.