Overview of Linear & Non-Linear Data Structures

Now that we have covered all the popular data structures let’s see which of them are linear and which are non-linear. This information is useful when deciding the appropriate data structure for our algorithm.

Linear Data Structures

In linear data structures, each element is connected to either one (the next element) or two (the next and previous) more elements. Traversal in these structures is linear, meaning that insertion, deletion, and search work in O(n).

Arrays, linked lists, stacks, and queues are all example of linear data structures.

Non-Linear Data Structures

The exact opposite of linear data structures are non-linear data structures. In a non-linear data structure, each element can be connected to several other data elements. Traversal is not linear and, hence, search, insertion, and deletion can work in O(log n) and even O(1) time.

Trees, graphs and hash tables are all non-linear data structures.

Time and Space Complexity Cheat Table

Here’s a quick refresher of all the complexities for the data structures we’ve studied in this course. This will help you compare their performances in different scenarios.

Note: In the table, n is the total number of elements stored in the structure.

Data Structure	Insertion (Average/Worst)	Deletion (Average/Worst)	Search (Average/Worst)	Space Complexity (Worst)
Array	O(n)

...