CODEWITHSUNDEEP
cpointerslinked-list
Avallauch
Avallauch

Reputation: 65

Linked list, but every "next" pointer points to the next node's "next" pointer

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?

Upvotes: 0

Views: 986

Answers (3)

Barmar
Barmar

Reputation: 780842

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.

Upvotes: 3

Abhijit Pritam Dutta
Abhijit Pritam Dutta

Reputation: 5591

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

Upvotes: 0

Martin James
Martin James

Reputation: 24847

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

struct Node {
    void *next;
    int val;
}

No explicit pointer arithmetic required.

Upvotes: 1

Related Questions