1

I'm having trouble understanding a piece of C code that represents a linked list structure. The skeleton of the struct looks like this:

struct r{
   r *next;
   r **prev; 
   data *d;
}
struct r *rlist;

rlist can be filled by calling the following function: (skeleton only)

r* rcreate(data *d){
     struct r *a = xmalloc(sizeof(*r))
     a->d = d;
     a->next = rlist;
     a->prev = &rlist;
     if (rlist)
         rlist->prev = &a->next;
     rlist = a;
     return a;
}

How do I go about using this data structure? e.g. how to traverse rlist ?

Edit: here is the function for deleting a node in the linked list

void rdestroy(struct r *a){
     if (a->next){
         a->next->prev = a->prev;
     }
     *a->prev = a->next;
      destroy(a->d); /* destroy is defined elsewhere */

}
Improve this question
2
  • 1
    why are u using prev as double pointers , u are making it complicated Commented Nov 20, 2013 at 6:20
  • 1
    @cyberworm I have no idea why the code uses double pointers, it's part of a larger program that I shouldn't modify. Commented Nov 20, 2013 at 6:27

4 Answers 4

Reset to default
1

Double prev pointer seems to allow traversing list in one direction only, while allowing easy deletion (because even though you can't access the previous element (easily), you can access the next pointer of previous element, and set it to new correct value when deleting a node.

Without seeing other related functions, it's hard to see why it is done this way. I've not seen this done, and can't immediately think of any really useful benefit.

I think this allows having simpler node deletion code, because node does not need to care if it first or not, because node's prev pointer will always have non-NULL value to a pointer it needs to modify when deleting itself. And same simplicity for insertion before a current node. If these operations are what dominate the use pattern, then this could be seen as minor optimization, I suppose, especially in older CPUs where branches might have been much more expensive.

How to traverse list

This was the question, right? You can only traverse it forward, in a very simple manner, here's a for loop to traverse entire list:

struct r *node;
for (node = rlist ; node ; node = node->next) {
    // assert that prev points to pointer, which should point to this node
    assert(*(node->prev) == node); 

    // use node
    printf("node at %p with data at %p\n", node, node->d);
}

Example insertion function

This example insertion function demonstrates how insertion before a node needs no branches (untested):

struct r *rinsert(struct r *nextnode, data *d) {

     // create and initialize new node
     struct r *newnode = xmalloc(sizeof(struct r));
     newnode->d = d;
     newnode->next = nextnode;
     newnode->prev = nextnode->prev;

     // set next pointer of preceding node (or rlist) to point to newnode
     *(newnode->prev) = newnode;

     // set prev pointer of nextnode to point to next pointer of newnode
     nextnode->prev = &(newnode->next);

     return newnode;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thanks. i see your reasoning about node deletion. (i updated the question with the node deletion code. rcreate and rdestroy are the only utility functions i have about this data structure, besides the code for modifying the content of data) I will try implementing your method.
1

There's no good reason to have r ** next in that structure. It's for a double linked list. So if this thing is created you have it assigned

thisList = rcreate("my data")

now you could start with traversing it while (thisList->next) thisList = thisList->next. ...

Improve this answer

2 Comments

Thanks. I thought about using a while loop, but I still don't fully understand how the linking works.
Well usually they show you boxes |prev | <- |data | -> | next |
0

Your code has many syntactical errors in it, probably because (as you say) it is a "skeleton," so it is hard to parse what the author (whether it was you or someone else) actually intended this code to do.

A simple (doubly) linked list structure looks like this:

struct node {
  struct node *next, *prev; // pointers to the adjacent list entries
  int data; // use whatever datatype you want
};

struct node *list = NULL; // the list starts empty

void add_entry(int new_data) {
  struct node *new_entry = malloc(sizeof(struct node));
  // note that in the above line you need sizeof the whole struct, not a pointer

  new_entry->data = new_data;
  new_entry->next = list; // will be added to the beginning of the list
  new_entry->prev = NULL; // no entries currently front of this one
  // in general a NULL pointer denotes an end (front or back) of the list

  list->prev = new_entry;
  list = new_entry; // now list points to this entry
  // also, this entry's "next" pointer points to what used to
  // be the start of the list
}

Edit: I'll say that if you want us to help you understand some code that is part of a larger program, that you did not write and can't modify, then please post the relevant code in a format that is at least syntactical. As others have said, for example, the use of prev in the code you posted is indecipherable, and it isn't clear (because there are other similarly confusing syntactical problems) whether that was in the original code or whether it is an error introduced in transcription.

Improve this answer

Comments

0

Yang, I am not sure how comfortable you are with pointers in general. I suggest taking a look at few other linked-list implementations, it might just do the trick.

Take at look at this Generic Linked List Implementation.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.