What are data structures

Data structures, at a high level, are techniques for storing and organizing data that make it easier to modify, navigate, and access. Data structures determine how data is collected, the functions we can use to access it, and the relationships between data.

Data structures are used in almost all areas of computer science and programming, from operating systems to basic vanilla code to artificial intelligence.

Data structures enable us to:

• Manage and utilize large datasets
• Search for particular data from a database
• Design algorithms that are tailored towards particular programs
• Handle multiple requests from users at once
• Simplify and speed up data processing

Data structures are vital for efficient, real-world problem solving. After all, the way we organize data has a lot of impact on performance and useability. In fact, most top companies require a strong understanding of data structures.

Anyone looking to crack the coding interview will need to master data structures.

JavaScript has primitive and non-primitive data structures. Primitive data structures and data types are native to the programming language. These include boolean, null, number, string, etc.

Non-primitive data structures are not defined by the programming language but rather by the programmer. These include linear data structures, static data structures, and dynamic data structures, like queue and linked lists.

1. Array

The most basic of all data structures, an array stores data in memory for later use. Each array has a fixed number of cells decided on its creation, and each cell has a corresponding numeric index used to select its data. Whenever you'd like to use the array, all you need are the desired indices, and you can access any of the data within.

Advantages

• Simple to create and use.
• Foundational building block for complex data structures

Disadvantages

• Fixed size
• Expensive to insert/delete or resequence values
• Inefficient to sort

Applications

• Basic spreadsheets
• Within complex structures such as hash tables

2. Queues

Queues are conceptually similar to stacks; both are sequential structures, but queues process elements in the order they were entered rather than the most recent element.

As a result, queues can be thought of as a FIFO (First In, First Out) version of stacks. These are helpful as a buffer for requests, storing each request in the order it was received until it can be processed.

For a visual, consider a single-lane tunnel: the first car to enter is the first car to exit. If other cars should wish to exit, but the first stops, all cars will have to wait for the first to exit before they can proceed.

Advantages

• Dynamic size
• Orders data in the order it was received
• Low runtime

Disadvantages

• Can only retrieve the oldest element

Applications

• Effective as a buffer when receiving frequent data
• Convenient way to store order-sensitive data such as stored voicemails
• Ensures the oldest data is processed first

3. Linked List

Linked lists are a data structure which, unlike the previous three, does not use physical placement of data in memory. This means that, rather than indexes or positions, linked lists use a referencing system: elements are stored in nodes that contain a pointer to the next node, repeating until all nodes are linked.

This system allows efficient insertion and removal of items without the need for reorganization.

Advantages

• Efficient insertion and removal of new elements
• Less complex than restructuring an array

Disadvantages

• Uses more memory than arrays
• Inefficient to retrieve a specific element
• Inefficient to traverse the list backward

Applications

• Best used when data must be added and removed in quick succession from unknown locations

4. Trees

Trees are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, nodes contain both elements of data and pointers marking its relation to immediate nodes.

Each tree has a "root" node, off of which all other nodes branch. The root contains references to all elements directly below it, which are known as its "child nodes". This continues, with each child node, branching off into more child nodes.

Nodes with linked child nodes are called internal nodes while those without child nodes are external nodes. A common type of tree is the "binary search tree" which is used to easily search stored data.

These search operations are highly efficient, as its search duration is dependent not on the number of nodes but on the number of levels down the tree.

This type of tree is defined by four strict rules:

1. The left subtree contains only nodes with elements lesser than the root.
2. The right subtree contains only nodes with elements greater than the root.
3. Left and right subtrees must also be a binary search tree. They must follow the above rules with the "root" of their tree.
4. There can be no duplicate nodes, i.e. no two nodes can have the same value.

Advantages

• Ideal for storing hierarchical relationships
• Dynamic size
• Quick at insert and delete operations
• In a binary search tree, inserted nodes are sequenced immediately.
• Binary search trees are efficient at searches; length is only O(height)O(height).

Disadvantages

• Slow to rearrange nodes
• Child nodes hold no information about their parent node
• Binary search trees are not as fast as the more complicated hash table
• Binary search trees can degenerate into linear search (scanning all elements) if not implemented with balanced subtrees.

Applications

• Storing hierarchical data such as a file location.
• Binary search trees are excellent for tasks needing searching or ordering of data.

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

5. Graphs

Graphs are a relation-based data structure helpful for storing web-like relationships. Each node, or vertex, as they're called in graphs, has a title (A, B, C, etc.), a value contained within, and a list of links (called edges) it has with other vertices.

In the above example, each circle is a vertex, and each line is an edge. If produced in writing, this structure would look like:

V = {a, b, c, d}

E = {ab, ac, bc, cd}

While hard to visualize at first, this structure is invaluable in conveying relationship charts in textual form, anything from circuitry to train networks.

Advantages

• Can quickly convey visuals over text
• Usable to model a diverse number of subjects so long as they contain a relational structure

Disadvantages

• At a higher level, text can be time-consuming to convert to an image.
• It can be difficult to see the existing edges or how many edges a given vertex has connected to it

Applications

• Network representations
• Modeling social networks, such as Facebook.

6. Hash Tables (Map)

Hash tables are a complex data structure capable of storing large amounts of information and retrieving specific elements efficiently. This data structure relies on the concept of key/value pairs, where the "key" is a searched string and the "value" is the data paired with that key.

Each searched key is converted from its string form into a numerical value, called a hash, using a predefined hash function. This hash then points to a storage bucket -- a smaller subgroup within the table. It then searches the bucket for the originally entered key and returns the value associated with that key.

Advantages

• Key can be in any form, while array's indices must be integers
• Highly efficient search function
• Constant number of operations for each search
• Constant cost for insertion or deletion operations

Disadvantages

• Collisions: an error caused when two keys convert to the same hash code or two hash codes point to the same value.
• These errors can be common and often require an overhaul of the hash function.

Applications

• Database storage
• Address lookups by name

Each hash table can be very different, from the types of the keys and values, to the way their hash functions work. Due to these differences and the multi-layered aspects of a hash table, it is nearly impossible to encapsulate so generally.

Data structure interview questions

[1,2,4,5,10,6,3]

[1,5,3]

//function removeEven(arr) {const odds = [];for (let number of arr) {if (number % 2 != 0)// Check if the item in the list is NOT even ('%' is the modulus symbol!)
            odds.push(number); //If it isn't even append it to the empty list}return odds; // Return the new list}let example = removeEven([3, 2, 41, 3, 34]);
console.log('EXAMPLE:', example); //EXAMPLE: [ 3, 41, 3 ]

//function removeEven(arr) {return arr.filter((v) => v % 2 != 0);}

console.log(removeEven([3, 2, 41, 3, 34]));

//
exp = '{[({})]}';

True

//"use strict";
module.exports = class Stack {constructor() {this.items = [];this.top = null;}getTop() {if ( this.items.length == 0 )return null;return this.top;}isEmpty() {return this.items.length == 0;}size() {return this.items.length;}push( element ) {this.items.push( element );this.top = element;}pop() {if ( this.items.length != 0 ) {if ( this.items.length == 1 ) {this.top = null;return this.items.pop();

//
n = 3;

//
result = ['1', '10', '11'];

//"use strict";
module.exports = class Queue {constructor () {this.items = [];this.front = null;this.back = null;}isEmpty() {return this.items.length == 0;}getFront() {if ( this.items.length != 0 ) {return this.items[ 0 ];} elsereturn null;}size() {return this.items.length;}enqueue( element ) {this.items.push( element );}

//
LinkedList = 0->1->2->3-4

//
LinkedList = 4->3->2->1->0

//"use strict";const Node = require( './Node.js' );
module.exports = class LinkedList {constructor() {this.head = null;}//Insertion At HeadinsertAtHead( newData ) {let tempNode = new Node( newData );
      tempNode.nextElement = this.head;this.head = tempNode;return this; //returning the updated list}isEmpty() {return ( this.head == null );}//function to print the linked listprintList() {if ( this.isEmpty() ) {
          console.log( "Empty List" );return false;} else {let temp = this.head;while ( temp != null ) {
            process.stdout.write( String( temp.data ) );
            process.stdout.write( " -> " );
            temp = temp.nextElement;

//
bst = {    6 -> 4,9    4 -> 2,5    9 -> 8,12    12 -> 10,14}where parent -> leftChild,rightChild

2

//'use strict';const Node = require('./Node.js');
module.exports = class BinarySearchTree {constructor(rootValue) {this.root = new Node(rootValue);}insert(currentNode, newValue) {if (currentNode === null) {
            currentNode = new Node(newValue);} else if (newValue < currentNode.val) {
            currentNode.leftChild = this.insert(currentNode.leftChild, newValue);} else {
            currentNode.rightChild = this.insert(currentNode.rightChild, newValue);}return currentNode;}insertBST(newValue) {if (this.root == null) {this.root = new Node(newValue);return;}this.insert(this.root, newValue);}preOrderPrint(currentNode) {if (currentNode !== null) {
            console.log(currentNode.val);this.preOrderPrint(currentNode.leftChild);}}};

//removeEdge(graph, 2, 3);

//const LinkedList = require('./LinkedList.js');const Node = require('./Node.js');
module.exports = class Graph {constructor(vertices) {this.vertices = vertices;this.list = [];let it;for (it = 0; it < vertices; it++) {let temp = new LinkedList();this.list.push(temp);}}addEdge(source, destination) {if (source < this.vertices && destination < this.vertices) this.list[source].insertAtHead(destination);return this;}printGraph() {
        console.log('>>Adjacency List of Directed Graph<<');let i;for (i = 0; i < this.list.length; i++) {
            process.stdout.write(`|${String(i)}| => `);}}};

//
maxHeap = [9, 4, 7, 1, -2, 6, 5];

//
result = [-2, 1, 5, 9, 4, 6, 7];

//function minHeapify(heap, index) {const left = index * 2;const right = index * 2 + 1;let smallest = index;if (heap.length > left && heap[smallest] > heap[left]) {
        smallest = left;}if (heap.length > right && heap[smallest] > heap[right]) smallest = right;if (smallest != index) {const tmp = heap[smallest];
        heap[smallest] = heap[index];
        heap[index] = tmp;minHeapify(heap, smallest);}return heap;}

//function convertMax(maxHeap) {for (var i = Math.floor(maxHeap.length / 2); i > -1; i--) maxHeap = minHeapify(maxHeap, i);return maxHeap;}var maxHeap = [9, 4, 7, 1, -2, 6, 5];

console.log(convertMax(maxHeap));