How would you define the "tail" of a linked list?

General Discussion
1

Has anyone ever heard of the “tail” of a list referring to the last element? I just seen two popular JavaScript algorithms courses where the instructors were calling the last element of a linked list the “tail”.

Previously, I’ve only heard “tail” being used to refer to everything but the first element, especially in languages that are based on lists.

In Elixir, the hd (head) and tl (tail) functions produce this:

my_list = [1, 2, 3, 4, 5]
hd(my_list) #=> 1
tl(my_list) #=> [2, 3, 4, 5]

In those list-based languages, it’s common to use recursive functions on the lists, processing the head on each loop and sending the tail into the function again until it’s empty.

As far as I can tell, the first language to use linked lists was IPL from 1956. I skimmed through the user manual but didn’t see anything there, and it doesn’t seem possible to search the document. Lisp (LISt-Processing language) was created in 1958. It uses the terms car (head) and cdr (tail), and the cdr is everything but the first element.

Here’s how it works in four languages that feature linked lists: Haskell, Elixir, Erlang, Common Lisp.

linked lists
linked lists944×330 19.1 KB

I suspect that it’s probably incorrect to call the last item of a linked list the “tail”, but I’m wondering if there are some situations where it would be considered correct. Does anyone know?

2

Just poking around, it appears the two uses are distinct for arrays vs. linked lists. For arrays tail seems refer to everything but the first element, and for linked lists it seems to refer to the last node.

3

I’ve generally understood tail of a linked list as referring only to the very last node / element (which could actually be the same as the head in a single node list). On Wikipedia the linked list article section on nomenclature says it could refer to either the last element or to the rest of the list after the head, but unfortunately doesn’t offer any citation on that definition.

Etymologically the list ‘tail’ may have originated as referencing all elements past the first but I think by common usage it can be a direct reference to the endpoint and still be considered “correct”, in the same way words like awful have semantically changed over time. My google image search for linked list tail shows almost every diagram with the final node labeled as the tail. Unfortunately this leaves tail with a bit of ambiguity but such is modern language. You can fortunately get to either definition relative to the rest of the list (by ‘the last node’, or ‘all nodes after the head’) if you need to be explicit and clear.

To me it seems more often useful to refer directly to the last node, e.g. if you have a pointer to the tail of a linked list you can append a node in O(1) time. I’m sure there are cases when the other definition is also useful though.

1 Like
5

I guess it must be interchangeable, or maybe it varies by language?

Here’s a runnable example of how it works in Elixir:

The version of the function where the arguments match will run. So passing in an empty list is the base case. If the list is not empty, the head and tail are destructured as they get passed in.

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)
1 Like
6

In the classes I took the tail in a linked list was the last node, but now I’m thinking sometimes it wasn’t used. It could of been for doubly-linked lists… ok, I’m no help, I’ll have to look through my repos.