Data Structures

Question 1

Contiguous vs linked data structures

Answer 1

Contiguously-allocated structures are composed of single slabs of memory, and
include arrays, matrices, heaps, and hash tables.

Linked data structures are composed of distinct chunks of memory bound
together by pointers, and include lists, trees, and graph adjacency lists

Question 2

Array

Answer 2

A contiguously allocated data structure. Arrays are typically of fixed size. Elements can be accessed by their index.

Accessing by index: O(1)
Insert in the beginning;O(n)
Insert at the end: O(1) amortized
Insert in the middle: O(n)
Delete complexity is the same as insert.