#better way of indexing nodes of a doubly linked list

79 messages · Page 1 of 1 (latest)

spiral aurora
#

basically i have a doubly-linked list where each node needs to have an index associated with it.

typedef struct node{
  struct node* prev;
  struct node* next;
  char*        text;
  uint32_t     index;
} node_t;

if i want to insert or delete a node, i need to update the index of every node after it. Currently im doing something like this:

void increment_following_indices(node_t* node){
  for(; node != NULL; node = node -> next)
    ++node -> index;
}

the problem is if i have tens of thousands of these nodes its gonna get slow. Should i use a different data structure or can someone help me find a clever solution?

lucid spruceBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

opaque yew
#

but why do yo have that index?

spiral aurora
winter bloom
#

I think it's not good way to save index in the node.

#

You can use the index map separately.

spiral aurora
#

but it gets kinda tricky

opaque yew
winter bloom
#

map<node*, index> indexmap;

#

like this.

spiral aurora
#

this is C

winter bloom
#

Oh, i see.

spiral aurora
#

plus i think a hashmap would use too much memory for this

opaque yew
#

it also doesn't fix the issue: when inserting, the map would need an update

opaque yew
lofty wind
#

Why store nodes in a linked list AND in a hashmap?
That's going to be hard to keep in sync.

spiral aurora
#

right

spiral aurora
opaque yew
#

and hat node mght not be the head, right?

spiral aurora
#

sorry if i misunderstood

spiral aurora
opaque yew
#

and your list is not sorted by text, by any chance?

spiral aurora
#

nope the text completely unrelated to the index

#

it gets read from a file

opaque yew
#

how do you take the decision to insert in the middle of the list?

#

(like, what could be a reason to not append or prepend?)

spiral aurora
#

i made some functions for inserting like: void insert_node(node_t* node, node_t* other); just as an example

#

i wont get into what triggers a function to be called, but i have like an entire file of functions for operations on nodes

opaque yew
#

I'm just wondering if you couldn't rather use a binary tree or something like that
because then getting back the index "on-demand" would only be O(log(N)), which might be an ok compromise
(and trees can encode lists)

#

I think you wouldn't need an ordering in a stndard red-black tree, as you already can target the insertion point. so you just have to code the rebalancing technique. alternatively, you can also code a skiplist (also skipping the ordering part), as it's easier to code and offers good average performance

spiral aurora
#

lmao

opaque yew
#

I doubt, since I don't use SO

#

but good to know it's standard

spiral aurora
#

basically yes, thats what people recommend

#

ill see what i can do 👍

opaque yew
spiral aurora
opaque yew
#

this one

Screenshot_2024-03-04_at_05.32.46.png
opaque yew
#

indeed

spiral aurora
opaque yew
#

if you don't want to use the std lib for random numbers, you could maybe just use the following heuristic:

struct {
  unsigned long long int x1;
  unsigned long long int x2;
  unsigned long long int N;
} Generator;

unsigned long long int move_and_get(Generator *g) {
  const unsigned long long int x3 = (g->x1 + g->x2) % N;
  g->x1 = g->x2;
  g->x2 = x3;
  return x3;
}```
#

for N prime, iirc it creates a random process of pairwise independent numbers, uniformly distributed over [0, N) ; under the assumption x1,x2 are chosen independent and uniform (just make sure the start is not (0,0), otherwise well, it won't move a lot)

(and ofc if N is small enough, you don't need long long)

#

might be good enough for you case (and it's deterministic, so easier to debug; or at least, reproduce a bug)

spiral aurora
#

thanks ill use it 👍

lucid spruceBOT
#

@spiral aurora Has your question been resolved? If so, type !solved :)

opaque yew
#

or maybe just a classic random number generator actually

spiral aurora
#

ill try as much as i can. but i'll get to work later tonight or tmrw morning at school, i need a break right now since i've been working on something else all day

#

ill let yall know !!

spiral aurora
#

@opaque yew I think im gonna go with something like a skip list since it looks like the easiest to implement and im pretty sure i can make up for the added memory cost by using a xor linked list on the normal lane

#

then ill get rid of the index of every node on the normal lane and have each node on the express lane keep the index of the node it points to, that way i can update the following indices in fewer iterations

#

on second thought it may not be that easy

opaque yew
#

remember that the goal of this structure is to have a O(log(n)) way to retrieve the index. for a skip-list, you can go fast in one direction only (where the skips happen), which is fine because knowing your position to the end + the length of the list, gives you the index

spiral aurora
# opaque yew what blocks you exactly ?

having one big xor linked list on the normal line makes a lot of trouble. instead im doing a bunch of small xor linked lists and having each of the express nodes keep track of how many nodes in it's list. sorry if i explained that poorly heres a picture i made. ill send some poc in within a few hours i promise

Screenshot_from_2024-03-04_14-59-27.png
opaque yew
#

you were not in the skip-list topic eventually ?

spiral aurora
#

sorry? can you rephrase?

opaque yew
#

I thought you eventually decided to code a skip-list to solve the problem

spiral aurora
#

i decided that a skip list would be the best option, but combining it with one big xor linked list is gonna complicate things, so now ive decided im gonna do it like the picture shows because that means less pointers i need to keep track of and update. im working on implementing it right now

opaque yew
# opaque yew this one

intuitively, I would have thought only the bottom level in this picture, really requires another pointer level (to achieve the double-linked list feature)

#

in such a way that in one direction, you have a simple linked list ; and in the other direction, you have a skip list

#

because having only one direction being fast, is enough to acquire the O(log(n)) desired feature for indexing

spiral aurora
opaque yew
#

yes

spiral aurora
#

thats why im givin each node on the top level a pointer to the head of its own small list

#

since i can only start from one end given only one pointer

opaque yew
#

but why do you want a xor list actually ?

spiral aurora
#

so all together it will be the same size as a regular skip list but the bottom level is now doubly linked

spiral aurora
opaque yew
#

that I don't get tbh. in a standard skip list, if you're in the middle, you can continue going forward as usual

and if your low-level layer is a double linked list, you can just go down there and go backward if you desire 🤔

#

(it takes one pointer more than a xor list, for sure)

spiral aurora
#

right, this skip list is just a singly linked list. and the bottom layer is doubly linked

#

i may not be explaining this the best id better start working on the poc so i can send it

spiral aurora
# 
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

// doubly-linked
// one data, two links encoded as one
typedef struct _xll_n{
    void* data;
    long  nodes; // (prev) ^ (next)
} node_t;

// singly-linked
// two data, one link
typedef struct _skip_n{
    struct _skip_n* next; // pointer to next group
    node_t*         node; // head of group
    uint32_t        size; // how many nodes in this group?
} skip_t;

node_t* create_node(void* data){
node_t* node = malloc(sizeof(node_t));
    *node = (node_t){
        .data  = data,
        .nodes = 0
    };

    return node;
}

skip_t* create_skip_node(void){
    skip_t* _node = malloc(sizeof(skip_t));
    *_node = (skip_t){
        .node = NULL,
        .size = 0
    };

    return _node;
}

void append(skip_t* group, node_t* node){
    while(group -> next != NULL)
        group = group -> next;

    // if the group is full
    if(group -> size == UINT8_MAX){
        // if there isn't another group
        if(group -> next == NULL){
            // create one
            puts("new group");
            group -> next = create_skip_node();
            group -> next -> node = node;
            ++group -> next -> size;
            return;
        }

        // else, try appending again on the next group
        append(group -> next, node);
        return;
    }

    // if the group is empty
    if(group -> size == 0){
        puts("appended first");
        group -> node = node;
        ++group -> size;
        return;
    }

    node_t* next, *curr = group -> node, *prev = NULL;
    for(uint8_t i = 0; i < UINT8_MAX; ++i){
        next = (node_t*)(curr -> nodes ^ (long)prev);

        // if we've reached the end of this group
        if(next == NULL){
            // append the node
            puts("appended");
            node -> nodes  = (long)curr;
            curr -> nodes ^= (long)node;
            ++group -> size;
            return;
        }

        // else, continue traversing forward
        prev = curr;
        curr = next;
    }
}

int main(void){
    skip_t* group = create_skip_node();

    uint32_t n = 0;
    scanf("%u", &n);

    for(uint32_t i = 0; i < n; ++i)
        append(group, create_node(NULL));

    while(group != NULL){
        printf("%p : %u\n", group, group -> size);
        group = group -> next;
    }
}
#

the comments might not make much sense but the output should be clear i hope

#

doing it this way, we can get the index of any node: the sum of the size of all previous skip nodes + the distance of the xll node from the head of it's group (we'd need to have been keeping track of it during traversal)