0

I'm trying to write a linked list, with the restriction being that the pointer inside of a node has to point to the next node's pointer. With this restriction, how would I ever access a variable inside of a node? Say the node is defined

struct Node {
    int val;
    void *next;
}

but for every Node, say we have currentNode and nextNode, we make the void *next value

currentNode.next = &(nextNode.next);

How would you go about creating this and efficiently accessing each node?

Avallauch
  • 65
  • 2
  • 11
  • Why do you have this restriction? And why have you declared it as `void*` instead of `struct node **`? – Barmar Oct 05 '17 at 03:38
  • 2
    The `next` pointer is a certain [*offset*](http://en.cppreference.com/w/c/types/offsetof) from the beginning of the structure. While highly discouraged you can always get a pointer to the structure through some simple arithmetics. – Some programmer dude Oct 05 '17 at 03:39
  • It's a school assignment, we can't modify the struct. We have to write a function that works with a list like this, but I need to understand how the list works before I can do that. I can't find any examples of a list like this. The restriction is in this assignment, the void *next points to the next field in the next node, not the beginning of the node. That is, curr_node.ptr = &(next_node.ptr); not curr_node.ptr = &next_node – Avallauch Oct 05 '17 at 03:40
  • 2
    @Barmar I think you mean `struct Node *` – Tom Karzes Oct 05 '17 at 03:41
  • If that's the restriction, fine. Change the struct so that the 'next' pointer is at the start of the struct: 'struct Node {void *next; int val;}' Done. – Martin James Oct 05 '17 at 04:56

3 Answers3

3

You can get a pointer to the Node by subtracting the offset of next, using the offsetof operator.

struct Node *nextNode = (struct Node *)((char *)currentNode.next - offsetof(Node, next));
int nextVal = nextNode->val;

If you're using C99, which doesn't have offsetof() built in, you can use this traditional macro:

#define offsetof(st, m) ((size_t)&(((st *)0)->m))

It's technically undefined behavior (see Does &((struct name *)NULL -> b) cause undefined behaviour in C11?) but it generally works.

Barmar
  • 741,623
  • 53
  • 500
  • 612
1

Use an appropriate struct so that the restriction is inherently satisfied:

struct Node {
    void *next;
    int val;
}

No explicit pointer arithmetic required.

Martin James
  • 24,453
  • 3
  • 36
  • 60
0

I am implementing a link list as per your requirement. Hope this will help your. In this link list every pointer inside the node pointing to the next node pointer.

Please add these 3 header file at the top of your program stdio.h, memory.h and stdlib.h 

struct Node {
    int val;
    void *next;
};


void main(void)
{
  typedef struct Node NODE;
  NODE *f,*p,*q = NULL;
  int i = 1;
  /* First create your first node here */
  f = (NODE *)malloc(sizeof(NODE));
  f->next = f;
  f->val = 0;
  p = f;

/* now lets create link list with 10 nodes */
  while( i < 10 )
  {
    q = (NODE *)malloc(sizeof(NODE));
    q->next = q;
    q->val = i++;
    p->next = q->next; /* first node is pointing to the next node pointer */
    p = q;
  }

    /* search the link list and print its value */
    p = f; /* now p is pointing to the first node of the link list */
    i = 0;
    /* first print the value of first node here */
    printf("Node :%d and val = %d\n", i, p->val);
    while(p->next != p)
    {
      printf("Node :%d and val = %d\n", i++, ((NODE *)(p->next))->val);
      p = p->next;
    }
}

output of this program;

Node :0 and val = 0

Node :1 and val = 1

Node :2 and val = 2

Node :3 and val = 3

Node :4 and val = 4

Node :5 and val = 5

Node :6 and val = 6

Node :7 and val = 7

Node :8 and val = 8

Node :9 and val = 9

Abhijit Pritam Dutta
  • 5,521
  • 2
  • 11
  • 17
  • Thanks! This visualization helped. I managed to get it working, the idea was you use an offset like (&(node->ptr) - 0x4); and that will point to the beginning of a node. – Avallauch Oct 06 '17 at 03:17