2

Now I know that why pointers are used in defining linked lists. Simply because structure cannot have a recursive definition and if there would have been no pointers, the compiler won't be able to calculate the size of the node structure.

struct list{
        int data;
        struct list* next;    // this is fine
};

But confusion creeps up when I declare the first node of the linked list as:

struct list* head;

Why this has to be a pointer? Can't it be simply declared as 

struct list head;

and the address of this used for further uses? Please clarify my doubt.

Improve this question
7
  • 1
    How would you signify an empty list? Commented Jul 28, 2015 at 18:42
  • So is this is the only reason why first node is used as a pointer...? Commented Jul 28, 2015 at 18:43
  • That and every other node in a link list is a pointer. Commented Jul 28, 2015 at 18:44
  • @copo: No, because a class/struct cannot declare a non-pointer member that is the same type as itself, as it is not a fully defined type at that point. It can only declare a member that is a pointer to its own type. Commented Jul 28, 2015 at 18:44
  • 3
    No -- by declaring it as a pointer, you can move the head record by changing the list entry it points to as well Commented Jul 28, 2015 at 18:44

3 Answers 3

Reset to default
4

There's no definitive answer to this question. You can do it either way. The answer to this question depends on how you want to organize your linked list and how you want to represent an empty list.

You have two choices:

  1. A list without a "dummy" head element. In this case the empty list is represented by null in head pointer

    struct list* head = NULL;

    So this is the answer to your question: we declare it as a pointer to be able to represent an empty list by setting head pointer to null.

  2. A list with a "dummy" head element. In this case the first element of the list is not used to store actual user data: it simply serves as a starting "dummy" element of the list. It is declared as

    struct list head = { 0 };

    The above represents an empty list, since head.next is null and head object itself "does not count".

    I.e. you can declare it that way, if you so desire. Just keep in mind that head is not really a list element. The actual elements begin after head.

And, as always, keep in mind that when you use non-dynamically-allocated objects, the lifetime of those objects is governed by scoping rules. If you want to override these rules and control the objects' lifetimes manually, then you have no other choice but to allocate them dynamically and, therefore, use pointers.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Yes, it appears to me that we declare a pointer so that we can also represent an empty list which would become complicated without using a pointer.
@copo — Yes, it can be considered as a minor complication, but it can be done. Note that event the existence of an empty list is not necessarily a requirement, it depends on a particular application.
1

You can declare a list such a way

struct list head = {};

But there will be some difficulties in the realization of functions that access the list. They have to take into account that the first node is not used as other nodes of the list and data member of the first node data also is not used.

Usually the list is declared the following way

struct List
{
    // some other stuff as for example constructors and member functions
    struct node
    {
        int data;
        struct node* next;    // this is fine
    } head;
};

and 

List list = {};

Or in C++ you could write simply

struct List
{
    // some other stuff as for example constructors and member functions
    struct node
    {
        int data;
        struct node* next;    // this is fine
    } head = nullptr;
};

List list;

Of course you could define the default constructor of the List yourself.

In this case for example to check whether the list is empty it is enough to define the following member function

struct List
{
    bool empty() const { return head == nullptr; }

    // some other stuff as for example constructors and member functions

    struct node
    {
        int data;
        struct node* next;    // this is fine
    } head;
};
Improve this answer

3 Comments

So to summarize, it becomes complicated to represent empty linked lists.
@copo Simply there is no great sense to have an empty node that in fact is not used and the functions indeed become more confusing for readers of their implementations.
This is the answer. A list is a collection of nodes. A list is not a node.
0

In simple terms, if your head is the start node of the linked list, then it will only contain the address of the first node from where linked list will begin. This is done to avoid confusion for a general programmer. Since the head will contain only address, hence, it is declared as a pointer. But the way you want to declare is also fine, just code accordingly. Tip: If you later on want to make some changes in your linked list, like deletion or insertion operations at the beginning of the linked list, you will face problems as you will require another pointer variable. So its better to declare the first node as pointer.

Improve this answer

2 Comments

True. Also to represent empty lists.
yes.. indeed then you can simply make the start point to the updated node :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.