Data Structures & Algorithm Day 0

Day 0

Basic data structures

We will see all the code examples in javascript but these concepts are not language-agnostic

1. Arrays

An array is a collection of elements, typically of the same type, stored in contiguous memory locations.

Array as a List of Books:
Imagine you have a shelf that holds a specific number of books. Each slot on the shelf is like an index in an array, and each book is like the element stored at that index.

Key Characteristics:

Indexing: Each element can be accessed by its index (0-based or 1-based depending on the language).

const fruit  = ['Banana','Apple','Grape', 'Pineapple']

console.log(fruit[0]) //  Banana is accessed 0 index
console.log(fruit[3]) // Pineapple is accessed 3 index

Fixed-size: Once declared, the size of the array cannot change (static arrays).
In languages with static arrays, when you declare an array, you must specify its size at the time of creation. This means that if you declare an array with a size of 5, you can only store 5 elements in it, and the size cannot be changed later. You can't add more elements once the array is full, nor can you shrink it.

However, JavaScript arrays are dynamic by nature, so you don't have this fixed-size limitation in most cases. But to understand fixed-size arrays conceptually, imagine if JavaScript arrays couldn't grow or shrink.

let fixedArray = new Array(3); // Array with a fixed size of 3
fixedArray[0] = 'apple';
fixedArray[1] = 'banana';
fixedArray[2] = 'cherry';

// Now if you try to add another item:
fixedArray[3] = 'date'; // This would throw an error or overwrite an existing element (hypothetically)


console.log(fixedArray) // [ 'apple', 'banana', 'cherry', 'date' ]

Random access: You can access any element directly using its index.

const fruit  = ['Banana','Apple','Grape', 'Pineapple']

console.log(fruit[0]) // index 0 is the Banana 
console.log(fruit[3]) // index 3 is the Pineapple 

Pros:

• Fast access to elements by index (O(1) time complexity).
• Simple to implement.

Cons:

• Insertion and deletion are expensive (O(n) time complexity) because shifting elements may be necessary.
• Fixed-size (in some languages), making it less flexible.