What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online

Question

So I have a pic which I think illustrates my confusion:

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?

Answer 1

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: [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:

[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]:

Typical representation without base registers [6]:

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)

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.