Linked List Logic

Question

I am having a little trouble understanding the flow of a linked list.

I have these type definitions for my list and its nodes.

typedef struct node node_t;

struct node{
    data_t data;
    node_t *next;
};

typedef struct {
    node_t *head;
    node_t *foot;
} list_t;

list_t *insert_at_foot(list_t *list, data_t value) {
    node_t *new;
    new = malloc(sizeof(*new));
    assert(list!=NULL && new!=NULL);
    new->data = value;
    new->next = NULL;
    if(list->foot==NULL){
        //this is the first insertion into the list
        list->head = list->foot = new;
    }else{
        list->foot->next = new;
        list->foot = new;
    }
    return list;
}

Specificly this code below

if(list->foot==NULL){
    //this is the first insertion into the list
    list->head = list->foot = new;
}else{
    list->foot->next = new;
    list->foot = new;
}

I get that we allocate the head and the foot to the node "new" as it is the first node, but I don't understand the following lines. It would seem to me that if we are allocating this new node to the end of the list (to the foot),

list->foot->next = new;

Should be,

list->foot->next = NULL;

I just don't get the point of assigning both the foot pointer and its next pointer to the same node (new)

This has been bugging me as the concept is quite easy to understand.

Answer 1

What you have hit on is the difference between a simple linked-list and a refinement called a circular linked-list. As vagueness describes, in a simple list, you generally keep an additional 1 or 2 pointers (HEAD) or (HEAD, TAIL), respectively that hold the beginning node (HEAD), and the current ending node (TAIL) of the list. What is the point of having HEAD/TAIL?

The simple answer is two-fold. (1) it allows permanent reference for adding nodes either at the beginning or end of the list, and (2) they provide begin and end points for iterating through the list. But do you have to have them to implement a linked-list? No.

A circular linked-list eliminates the need to keep any HEAD,TAIL pointer(s) by having your end->next point to first (thus the name circular linked-list. I have used both and quickly abandoned the HEAD,TAIL simple list in favor of a circular linked-list. To get the benefits of both you can add and additional pointer node->prev and make the list a circular double-linked-list which retains the ability to access the HEAD & TAIL nodes without iteration.

Is a circular list harder to implement than a simple list -> No, it just takes a different add_node function. Let's take a look. A diagram showing the relationships and differences between simple and circular lists helps (double-linked-list shown):

             Tail                 Current                Head
         (node->prev)              node              (node->next)
        +------------+        +------------+        +------------+
        |   payload  |        |   payload  |        |   payload  |
        +------------+        +------------+        +------------+
+<------|   prev     |<-------|   prev     |<-------|   prev     |<------+
|       +------------+        +------------+        +------------+       |
|  +--->|   next     |------->|   next     |------->|   next     |--->+  |
|  |    +------------+        +------------+        +------------+    |  |
|  |                                                                  |  |
|  +<--------------------<---------------------<----------------------+  |
|                                                                        |
+------------------------>--------------------->------------------------>+

If you look closely, you will see that a simple and circular list are exactly the same for all practical purposes, however, in the case of the simple list, you have to keep track of your HEAD,TAIL pointers, but for the circular list, the logic of the implementation keeps track of them for you. That's the difference, and that's why the answer to your question: the point of assigning the HEAD,TAIL pointers? is simply to provide for insertion of new nodes and begin and end points for iteration. If you are smart in your implementation, then you never have to worry about assigning them, your list logic keeps track of them for you. With that in mind, here is an example of implementing the circular list without needing to keep track of HEAD,TAIL.

For your data structure you will typically have:

typedef struct list {
    char *data;
    struct list *prev;
    struct list *next;
} list;

Then you have your functions to create node and to insert node at the end. Note: the insert node function calls create node, but it can all be done in insert node if you choose.:

list *create_node (char *str) {

    list *node = NULL;

    node = malloc (sizeof (struct list));   /* allocate memory for new node      */
    node-> data = strdup (str);             /* allocate and save payload data    */

    return node;                            /* return node poiter to add to list */
}

list *insert_at_end (list **ll, char *str) {

    /* create the node and allocate memory for node and payload
    if no list, then create and assign as list address
    else, insert new node at end of list */

    list *node = NULL;              // create a new node pointer for list

    node = create_node (str);       // allocate new node and fill payload

        /* now just Wire/Rewire list pointers to accept node */

    if (!*ll) {                     // this is the first node

        node-> next = node;            // circular linked-list
        node-> prev = node;            // set next, prev = node
        *list = node;                  // set *list = node (adding node to list)

    } else {                        // add - insert new node at end

        node->next = *ll;              // set node->next to list
        node->prev = (*ll)->prev;      // set node->prev to list->prev
        node-> prev-> next = node;     // set (old end)->next to this node
        (*ll)-> prev = node;           // set list->prev to node
    }
    return node;                    // return pointer to current node for convenience
                                    // (immediate reference) and to test success
}

In your main(), you simply have something similar to:

list *mylist = NULL;
int i = 0;

// add data to your list (example using argv entries)
for (i = 0; i < argc; i++)
    insert_at_end (&mylist, argv[i]);
...

Hopefully this helps your understanding. Whether you use a simple or circular, single or double linked-list, just make sure you understand the logic and why each assignment is being made. It is just a game of pointers. They are all simple data structures, but they do require a steep, but short, learning curve. Take the time to learn it once and they will serve you well from then on. There are many tutorials and howto's on the web for simple and circular lists. Now knowing the difference, it will make finding what you need much easier.

Answer 2

Inserting at the end of a linkedlist is O(n) if we don't have the tail of list. If we just have the head of list we should iterate through the list and find the end and insert the item at the end of the list( in case we want to preserve the insertion order). To avoid this people usually keep the tail of list. For example if your list is 1->2->3 and you want to add 4 in the list. The head is 1 and the tail is 3 in this case. so

list->foot->next = 4

means that our list will be 1->2->3->4 and the next line list->foot = new; assigns the tail(foot) to 4 to make sure that for another insertion we have the updated tail(foot).