Week 2 - Arrays and Linked Lists

Question 1

What is computer memory?

Answer 1

Computer memory is a long sequence of bytes and is byte-addressable. It can be imagined as a single drawer that holds a single item.

Question 2

What is an Array?

Answer 2

An array is a data structure that stores elements in a continuous block of memory, allowing efficient access to each element.

Question 3

How is a new item inserted into an array?

Answer 3

Inserting a new item into an array often requires shifting elements. If there isn’t enough space, the entire array may need to be relocated in memory first.

Question 4

What’s a solution to the issue of arrays not fitting in memory

Answer 4

One solution is to allocate a larger array with dummy values in the extra slots, but this can waste space. If the extra space is filled, the problem persists.

Question 5

What are linked lists?

Answer 5

Linked lists are a data structure where each element stores the address of the next, forming a chain. This makes inserting a new element easier than in an array, but it has a time complexity of O(n) to find a specific element in the list.

Question 6

What module in python allows you to use linked lists?

Answer 6

structlinks

Question 7

What is the Big-O time complexity of reading and inserting in an array and linked list?

Answer 7

Array
Reading –> O(1) Constant time
Inserting (instant access) –> O(n)
Deleting (instant access) –> O(n)
Insert/ Delete at index –> O(n)

Linked List
Reading –> O(n)
Inserting (instant access) –> O(1)
Deleting (instant access) –> O(1)
Insert/ Delete at index –> O(n)

Question 8

What is a constant time O(1) algorithm?

Answer 8

A constant time algorithm performs a fixed number of steps or operations, regardless of the input size.

Question 9

What is the difference between access in arrays and linked lists?

Answer 9

Arrays allow for random access, unlike linked lists which have sequential access.

Question 10

What is selection sort and how does it work?

Answer 10

Selection sort is a sorting algorithm that repeatedly finds the smallest/ largest element from the unsorted list and places it in the sorted portion. It’s like picking the top songs one by one until all are sorted. It has a time complexity of O(n^2) (Quadratic time)