A data structure is a particular way of organizing data in a computer memory so that it can be used effectively. The main aim of data structure is to reduce the space and time complexities of different tasks. The linear and non-linear data structures are the sub-classification of the data structure which comes under the Non-primitive data structure.
What Is A Linear Data Structure?
Linear data structure is a type of data structure whereby data is arranged in a linear sequence; in which elements are linked one after the other. Data elements in a linear data structure are traversed one after the other and only one element can be directly reached while traversing. Given that linear data structures support single level storage; data elements can be traversed in a single run only.
Linked list is a good example of linear data storage or structure. Linked list stores data in an organized linear fashion. They store data in the form of a list.
Other Examples of linear data structure include:
- Array, which is a collection of data items having similar data types.
- Queue, which is a FIFO (First in First Out) data structure where the element that is added first will be deleted first.
- Stack, which is a FILO (First In Last Out) data structure where the element that is added first will be deleted last.
What You Need To Know About Linear Data Structure
- Linear data structure is a type of data structure whereby data is arranged in a linear sequence; in which elements are linked one after the other.
- Linear data structure is easy to implement in computer’s memory since they are organized sequentially.
- Examples of linear data structure are array, queue, stack, linked list etc.
- In linear data structure, there is one to one relationship between data elements.
- Given that linear data structures support single level storage; data elements can be traversed in a single run only.
- Linear data structure implementation result in poor utilization of memory.
- In linear data structure, all data elements are present at a single level.
- Time complexity of linear data structure often increases with increase in size.
What Is Non-Linear Data Structure?
Non-linear data structure is a type of data structure whereby data elements are hierarchically connected and are present at various levels. What this means is that, a data element of the non-linear data structure could be connected to more than one element to reflect a special relationship among them. Given that non-linear data structures support multi-level storage, they are not easy to traverse in a single run; they require multiple runs to be completely traversed.
Tree data structure is an example of a non linear data structure. A tree has one node referred to as root node that is the starting point that holds data and links to other nodes.
Another example of Non-linear is Graph. A Graph is a collection of a finite number of vertices and edges. Edges connect the vertices and represent the relationship between the vertices that connect these vertices.
What You Need To Know About Non-Linear Data Structure
- Non-linear data structure is a type of data structure whereby data elements are hierarchically connected and are present at various levels.
- Non-linear data structure is difficult to implement in computer’s memory since the data element can be attached to various other data elements.
- Examples of non-linear data structure are tree and graph.
- In non-linear data structure, there may be one-to-one or one-to-many relationship between data elements.
- Given that non-linear data structures support multi-level storage, they are not easy to traverse in a single run; they require multiple runs to be completely traversed.
- Implementation of non-linear data structure result in efficient utilization of the memory.
- In non-linear data structure, data elements are present at multiple levels.
- Time complexity of non-linear data structures often remains unchanged with increase in size.
Difference Between Linear And Non-Linear Data Structures In Tabular Form
BASIS OF COMPARISON | LINEAR DATA STRUCTURE | NON-LINEAR DATA STRUCTURE |
Description | Linear data structure is a type of data structure whereby data is arranged in a linear sequence; in which elements are linked one after the other. | Non-linear data structure is a type of data structure whereby data elements are hierarchically connected and are present at various levels. |
Implementation | It is easy to implement in computer’s memory since they are organized sequentially. | It is difficult to implement in computer’s memory since the data element can be attached to various other data elements. |
Examples | Examples of linear data structure are array, queue, stack, linked list etc. | Examples of non-linear data structure are tree and graph. |
Relationship Between Data Elements | There is one to one relationship between data elements. | There may be one-to-one or one-to-many relationship between data elements. |
Traversal | Data elements can be traversed in a single run only. | They are not easy to traverse in a single run; they require multiple runs to be completely traversed. |
Memory Utilization | Linear data structure implementation result in poor utilization of memory. | Implementation of non-linear data structure result in efficient utilization of the memory. |
Data Elements | All data elements are present at a single level. | Data elements are present at multiple levels. |
Time Complexity | Time complexity of linear data structure often increases with increase in size. | Time complexity of non-linear data structures often remains unchanged with increase in size. |