Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. Data structures have a wide and diverse scope of usage across the fields of Computer Science and Software Engineering.
Big O notation is one of the most fundamental tools for computer scientists to analyze the cost of an algorithm. It is a good practice for software engineers to understand in-depth as well.
“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”
— Wikipedia’s definition of Big O notation.
Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.
Arrays can be used to store linear data of similar types, but arrays have the following limitations:
- The size of the arrays is fixed, So we must know the upper limit of the number of elements inadvance.
- Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room exisiting elements have to be shifted
- Deletion is also expensive with arrays until unless some special techniques are used.
- Dynamic size.
- Ease of insertion/deletion.
- Random access is not allowed. we have to access elements sequentially starting from the first node.
- extra memory space for a pointer is required with each element of the list.