Array

1. Array

• A sequenced collection of variables all of the same type
• Index → Access : O(1) for both
• Length(capacity) → Its size needs to be specified
• It can contain primitive elements and also references to objects

2. Operation

• Search
• Add / Remove → O(n)
  • You'll have to shift items first. The order matters

3. Implementation

Unsorted Array

• Search : O(n)
• Addition : O(1)
• Deletion : O(n)

Sorted Array

• Search : O(log(n)) → Binary Search could do
• Addition : O(n)
• Deletion : O(n)

4. Application

List

1. Singly Linked List

• Flexible size

• A sequence of nodes

• Node : element, reference to the next node

• One way

2. Operation - Singly Linked List

• size(), isEmpty(), first(), last()
• Insert, Remove
  • it could be done in the middle of the list as well. You'll have to search first and then insert/remove the node considering the order like the ones below are done
  • InsertAfter (Node n, e) : insert a new node with element e after Node n
  • DeleteAFter (Node n) : delete a node after Node n