1

To get some practice in C, I'm writing some basic functions for operating on a linked list of ints. I started out with functions that accepted as a "list" a pointer to the head node. Now, I find myself running into more and more occasions when I either need to limit the spec of the function more than I would like, or I need to use a pointer to a pointer to the head node to allow for alteration/removal of the head node in a way that is consistent with the way I alter/remove other nodes.

Is it preferable to have all functions accept a "list" in the same form, as a pointer to a pointer, rather than having some accept just a pointer to the node? Or should I perhaps change the way I think about altering/removing the head node to avoid needing to change the head pointer?

For example, if I write a remove function that removes all instances of the given int, and the head node's value is that int, I see a few obvious choices:

  1. I can pass in a pointer to a pointer and move the head pointer to the next node not being removed.

  2. I can pass in a pointer and I can move the value of the next node not being removed, say node x, into the head node and remove node x along with any other nodes that hold the value to be removed. This fails in the case that the list consists of only a single node that contains the value, and so I have to limit the spec to exclude this case.

In the case that I pass in a pointer to a pointer for this function, should I now change all other functions to accept a pointer to a pointer?

Are there standards for things like this or is it up to me? (Pretending of course that this code matters in some fashion to someone other than me and would, in that fantasy land, be used by other people without knowledge of the inner workings of the functions, beyond their signatures.)

  • What does the linked list implementation actually require? Is the additional layer of indirection necessary? – Robert Harvey Oct 20 '14 at 1:19
  • OK, I saw your edit. So I have some questions. The first is, will a pointer in a particular node ever need to point to more than one other node? The second is, will a pointer ever have to point to anything except some other node? The third is, it sounds like you haven't figured out how to terminate the linked list; that is, how do you define the last node in the list? – Robert Harvey Oct 20 '14 at 1:56
  • A pointer inside a node points to one node at a time, the next in the list, but changes which node it points to in several functions. I only use pointers that point to a single node right now, if that answers the second question. The last node in the list is just that for which the next pointer is NULL. – bazuzi Oct 20 '14 at 4:11
  • For internal functions, pointer-to-pointer is typical. For public functions, the pointer shall be hidden by the struct. – o11c Oct 20 '14 at 14:51
  • @o11c: That's a little vague. – Robert Harvey Oct 20 '14 at 15:01
6

There are three choices that I can see.

  1. Use a "list head" struct that doesn't contain any data, but simply points at "the list" (as pointed out by Jonathan Eunice in a comment, this means you have a conventient place for any extra data you may eventually want to collect and means you no longer need pointers-to-pointers)
  2. Use the pointer-to-pointer you have identified
  3. Always return the "new" list value and make use of the returned value.

As an example of the third model:

struct list { int val; struct list *next; }

struct list *drop_head(struct list *lst)
{
  struct list *rv = lst->next;
  free(lst);
  return rv;
}

void blah()
{
  struct list *my_list;
  /* imagine interesting code here */
  my_list = drop_head(my_list);
  /* imagine more interesting code here */
}
  • 3
    If you use option 1 (a differentiated "list head" struct) you won't need handles (pointers to pointers). You will also have a very convenient place to put other data you may eventually want to efficiently track (e.g. list length, timestamp of last update, pointer to last node in the list, etc.) – Jonathan Eunice Oct 23 '14 at 18:07
0

I wrote a similar program for the linked list in C, you need to get pointer to pointers in all functions to make it consistent across all function, because removing and create a new head or tail would require a pointer to pointer. However you can make a enum for the tail and head pointers. example from my code:

enum LIST_PTR {
    LIST_HEAD =0,
    LIST_TAIL
};
struct node {
  struct node *NextNode; // Pointer to next node
  int data; // node data.
};

void enqueue(struct node** head, struct node** tail,int data);
int dequeue(struct node** head, struct node** tail);
int getCount(struct node** head, struct node** tail);
int destroyList(struct node** head, struct node** tail);

then you can declare and use or linked list in following manner

struct node* my_list[2];
my_list[0]=my_list[1]=NULL;

getCount(&my_list[LIST_HEAD],&my_list[LIST_TAIL]);

make sure you assign the pointers to NULL or i am telling you by experience, you will have a seg fault of which you will have no idea!

  • What's eag? Prefixes should have an understandable naming scheme. – raptortech97 Oct 22 '14 at 20:40
  • its just an example code, its basically snippet of my code. prefixes doesnt matter here – Aunn Raza Oct 22 '14 at 21:15
  • @AunnRaza: If the confusing prefix doesn't matter, why not remove it? – Michael Shaw Oct 24 '14 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.