Linear Link List - Valid / General Terminology?

Question

Talking about a linear relationship, connected as opposed to a circular linked list, current / general term? For some examples that I send to my students, I need to distinguish between one and the other, and I do not want to use terms that do not really exist!

Answer 1

I would just call them "non-circular."

For reference only, Lisp defines "appropriate lists" as lists that end with an empty list. “Wrong” lists can be “circular lists” or “dotted lists” (lists that do not end with an empty list, but with some other atom).

Answer 2

I would say that linear or open linked lists are valid conditions, but I only heard them mentioned in a context where they should be clearly differentiated from circular linked lists, otherwise a “linked list” without another qualifier is considered linear.

Answer 3

I call these “singly linked lists”, although this usually distinguishes them from “doubly linked lists”. A circular linked list can be either simply connected or doubly connected, so technically it does not distinguish between them. However, I don’t think I’ve ever heard that anyone refers to a circular linked list by any other name (except, possibly, with additional quantifiers, i.e. a circular doubly linked list).

Answer 4

I call them

1) Single list [1]->[2]->NULL

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

3) The circular list [1]->[2]->[1]

You can then use the combination to create your own conditions. However, a description of the problem or an explanation of the problem will clarify the actual meaning of the terms if there is any doubt.

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 “right,” “wrong,” and “circular.”

Unqualified, a link to a list means "acyclic," so "non-circular" is unusual and rather crude.

Ultimately, if your students are mature enough, preference is given to "cyclic" and "acyclic", since your students will again fulfill these conditions when generalizing lists on trees to DAGs on graphs.