CODEWITHSUNDEEP
c++data-structuresc++17
Brandon
Brandon

Reputation: 510

Boolean memory efficient linked list

How would you implement a memory efficient linked list of booleans? Obviously the next node pointer is much larger than the payload itself in the conventional linked list.

Upvotes: 1

Views: 531

Answers (2)

DrPizza
DrPizza

Reputation: 18360

Align nodes on something more than 1-byte boundaries, and use the least significant bit of the 'next' pointer to encode the bool value.

I'm not very good at coding directly into text boxes, but something along the lines of this:

struct node {
    static_assert(alignof(node) > 1, "node is insufficiently aligned");

    bool get_value() const {
        return static_cast<bool>(reinterpret_cast<size_t>(next) & 0x1);
    }

    void set_value(bool value) {
        size_t ptr = reinterpret_cast<size_t>(next);
        ptr &= ~1;
        ptr |= static_cast<size_t>(value);
        next = reinterpret_cast<node*>(ptr);
    }

    node* get_next() const {
        size_t ptr = reinterpret_cast<size_t>(next);
        ptr &= ~1;
        return reinterpret_cast<node*>(ptr);
    }

    void set_next(node* n) {
        bool value = get_value();
        next = n;
        set_value(value);
    }

private:
    node* next;
};

Upvotes: 4

Michael Albers
Michael Albers

Reputation: 3779

Here's a rough idea. In your linked list node, have two fields, first is a pointer to the next node, the second is another integer member of equal size to a pointer on your system. For example, on a 64-bit architecture:

struct node {
  node *next;
  uint64_t bits;
}

Each node then stores 64 booleans instead of just the one in a standard linked list implementation. Many operations become less time efficient (but that's the usual trade-off for memory/space efficiency) as you will have to do some bit shifting and something akin to tree balancing when you add a 65th boolean or insert into a "full" bitset, etc. (Also, thinking about this further, you probably need a 3rd member telling you the number of bits used.)

However, there are some advantages to this as a simple structure like this fits into a cache very well.

Like I said, this is a just a rough idea and there are probably a ton of pitfalls in implementing something like this. Write good tests.

Upvotes: 2

Related Questions