Basic Array

• The array data structure is among the oldest and the most frequently used data structure
• It uses the addressing logic of computers
• Array stores data of the same type in consecutive memory locations
• The array size is fixed once it is created
• It can store data at maximum equal to its size
• Most computer languages start the index of array at 0
• An element can be inserted to the array anywhere using in array index
  • A[3] = 5 means assign 5 to the array at index 3

Index, Load and Length of An Array

• Index of each cell is the distance to the first cell
• Length/Size is the maximum capacity of the array
• Load is the number of elements in the array

Using Array for Keeping Sequential Data

• To preserve the order of existing data
• To maintain data in a compact form without any gaps between data
• It is used for efficient management

Performance Analysis of Basic Array Operations

Array Operations

• Insert an item into an array
• Remove an item from an array
• Get a value at a specific location in an array
• Set a value at a specific location in an array
• Search for a value in an array
• We assume data are consecutively ordered from first to the last after theses operations (no gap within the structure)

Insert an Item

• addFirst insert a new item at the front most $$O(n)$$ ![[Array#addFirst]]
• addLast insert a new item next to the last one of the array $$O(1)$$ ![[Array#addLast]]
• addAtIndex insert a new item at index i $$O(n)$$ ![[Array#addAtIndex]]

Delete an Item

• removeFirst delete the front item $$O(n)$$ ![[Array#removeFirst]]
• removeLast delete the last item $$O(1)$$ ![[Array#removeLast]]
• removeAtIndex delete a data at an index i $$O(n)$$ ![[Array#removeAtIndex]]

Get/Set a Value from Array

• It can be accessed directly from its address
  • to get the third element, we write A[2]
  • to set the third element to 4, we write A[2] = 4
    ![[Array#get]]
    ![[Array#set]]

Array Operation Complexity