Implementation of a linked list with bucket?

Question

I have a linked list which stores 1 string of text in each node and each node can point to next node (basically what a linked list does).

I am trying to make another linked list where each node has an array of string of a given size (bucket) lets say 20.

So each node stores a array of strings[20] and a link to next node (bucket linked list).

On storing (adding new item) in the linked list it should keep filling the array or bucket of current node until its full and when its full it should split the array or bucket into 2 buckets of same size (20) and have 10 items in each bucket.

This way all the nodes will have buckets which are half empty only first bucket can be half or more than half empty at any given time. And again start to fill the new string in correct bucket(one of the half empty bucket) until its filled and repeat the process.

I was thinking if there is any implementation of a data structure like this anywhere please point me to it. So I can take a look and have a better understanding.

Answer 1

Okay, so you have two linked lists. A list of buckets and a list of nodes:

bucket -> bucket -> bucket -> NULL
   |         |         |
  node      node      node
   |         |         |
  node      node      node
   |         |         |
  node      node      node
   |         |         |
  node      NULL      NULL
   |
  NULL

Insertion is always to the first bucket. If that overflows, the contents are split and the second half is transferred to a new bucket that is inserted after the first bucket.

In addition to the nodes (nd) and buckets (bt), the code below uses a bucket list (bl) as front end for all operations:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct Bucketlist Bucketlist;
typedef struct Bucket Bucket;
typedef struct Node Node;

/*
 *      The node holds the actual data, here an int
 */
struct Node {
    int data;
    Node *next;
};

Node *nd_new(int x)
{
    Node *nd = malloc(sizeof(*nd));

    nd->data = x;
    nd->next = NULL;

    return nd;
}

void nd_delete(Node *nd)
{
    while (nd) {
        Node *nx = nd->next;

        free(nd);
        nd = nx;
    }
}



/*
 *      The bucket holds the nodes as a linked list. It has a tail
 *      for easy inserting and keeps a count of its elements. Buckets
 *      are also organised in a linked list via the next pointer.
 */
struct Bucket {
    Node *head;
    Node *tail;
    Bucket *next;
    int count;
};

Bucket *bt_new()
{
    Bucket *bt = malloc(sizeof(*bt));

    bt->head = NULL;
    bt->tail = NULL;
    bt->next = NULL;
    bt->count = 0;

    return bt;
}

void bt_delete(Bucket *bt)
{
    while (bt) {
        Bucket *nx = bt->next;

        nd_delete(bt->head);
        free(bt);
        bt = nx;
    }
}

void bt_split(Bucket *bt)
{
    Bucket *nx = bt_new();
    Node *nd = bt->head;

    int n = bt->count / 2;

    nx->next = bt->next;
    bt->next = nx;

    nx->count = bt->count - n;
    bt->count = n;

    while (--n) nd = nd->next;
    nx->head = nd->next;
    nx->tail = bt->tail;
    nd->next = NULL;
    bt->tail = nd;
}

void bt_add(Bucket *bt, int x)
{
    Node *nd = nd_new(x);

    if (bt->count >= 20) bt_split(bt);

    if (bt->head == NULL) {
        bt->head = bt->tail = nd;
    } else {
        bt->tail->next = nd;
        bt->tail = nd;
    }
    bt->count++;
}

void bt_print(Bucket *bt)
{
    Node *nd = bt->head;

    printf("%d items [", bt->count);

    while (nd) {
        if (nd != bt->head) printf(", ");
        printf("%d", nd->data);
        nd = nd->next;
    }

    printf("]\n");
}



/*
 *      The bucket list is just a front end to the linked list of
 *      buckets. It is the interface that the cleient code uses.
 */
struct Bucketlist {
    Bucket *head;
};

void bl_add(Bucketlist *bl, int x)
{
    if (bl->head == NULL) bl->head = bt_new();
    bt_add(bl->head, x);
}

void bl_delete(Bucketlist *bl)
{
    bt_delete(bl->head);
}

void bl_print(Bucketlist *bl)
{
    Bucket *bt = bl->head;

    while (bt) {
        bt_print(bt);
        bt = bt->next;
    }
}



int main()
{
    Bucketlist bl = {NULL};
    int i;

    srand(time(NULL));

    i = 36 + (rand() & 63);
    while (i--) bl_add(&bl, rand() & 1023);

    bl_print(&bl);
    bl_delete(&bl);

    return 0;
}

I've used integers as data here, but it should be easy to modify this list for strings.