Amira Abdelhalim

Posted on

# Linked lists, Arrays and Selection sort...

Here is with chapter 2 of Grokking Algorithms.
• Computer memory is like a giant set of drawers, each drawer has an address. Each time we want to store an item we ask computer for some space and it gives us an address where we can store the item.
• Storing multiple items requires an array or a list

Arrays
• using array means our items will be stored contiguously in memory.
• Every time we add an item to the array we need to check if there is an empty place in the array it is added successfully else we need to ask if there is an empty place in memory that fits all our items right next to each other.
• The place of an item in array is known because items are stored contiguously so to read an item from array it takes O(1).
• To insert in an array it takes O(n) as if we want to insert item at the beginning of an array we will need to shift all other items in the array.
• To delete from an array it also takes O(n) as every thing needs to be moved up when we delete an item.

• Elements in array should be of the same type (int, string...etc,)

“Let’s say we created an array with 10 slots but used only 5 slots in this case we won’t need to move to a new place in memory but here we wasted 5 places in memory.”

• using linked lists allow items to be stored anywhere in memory.
• Each item in the list stores the address of the next item.
• insertion takes O(1) in linked list as we only need to change what a previous element points to.
• deletion takes O(1) as well .