Overview of Linear & Non-Linear Data Structures
Learn to distinguish between linear and non-linear data structures, such as arrays, linked lists, trees, and hash tables. Understand how their structure affects traversal and operations like insertion, deletion, and search at various time complexities. This lesson helps you choose the right data structure for efficient algorithm implementation in Java.
We'll cover the following...
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; hence, search, insertion, and deletion can work in O(log n) and even ...