Traits

Go’s Arrays(Static arrays) and Slices(Dynamic arrays)

• Arrays, Slices

Upsides

• Efficient Insert/Remove End
• Index-based access allows relationships calculation like parent-child relationship in Heaps.

Downsides and Compensations

• Inefficient Insert/Remove Middle
• Inefficient Insert/Remove First
  • Can be fixed by head tracking, bit it will cause memory leak
  • Can be fixed by circular/ring buffer, but it will loses physical index order (limited random access).

Dynamic Arrays

Insert End

1. Create a new extended view (Go) or Extend the length of current view (Other languages)
   1. It points to the same array if the capacity is sufficient.
   2. Or, it points to a new extended capacity array, which require O(n) time for copying.
2. Reassigns the last element. It takes constant time, O(1).

func insertEnd(nums []int, value int) []int {
	return append(nums, value)
}

Insert First/Middle

1. Create a new extended view (Go) or Extend the length of current view (Other languages)
2. Shift elements. It preforms linear time, O(n).

func insertKth(nums []int, k, value int) ([]int, bool) {
	if k < 1 || k > len(nums) {
		return nil, false
	}
	return append(nums[:k-1], append([]int{value}, nums[k-1:]...)...), true
}

func insertKth(nums []int, k, value int) ([]int, bool) {
	if k < 1 || k > len(nums) {
		return nil, false
	}
	nums = append(nums, 0) // extend the length
	copy(nums[k:], nums[k-1:])
	nums[k-1] = value
	return nums, true
}

Kth (1-Index-Based)