• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 444
  • Last Modified:

Link list in c

I tried to create a new implementation of a link list using except head also the tail of the struct.

The problem is that I don’t  understand  how to use the NODE *tail;
And what is the profit to use it?

The struct is presented bellow :

typedef struct node
      int data;
      struct node *next;  

typedef struct list
         NODE *head;
         NODE *tail;
         int size;      
2 Solutions
mccarlIT Business Systems Analyst / Software DeveloperCommented:
Usually, you would use the "tail" pointer if you were implementing a doubly-linked list, but for that you would also need a "previous" pointer to be defined in your NODE struct (and you would need the associated implementation to track things properly).

Therefore, the usefulness of the "tail" pointer is questionable. One possibility though, was if this particular list was likely to be used in a situation where a large number of operations occur with respect to the last element in the list, ie. the "tail". For example, if inserting new elements to the end of the list was a reasonably frequent operation, then yes, explicitly tracking the "tail" element (rather than having the walk the list everytime you wanted to append an element to the list) would make sense.
Julian HansenCommented:
There is nothing wrong with your declaration.

The LIST structure (as I understand your code) is for maintaing the list of NODE's.

If you did not have a tail pointer and you wanted to add something to the end of the list then to do so you would have to iterate through the list until you hit a NULL next pointer before being able to add an element.

By keeping a head and a tail you are easily able to add to the end of the list

Something like this
NODE * newnode = malloc(sizeof(NODE));
newnode->data= 10;
newnode->next = null;
list->tail->next = newnode;
list->tail = newnode;

Open in new window

Which is more efficient than iterating through the list.

So if you are implementing a FIFO (first in first out list) you would need the tail so you could add latecomers to the back of the queue.

If you are implementing a LIFO list then you don't need a tail because you are pushing latecomers to the front of the queue.

If you are implementing a sorted list then you also don't need a tail because you are iterating through the list anyway to find the insertion point.

So the usefuleness of the tail depends on how you want to use the list.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now