Why Linked List is a Linear Data Structure?

Reminiscing my textbook definitions during graduation, all I ever read about linear data structures was that, they have elements placed adjacent to each other. Now, I curse myself for not being able to understand the inners of the concept rather than trying to perceive the whole thing at superficial level.

As I dig through this, I see that there are two aspects to the term linear. One is at the physical level (in bits and bytes of memory), other at the logical level (concerning the data structures used). At the logical level we talk about data structures as being linear or non linear. But in reality, at the physical level, computer memory is always linear i.e one memory block adjacent to other.

The concept of non linearity is (usually) implemented with the help of pointers that connect other memory chunks by storing their addresses. Technically, implementing pointers at the physical level is somehow helping us to understand non linearity at the logical level implementation of data structures. Assuming so, I was stumped at this point, wondering why a linked list is considered linear in spite of the nodes never being physically adjacent.

After an overwhelming head-breaking session, I started to see this differently. The terms linear and non linear are purely meant to be viewed at the logical level when used along side data structures. If a list is being used, irrespective of whether it is an array implementation or a linked list implementation, it should only be perceived as a data structure that stores elements adjacently (logically, abstract picture) and hence it is linear.

If the confusion still lasts, there is this thumb rule that you can take help of, to recheck if a data structure is linear or non linear. If you are required to sequentially traverse through all the elements of a data structure to access its nth element, then the data structure is linear. Else it is non-linear.

Example : Stacks, Queues, Lists are always linear. Irrespective of whether they are implemented using pointers or arrays, you need to sequentially traverse through the whole data structure to access the nth element which is not so in the case of trees and graphs wherein to access one element, traversing a specific branch might suffice.

Tweet