Alex Ruheni

Lecture 2: Data Structures and Dynamic Arrays

| 2 min read
Introduction to Algorithms (2 part series)

Interface vs Data Structure

Interfaces also go by Application Programming Interface(APIs) or Abstract Data Types(ADTs).

InterfaceData structure
Is a specification of what you might want to doIs a representation of how to do something (implementation)
Defines what data you can storeDefines how to store the data
Defines the supported operations and what they meanDefines the algorithms to support the operations
Is a problem statementThe solution/ algorithm

Sequence

A sequence a collection of items stored in an order.

There are different data structures that can be used to define and implement a sequence.

Static sequence

aka static array

This is an array with a fixed size/ memory allocated. When the array is created, it can be empty — but the space already allocated in memory. When a value is inserted into the array, it will occupy the available space.

Dynamic sequence/ arrays

Dynamic arrays don't have a pre-defined size. When a new element is being added to a dynamic array:

  1. A new array is created in memory
  2. Data from the previous array is copied over to the new array
  3. The new element is added to the new array
  4. The "old" array is freed from memory

The two common implementations of a dynamic sequence are linked lists and dynamic arrays:

  • Linked-lists
  • Dynamic arrays

Linked-list

Data is stored in a node: containing the element and a pointer to the next element in the list/ array.

Courtesy of https://bodo-schoenfeld.de/

Dynamic array

In a dynamic array, memory is over-allocated when the array is create, i.e, reserves more memory than it needs. This means that the array will be resized every time memory is allocated is depleted by "booking" more memory.

Other learnings

  • Amortized analysis: a method of analyzing a given algorithm's complexity or the total resources required to execute it. It's used to get the average cost of a given operation