linked list

Answer 1

If you are looking to better understand the basics of linked lists, take a look at the following document:

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Answer 2

In memory your items are linked by pointers in the list structure

item1 -> item2

Why not make the list structure part of your item?

Then you allocate a product item, and the list structure is within it.

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct list_t list; // contains the pointers to other product data in the list
}product_data_t;

Answer 3

You're calloc'ing space for your list_t struct, just pointers to list head and tail, which isn't what you want to do.

When you add to a linked list, allocate space for an actual node in the list, which is your product_data_t struct.

Answer 4

You're allocating the wrong chunk of memory. Instead of allocating memory for each list element, you're allocating for the list head and tail.

For simplicity, get rid of the separate structure for the head and tail. Make them global variables (the same scope they're in now) and change them to be listhead and listtail. This will make the code much more readable (you won't be needlessly going through a separate structure) and you won't make the mistake of allocating for the wrong struct.

You don't need a tail pointer unless you're going to make a doubly linked list. Its not a major element to add once you create a linked list, but not necessary either.

Answer 5

I am not writing the code here but you need to do the following:

• Create and object of list, this will remain global for the length of program.
• Malloc the size of product _ data _ t.
• For first element (head is NULL), point head to the malloced' address.
• To add next element, move to the end of list and then add the pointer of malloced address to next of last element. (The next of the last element will always be NULL, so thats how you traverse to end.)
• Forget tail for a while.

Answer 6

Go STL route. Declaring linked lists should be agnostic of the data. If you really have to write it yourself, take a look at how it is implemented in STL or Boost.

You shouldn't even keep the *next pointer with your data structure. This allows you to use your product data structure in a various number of data structures - trees, arrays and queues.

Hope this info helps in your design decision.

Edit:

Since the post is tagged C, you have equivalent implementations using void* pointers that follow the basic design principle. For an example, check out:

Documentation | list.c | list.h

Answer 7

Arguably you want your list data structure to be external to the data that it stores.

Say you have:

struct Whatever
{
   int x_;
}

Then your list structure would look like this:

struct Whatever_Node
{
   Whatever_Node* next_
   Whatever* data_
}

Ryan Oberoi commented similarly, but w/o example.

Answer 8

If you are learning C pointer theory this is a good exercise. Otherwise, it feels like too much indirection for code that is not generic (as in a library).

Instead of allocating a static 128 byte character string, you might want to do some more pointer practice and use an allocated exact length string that you clean up at exit.

Academically, kungfucraigs' structure looks more generic then the one you have defined.

Answer 9

In your case the head and tail could simply point to the beginning and end of a linked-list. With a singly linked-list, only the head is really needed. At it's most basic, a linked-list can be made by using just a struct like:

typedef struct listnode
{
   //some data
   struct listnode *next;
}listnodeT;

listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;

and as long as list is always pointing to the beginning of the list and the last item has next set to NULL, you're fine and can use current_node to traverse the list. But sometimes to make traversing the list easier and to store any other data about the list, a head and tail token are used, and wrapped into their own structure, like you have done. So then your add and initialize functions would be something like (minus error detection)

    // Initialize linked list
void initialize(list_t *list)
{
    list->head = NULL;
    list->tail = NULL;
}

void add(list_t *list, int code, char name[], int cost)
{
    // set up the new node
    product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t));
    node->code = code;
    node->cost = cost;
    strncpy(node->product_name, name, sizeof(node->product_name));
    node->next = NULL;

    if(list->head == NULL){ // if this is the first node, gotta point head to it
        list->head = node;
        list->tail = node;  // for the first node, head and tail point to the same node
    }else{
        tail->next = node;  // append the node
        tail = node;        // point the tail at the end
    }
}

In this case, since it's a singly linked-list, the tail is only really useful for appending items to the list. To insert an item, you'll have to traverse the list starting at the head. Where the tail really comes in handy is with a doubly-linked list, it allows you to traverse the list starting at either end. You can traverse this list like

// return a pointer to element with product code
product_data_t*  seek(list_t *list, int code){
   product_data_t* iter = list->head;
   while(iter != NULL)
       if(iter->code == code)
           return iter;
       iter = iter->next;
   }
   return NULL; // element with code doesn't exist
}

Often times, the head and tail are fully constructed nodes themselves used as a sentinel to denote the beginning and end of a list. They don't store data themselves (well rather, their data represent a sentinel token), they are just place holders for the front and back. This can make it easier to code some algorithms dealing with linked lists at the expense of having to have two extra elements. Overall, linked lists are flexible data structures with several ways to implement them.

oh yeah, and nik is right, playing with linked-lists are a great way to get good with pointers and indirection. And they are also a great way to practice recursion too! After you have gotten good with linked-list, try building a tree next and use recursion to walk the tree.