Linear Linked List - valid/common terminology?

Question

Is speaking of a linear linked linked in contrast to a circular linked list a valid / common term? For some examples I'm posting to my students I need to distinguish between both and don't want to use terms which don't actually exist!

Answer 1

I would say linear or open linked lists are valid terms, however, I have only heard them mentioned in context where they have to be explicitly differentiated from circular linked lists, otherwise a "linked list" with no other qualifier is assumed to be linear.

Answer 2

I would simply call them "non-circular".

Just for reference, Lisp defines "proper lists" as lists that are terminated by the empty list. "Improper" lists can be "circular lists" or "dotted lists" (lists that are not terminated by the empty list but by some other atom).

Answer 3

I call those "singly-linked lists" although that usually just distinguishes them from "doubly-linked lists." A circular linked list can be either singly-linked or doubly-linked so technically it doesn't distinguish between them. However I don't think I've ever heard of someone refer to a circular linked list by any other name (except perhaps with additional quantifiers, i.e. - circular doubly-linked list).

Answer 4

I call them

1) Singly linked list [1]->[2]->NULL

2) Doubly linked list NULL<-[1]<=>[2]<=>[3]->NULL

3) Circular linked list [1]->[2]->[1]

You can then use the combination to make your own terms. However the descriptions of the problem or the explanation to a problem will clarify the actual meanings of the terms, in case there be any doubts.

Answer 5

The terms you are looking for are 'cyclic' and 'acyclic', and apply to all graph data-structures. As @Svante mentioned, sometimes you will see 'proper', 'improper', and 'circular'.

Unqualified, a reference to a List implies 'acyclic', so 'non-circular' is uncommon and rather crude.

Ultimately if your students are mature enough, 'cyclic' and 'acyclic' are preferred as your students will meet these terms again when generalizing from Lists to Trees to DAGs to Graphs.