Is doubly linked list a non linear data structure or linear data structure?

Varun Teja picture Varun Teja · May 27, 2015 · Viewed 9.3k times · Source

A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists.

But in doubly linked list we can reach two data elements using previous pointer and next pointer.

So can we say that doubly linked list is a non linear data structure?

Correct me if I am wrong.

Thank you.

Answer

Am_I_Helpful picture Am_I_Helpful · May 27, 2015

Non-linear data structures are those data-structure in which the elements appear in a non-linear fashion,which requires two or more than two-dimensional representation . The elements may OR mayn't(mostly) be stored in contiguous memory locations,rather in any order/non-linearly as if you have skipped the elements in between. Accessing the elements are also done in an out-of-order pattern.

Example :- A Tree, here one may iterate from root to right child,to its right child,... and so on---thereby skipping all the left nodes.

But, in doubly linked list, you have to move sequentially(linearly) only, to move forward(using forward pointer) or backward(using previous pointer). You can't jump from any element in the list to any distant element without traversing the intermediary elements.

Hence, doubly-linked list is a linear data structure. In a linear data structure, the elements are arranged in a linear fashion(that is,one-dimensional representation).