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

Question

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.

Hawkinson

Answer 1

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).

Rowe

Note : Linked list(both single and doubly) is a linear data structure when we're talking about access strategy. However they're considered as non-linear data structures on the basis of storage. – Rosen

Answer 2

You are wrong; 2 justifications:

1. While you can get to 2 elements from any node, one of them was the one you used to get to this node, so you can only get to one new node from each.
2. It is still linear in that it has to be traversed sequentially, or in a line.

Animadversion

Answer 3

It is still sequential: you need to go over some elements in the list to get to a particular element, compared to an array where you can randomly access each element.

However, you can go linearly forwards or backwards, which may optimize the search.

Housemother

Answer 4

linked list is basically a linear data Structure because it stores data in a linear fashion. A linear data Structure is what which stores data in a linear format and the traversing is in sequential manner and not in zigzag way.

Enterovirus

Answer 5

It depends on where you intend to apply linked lists. If you based it on storage, a linked list is considered non-linear. On the other hand, if you based it on access strategies, then a linked list is considered linear.

Digitize