Arrays and Linked Lists

Arrays

An array is a data structure that stores elements contiguously. This makes them a good fit for reading operations because they offer random access. Forexample It takes O(1) contanst time to get an element anywhere in the array since we know it's address. But when it comes to insertions, arrays tend to be slower, reason being adding new elements to an array means to also shift existing elements. Therefore this takes O(n) time to insert an element into an array.

Linked Lists

For linked lists, elements are not stored contiguously, elements are stored at different memory locations but they are chained in a way to form a linked list. Forexample first element store the address of the next element which in turn store the address of the next element and so on...

Linked lists are faster for insertion operations O(1), all you need to do is insert an element in memory and get the last element point to the address of the recent added element. For reading operations O(n), linked lists are slower since we only know the address of the first element,we need to go through every element reading the addresses they point to.

Comparison Arrays and Linked lists

	Array	Linked list
Insertion	O(n)	O(1)
Reading	O(1)	O(n)