Why is a linked list implementation considered linear?

Typically, computer memory is always linear. So is the term non linear used for a data structure in a logical sense? If so, to logically achieve non linearity in a linear computer memory, we use pointers. Is that right?

In that case, if pointers are virtual implementations for achieving non linearity, why would a data structure like linked list be considered linear, if in reality the nodes are never physically adjacent?

• We don't use the word linear to talk about computer memory. Perhaps the word you are looking for there is "contiguous". Linear, constant, exponential all describe graph characteristics of an algorithim's performance. See en.wikipedia.org/wiki/Big_o_notation – Jeremy Nov 22 '11 at 15:15
• It's hard to decipher your question without some context. In particular, "virtual implementations for achieving non linearity" is nonsense. Can you edit your question to include examples of the usage to which you're referring? – Caleb Nov 22 '11 at 15:50
• @Jeremy - Linear refers to many things. The term "linear" in "linear algebra" also does not refer to performance. Particular memory locations are usually referenced using a single linear dimension which is called the "address". I've seen the term "linear memory" used to refer to this a few times, though e.g. "flat memory" is probably more common, as opposed to schemes such as "paged memory" or "segmented memory". See for example the first few words of en.wikipedia.org/wiki/Flat_memory_model – Steve314 Nov 23 '11 at 6:07
• @Steve314 I am aware that English words have multiple usages. This question specifically asks if "non-linear" is a common usage (implied in Computer Science) to refer to certain data structures. It isn't, and neither is linear in the sense that he means. If we talked about a linked list being linear, we are specifically referring to the characteristics of the algorithm used to traverse it. – Jeremy Nov 23 '11 at 14:39
• @Jeremy - which then begs the question - Why focus on the performance of a complete traversal? Why not focus on the constant-time insertion or removal of an item at a known location? Then we could call it a constant list, as opposed to a linear array. There's also other reasons to call a linear list linear (e.g. as opposed to circular). As my answer suggests, the performance of certain operations is a good reason for the name, but I'm not convinced it's the reason. If there's a definitive who-coined-the-term-and-why, though... – Steve314 Nov 23 '11 at 18:31

I think what they mean by "linear" is most probably the linked list's performance characteristics. To access the n-th element of a linked list, you need to walk through each element before it one by one. Thus, the time required to do this is a linear function of n (the upper limit of which is the list size). As opposed to e.g. an array, which is random access, i.e. accessing any array element by index requires practically the same, constant time.

OTOH inserting a new element in a known location in the middle of a linked list requires constant time, while doing the same in an array requires shifting the remainder of the array in memory, which is linear to number of subsequent elements (bounded by the size of the array). So linked lists do have performance benefits.

Non-linear tends to imply a structure beyond a simple sequential pattern. Pointers are one concept used to get past a simple array-like structures. Relational databases could also be seen as a non-linear structure if you want another example.

A linked list can be considered linear if each node is pointing at another node in contrast to trees and other data structures where there may be multiple pointers within a node. A binary tree for example, is much harder to imagine as a line. Another point is how some algorithms like finding the maximum element in an unsorted list have linear time complexity.

One possible reason - because where the nodes appear in memory isn't really relevant. It's more important is how you view the list conceptually.

In more concrete terms, consider how you'd normally represent a linear list as a diagram. Since arrangement in memory is unimportant - it's purely an implementation detail - you don't represent that in the diagram. You typically order the items according to the list order, so they form a line, with each item in order being one step further along the line.

Another idea is that it's purely "linear" in contrast to circular linked lists.

Péter raises a good point, too - probably better than mine. But we're both just inventing rationalisations I suspect. Some names don't have deep meaning, but were just what someone thought up without putting much thought into it, and then the name stuck.

• The problem with linked lists is that in real computers, memory costs aren't equal for all accesses and there's a real cost per independently allocated unit. Arrays fit caches and memory managers very well due to better locality of reference, and have less overhead per cell. – Donal Fellows Nov 22 '11 at 14:16