Overview of Linear and Non-Linear Data Structures
Learn to distinguish between linear and non-linear data structures, including arrays, linked lists, trees, and graphs. Understand their traversal methods and time complexities for insertion, deletion, and search. This lesson helps you choose the right data structure for your algorithms and optimize performance in your C# programs.
We'll cover the following...
Now that you have learned 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 your 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. This means that insertion, deletion, and search work is in O(n).
Arrays, linked lists, stacks, and queues are all examples 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; 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 that you 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) |