3
$\begingroup$

So I have a pic which I think illustrates my confusion:enter image description here

the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, which marked box does it refer to in my pic?

$\endgroup$
3
+100
$\begingroup$

You're right, there are many different definitions of a List/Linked List. No one definition is correct nor incorrect. This answer is a bit long-winded, but having a backstory on the logic behind lists is worthwhile.

History of Lists

Let's start with the definition of a List, in Computer Science, as described by the developers of the structure (Newell, Shaw, and Simon [1]) for their Information Processing Language [1] in 1957. It was initially developed as a method for flexible memory assignment in the Logic Theory Machine.

Definition of Lists (1957)

$Lists$ : Lists are the general units of information in the memory. A list consists of an ordered set of items of information. Any item on a list may be either a list or an element, and these are fundamentally different types of unit. [1]

Formation of Lists

To form a list, we use a set of location words, each containing two addresses. One address locates an item on the list, the other address locates the next location word. [1]

Location words are JOHHNIAC [2][3] words that contain two addresses.

The left address is the address of the next location word, the right address is the address of the item on the list. [1]

Here is an example of a List containing three elements: Fig. 4 [1]

You can see in this example, the items link to nothing. This is why items are "on the list", they are attached to the list but not a direct piece of the list. Saying the first element is the "head" of a list makes no sense in this context. They are not part of the list at all.

The Head of a List

Newell and Shaw describe the head of a list as the first location word in the list [1]. Thus, in a strict sense, the head has an address to the first element on the list, while itself is the first location word in the list.

This representation of a list was traditionally followed. This can even be seen in the LISP [4] programming language invented by John McCarthy. Also check the LISP 1.5 Programmer's Manual [5].


Definition of Lists (1964)

Soon came along the idea of putting "symbols" in the list, rather than attaching them on the list. Wilkes [6] describes the registers (nodes) of a list as having two parts (similar to Newell, Shall, and McCarthy) in his paper Lists and why they are useful [6]:

  1. The CAR, left free, and may be used to hold a symbol. Alternatively, can store an address memory. [6]

  2. The CDR (pronounced "cudder") contains an address pointing to the next register in the list. [6]

Here is a simple example of a list under Wilkes' definition, with symbols in the list:

enter image description here

[6]

Head of a List

A list must start somewhere, and the address of its first register is stored in a sequence of fixed memory registers known as base registers. [6] Normally, it is not necessary to show the base registers in diagrams of lists. [6]

With Base registers [6]:

enter image description here

Typical representation without base registers [6]:

enter image description here

In this definition, the head of a list is more in line with your first picture, it is an external register, not part of the list itself that merely contains the address to the first register in the list.


You may be wondering why I chose these examples instead of giving you the simple wiki definition [7]:

The head of a list is its first node.

This definition is left ambiguous most likely intentionally because there are many different implementations. We can now discuss the head in regards to the two examples I presented.

The Sentinel Node (wiki [8])

Of these two examples, the latter is a list using a sentinel node (the base registers), the former does not. When using a sentinel, the head is the sentinel, the first node in the list, even though the sentinel contains no elements or addresses to elements. Clearly without a sentinel, the head is simply the first node in the list.

Internal vs External Storage (wiki [9])

Of these two examples, the latter is an example of internal storage, the former is an example if external storage. With internal storage you could attempt to think of the head as the first element in the list (though I wouldn't recommend it, because it contains also the address of the next node), because the element is in the node. With external storage, the head contains a pointer (memory address) to the first element of the list and a pointer to the next node in the list.

Nodes vs Elements

Much of the confusion about lists comes from the fact that many people mix up an element of a list with a node of a list. To prevent any confusion, whether you're using internal/external storage or a sentinel node or not, in my opinion, it's best not to refer to the elements (data stored in the list) as nodes of the list. Conceptually they are distinct.

The node of a list should thus contain two parts (as previously mentioned), the element or address, and an address to the next node. In programming, even if the two are not separated in code, conceptually they should be. Therefore when Wikipedia refers to the head of a list, it refers to the first node in the list. That node, then contains element data and an address to the next node.


  1. Programming the logic theory machine by A. Newell and J. C. Shaw (1957, pp. 233)
  2. The History of the JOHNNIAC by F. J. Gruenberger (1968) (available here for free, no sign-in required)
  3. Johniac by E. Thelen (accessed Oct 29, 2017, last updated Aug 6, 2015)
  4. LISP I Programmer's Manual by J. McCarthy et al. (1960)
  5. LISP 1.5 Programmer's Manual by J. McCarthy et al. (1962, 2nd ed)
  6. Lists and why they are useful by M. V. Wilkes (1964, pp. 1-5)
  7. https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature (accessed Oct 29, 2017)
  8. https://en.wikipedia.org/wiki/Linked_list#Using_sentinel_nodes (accessed Oct 29, 2017)
  9. https://en.wikipedia.org/wiki/Linked_list#Internal_and_external_storage (accessed Oct 29, 2017)
$\endgroup$
  • $\begingroup$ I would not say it's a confusion but a different level of abstraction. A linked list is an implementation of an abstract data type. At the level of the abstract data type, there are no "nodes". At this level, the only thing the "head of a list" could possibly be is an element. $\endgroup$ – Derek Elkins Jun 14 '17 at 6:49
  • $\begingroup$ Yes you could remove that abstraction. Then you have to deal with internal vs external storage though. Is the head now the first element, or an address to the first element? In my opinion, abstracting it simply to the first node, which then contains an element or address is easier. Then there is no confusion: "is the head a pointer or an element?", the head is the first node in the list. $\endgroup$ – ryan Jun 14 '17 at 6:59
1
$\begingroup$

Head is a reference to the first object of class or struct that represent the link of the specified list. The object generally contains both data and link. So head is pointing to both data and next.According to your image, 2nd is the correct answer.

$\endgroup$
  • 2
    $\begingroup$ [citation needed]. Also, do you mean "head refers to..." Saying "head is a reference" sounds a lot like "head is a pointer". $\endgroup$ – David Richerby Jun 13 '17 at 12:47
1
$\begingroup$

Does head refer to a node with both a data and next, or only a node with next?

Head refers to the first node of your linked list. It can be a reference from an empty node which is in your words "only a node with next". Or it can be a variable that points to the first node of your list.

Practically, this would make a difference because the head will not always remain the same, so in your picture it might make sense to label the leftmost thing as the 'pointer to the head' and the first node of the linked list as the head. For example,

a = new Node(1);
b = new Node(2);
a.next = b;
head = a; // at this point, both a and head are pointers to the beginning of our linked list
// now we want to add c to the beginning of the linked list
c = new Node(3);
c.next = a;
head = c; // now c and head are pointers to the beginning of our linked list, but not a

So the concept of a 'pointer to the head' is important so that you can consistently have a pointer to beginning of your linked list (it will have to be updated every time you delete or add something to front of the linked list)

EDIT: thanks to David for pointing out in the comments that the distinction between the head and pointer to the head should be made clearer

$\endgroup$
  • 4
    $\begingroup$ Could you give a citation backing up your claim? We talk about the first element of a list much more often than we talk about a pointer to it, so it would seem more natural to use "head" for the first element and "head pointer" for a pointer to it, rather than "referent of the head" for the first element and "head" for the pointer. (Especially given that a list has only one first element but we might have multiple pointers to it; I've only heard people say "the head", not "a head"..) $\endgroup$ – David Richerby Jun 13 '17 at 12:48
  • $\begingroup$ I think you are correct, thanks for pointing that out. I'll update my answer. $\endgroup$ – Peeyush Kushwaha Jun 13 '17 at 13:58
0
$\begingroup$

Your confusion is understandable. As others have said, strictly speaking the head is the pointer to the first node in the list. BUT: Procedures for list manipulation - insertion, deletion in particular - can be simplified by always putting a special stub node at the start of the list [basically, this lets you eliminate the 'is this the first node?' special-case test]. When this is done, the stub node (or its 'next' pointer) is sometimes called the head instead.

$\endgroup$
  • 2
    $\begingroup$ "strictly speaking the head is the pointer to the first node in the list" [citation needed] We talk about the first node much more than we talk about the pointer to it. Why would we have a really short word for the pointer ("head", by your claim) but not for the first entry? $\endgroup$ – David Richerby Jun 13 '17 at 14:20
  • $\begingroup$ +1 for mentioning that procedures can be simplified by stub node $\endgroup$ – Peeyush Kushwaha Jun 13 '17 at 17:30
-1
$\begingroup$

Head in case of singly linked list is the pointer which points to the first node of the linked list. So it's not a node, it's a pointer reference.

$\endgroup$
  • 3
    $\begingroup$ [citation needed] $\endgroup$ – David Richerby Jun 13 '17 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.