Linear and Non Linear Data Structures

To start with let us recall that data structure defines a convenient and systematic approach for organizing data within primary memory.

Data organization encompasses the storage of data, as well as its retrieval. Now on the basis of how data can be retrieved out of the data structure, it can be split into two groups; (A) Linear Data Structure and (B) Non-Linear Data Structure.

---

Linear Data Structure

---

The data structure where the function of data access time with respect to the data label is linear is known as Linear Data Structure.

For example, let us think of an arbitrary data structure, let's say X, where the first data is stored in some memory location where the required access time is t unit, the access time of the second data is 2t unit, for third data, it is 3t unit and so on. In this case, if we draw a curve where the x-axis represents the data label and the y-axis represents the data axis time, then the curve would come out as a linear curve. Or stating it in another way, the function specified by the curve would be a linear function. Hence the data structure X would be treated as Linear Data Structure.

The following figure schematically represents the data access time curve for the arbitrary data structure X, and please note that the curve represents a linear function.

Fig: Data Access Time Curve for Arbitrary Data Structure X

Let us consider an array as a real example. The array supports direct access to any ith data, hence whatever the data label, the time required to access that would take unit time. Hence the data access curve would grow as shown in the figure below.

Fig: Data Access Time Curve for Array

So we can easily conclude that an array is an example of a linear data structure

---

Non-Linear Data Structure

---

Nonlinear data structures have Data Access Time Curve which represents Non-Linear functions. Lets us consider an arbitrary data structure Y. Where the access time of the first data is t, the access time of the second element is 2t, the access time of the third element is 2t, and so on.

If we plot the data access time vs data label, we would get a non-linear curve as shown in the following figure which obviously represents a nonlinear function.

Fig: Graph plot of Daya Structure Y

Examples of Non-Linear Data Structures are Tree, Graph, etc. We would discuss these data structures in great detail and there we would discuss the nonlinearity as shown in those data structures.

---

Hope the concept behind linear and nonlinear data structures is clear. :)

Happy Exploring!