Data Structures

What is a Data Structure?

A data structure (DS) is a way of organizing data so that it can be used effectively.

Abstract Data Types vs. Data Structures

An abstract data type (ADT) is an abstraction of the data structure which provides only the interface to which a data structure must adhere to.

The interface doest not give any specific details about how something should be implemented or in what programming language.

Examples

Abstraction (ADT)	Implementation (DS)
List	Dynamic Array
	Linked List
Queue	Linked List based Queue
	Array based Queue
	Stack based Queue
Map	Tree Map
	Hash Map / Hash Table
Vehicle	Golf Cart
	Bicycle

Runtime Complexity

Describes the performance of the algorithm. Ref Time complexity

Big O

• N / O(n) - 'linear' runtime

• N^2 / (n\*n) / O(n^2) - N-square or quadratic runtime