A Data Structure as the name suggests is the way Data or Information is structured or organized in computer systems. Data Structures are the programmatic way of storing and organizing data in a
computer.
You can imagine it like a real world book storage. You can organize your books in alphabetical order of their title or categorize them according their genre. You can put all the books together or seprate them into compartments for easier access.
Below I will describe some of the most commonly used Data Structures
Arrays
An Array is a data structure which is used to store data in adjacent memory
location. The data stored in the array is called the element of an array
and the location of the array is accessed using index. The size of the array
is fixed.
So going with a book storage analogy we can think of it as books stored in alphabetical order of their titles. In order to get to a book starting with "D", you will have to sequentially go past books with titles starting with "A", "B" and "C"
Big O - Time complexity of searching an item in an array.
Lets take an example we have a array of string below:
let stringArray = ['Apple', 'Orange', 'Banana', 'Strawberry'];
Now if I need to find the index of 'Apple' in this stringArray my code will
look something like this:
for(let i = 0; i < stringArray.length; i++){
if(stringArray[i] === 'Apple'){
return i;
}
}
Here since 'Apple' is at the first index the code executed in O(1) time.
However for Big O notation we consider the worst time. So in case we need to
find 'Strawberry' then our code will look something like this:
for(let i = 0; i < stringArray.length; i++){
if(stringArray[i] === 'Strawberry'){
return i;
}
}
Since 'Strawberry' is at the last index the code executed in O(n) time,
assuming that n = stringArray.length. So the time complexity of searching an
item in an Array is O(n).
Linked List
A linked list is a data structure where data is arranged as nodes, each node
contains two parts the actual data and the address to the next node. The data
stored in a linked list is accessed by traversing through the list from the
first node till we reach the node with required information. The size of the
linked list can shrink and grow on demand.
Comparing it with our real world book storage example you can think of link list as muliple book bins. Each bin has books of the same starting alphabet, plus it has a note which tells you where the next alphabet bin is located. So "A" bin will have all the books with title starting with A and it will have note which will tell you where "B" bin is located in the house.
Big O - Time complexity of searching an item in a linked list.
Lets take an example we have a linked list of string below:
'Apple', 'Orange', 'Banana', 'Strawberry'
class LinkedListNode(val) {
this.data = data;
this.next = null;
}
}
const head = new LinkedListNode('Apple') ;
head.next = new LinkedListNode('Orange');
head.next.next = new LinkedListNode('Banana');
head.next.next.next = new LinkedListNode('Strawberry');
Now if I need to find 'Apple' in this linked list
let current = head;
while(current !== null){
if(current.data === 'Apple')
return current;
current = current.next();
}
Here since 'Apple' is at the first node the code executed in O(1) time.
However for Big O notation we consider the worst time. So in case we need
to find 'Strawberry' then our code will look something like this:
let current = head;
while(current !== null){
if(current.data === 'Strawberry')
return
current;
current = current.next();
}
Since 'Strawberry' is at the last node the code executed in O(n) time,
assuming that n = number of nodes. So the time complexity of searching an
item in a Linked List is O(n).
Map
A Map is a data structure which stores data as key - value pairs. The value
can be directly accessed using the key.
Big O - Time complexity of searching an item in a Map.
Lets take an example we have a Map below:
let countryMap = new Map();
countryMap['us'] = 'United States';
countryMap['es'] = 'Spain';
countryMap['zw'] = 'Zimbabwe';
So if I need to access 'United States' from the Map all I need to do
is:
return countryMap['us'];
Similarly for 'Zimbabwe'.
return countryMap['zw'];
Here we see that no matter what the size of the Map is the time
complexity of Map does not change so it is O(1) (constant
complexity).
Graph
A Graph is a Data Structure which contains a set on nodes (vertices) and set
of edges connecting the nodes. Data stored in a graph can be accessed by
traversing through the edges of the nodes till you reach the required
information.
Graphs are most commonly represented in a program as Adjacency Matrix or
Adjacency List.
Adjacency Matrix - is represented as a two dimensional array of
size VxV where V is the total number of vertices. So for the above graph the
can be represented as follows:
Assuming that the above array is called adjacencyMatrix then
adjacencyMatrix[0][1] = 1 means there is a edge between vertex 0 and vertex
1. Similarly adjacencyMatrix[0][2] = 0 means there is no edge between vertex
0 and 2.
Big O - Time complexity of searching an item in a Graph represented by
Adjacency Matrix.
So the above graph can be represented as below and we have to search any
item in this two dimensional array.
const adjacencyMatrix = [[0,1,0,0,1],
[1,0,1,1,1],
[0,1,0,1,0],
[0,1,1,0,1],
[1,1,0,1,0]];
let rows = 5;
let cols = 5;
for(let i =0; i<5;i++){
for(let j = 0; j<5;j++){
console.log(a[i][j]);
}
}
We see that to search an item we need 2 nested for loops each size 5 which
is the total number of vertices in the graph. Assuming that n is the number
of vertices the time complexity of searching an item in adjacency matrix
representation of a graph is O(n2).
Adjacency List - is an array of lists where an entry a[i]
represents the list of vertices which the given vertex is connected by an
edge. Lets see how the graph above can be represented as a Adjacency List.
Big O - Time complexity of searching an item in a Graph represented by
Adjacency List. So the above graph can be represented as below:
const adjacencyList = new Map();
adjacencyList.set(0, new Set([1,4]));
adjacencyList.set(1, new Set([0,4,2,3]));
adjacencyList.set(2, new Set([1,3]));
adjacencyList.set(3, new Set([1,4,2]));
adjacencyList.set(4, new Set([3,0,1]));
The time complexity of accessing items in a map is O(1) so to search an item
in the Adjacency List with Map implementation is O(1).
Tree
A Tree is a special type of Graph Data Structure where all the nodes originate
either directly or indirectly from exactly one node, called the root node.
We can represent the above Tree using the Adjacency List like below:
const adjacencyList = new Map();
adjacencyList.set("A", new Set(["B","C","D"]));
adjacencyList.set("B", new Set(["E","F"]));
adjacencyList.set("C", new Set(["G"]));
adjacencyList.set("D", new Set(["H","I"]));
adjacencyList.set("G", new Set(["J","K"]));
The time complexity of accessing items in a map is O(1) so to search an item
in the Adjacency List with Map implementation is O(1).
Useful links:
