1

While studying data structure I came up with the Linked List section, particularly the head node and tail node section.

From what I was read an taught, many users of C tend to use only Node *head;.

But there was a part where using the following code was recommended to be used:

typedef structure _node node;

struct _node{
  int data;
  Node *next;
}

typedef structure list {
  Node *head;
  Node *tail;
  int size;
} List;

As a person who has just started studying C and data structure, I found it more understandable when writing it like this, but since the teacher told us that most people do not write it like this but just use Node *head, I was curious on knowing what others actually used in reality.

Do developers and C users really use just one line, or do they use it like the code written above?

EsmaeelE
  • 2,331
  • 6
  • 22
  • 31
Learner_15
  • 399
  • 2
  • 11
  • 1
    Note that you should not, in general, create function, variable, tag or macro names that start with an underscore. Part of [C11 §7.1.3 Reserved identifiers](https://port70.net/~nsz/c/c11/n1570.html#7.1.3) says: — _All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use._ — _All identifiers that begin with an underscore are always reserved for use as identifiers with file scope in both the ordinary and tag name spaces._ See also [What does double underscore (`__const`) mean in C?](https://stackoverflow.com/q/1449181) – Jonathan Leffler Jan 22 '20 at 08:35

1 Answers1

2

The data structure depends on whether you want to optimise for specific use cases. For example, if you have a linked list, where the elements shall be inserted mostly before the first element, then it may be superfluous to maintain a tail. If, however, elements shall be inserted mostly at the end, it makes sense to maintain a pointer to the tail instead of running through the complete list again and again whenever an element shall be inserted. And if you want to use your list for a First-In-First-Out (FIFO) use case, then it is beneficial to have both the head and the tail available directly, too.

Similarly, whether you store the size (redundantly) of the list might depend on how often you want to access that value. Since it can be calculated, you could derive the size on demand. If you access it rather often, or if you have long lists, then storing the value separately makes sense.

So it depends, and there may be other factors to consider as well.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Stephan Lechner
  • 34,891
  • 4
  • 35
  • 58
  • I think mentioning the FIFO concept as a typical example for the head/tail(/size) structure would be helpful. And maybe the concept of "caching" information which could be determined by lengthy list analysis, especially the size. – Yunnosch Jan 22 '20 at 07:55
  • IMO The overhead is so minimal (comparing to other list operations) and there is usually no room for such a micro optimizations. Sometimes it even much better too keep more information in the structure – 0___________ Jan 22 '20 at 08:14
  • 1
    Your example shows a singly linked-list (only `next` pointers). If you make a doubly linked list (each `Node` also has a `Node *prev` pointer), then it's extremely common to maintain a `tail` pointer too. – Edd Inglis Jan 22 '20 at 09:53