5 Common Data Structures

5 Common Data Structures

1. Arrays

Array is collection of elements which can be identified with array index

Each data element is assigned a positive numerical value called the Index*,* which corresponds to the position of that item in the array. The majority of languages define the starting index of the array as 0.

The following are the two types of arrays:

  • One-dimensional arrays
  • Multi-dimensional arrays
let arr = [1, 2, 3, 4]

arr[1] // 2

array

2. Stacks

Stacks are abstract data types that holds an ordered, linear sequence of items.

In contrast to a queue, a stack is a last in, first out (LIFO) structure.

A Real life example of stack could be a pile of books placed in vertical order which in order to take first book in the stack you need to remove all of the top ones.

This is called Last LIFO (Last in First Out)

Pile of Books

3. Queues

Similar to Stack, Queue is another linear data structure that stores the element in a sequential manner.

The only significant difference between Stack and Queue is that instead of using the LIFO method, Queue implements the FIFO method.

LIFO -> Last In First Out (Stack) FIFO -> First In First Out (Queue)

Queue

4. Linked Lists

Linked List

A linked list is another important linear data structure which might look similar to arrays at first but differs in memory allocation, internal structure and how basic operations of insertion and deletion are carried out.

Each item in the linked list called nodes that contain a reference to the next node in the list.

const linkedList = {
    // head of the linked list
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    //    Last value points -> null                            
                    next: null    
                  }
                }
            }
        }
    }
};

First let us create the node class of the linked list

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

Then we can create linkedList which takes a node as an argument.

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}
let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

let list = new LinkedList(node1)

console.log(list.head.next.data) //returns 5

5. Hash Tables (Objects | Dictionaries)

Hash Table

Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its "key"

So, the object is stored in the form of a "key-value" pair, and the collection of such items is called a "dictionary."

Each object can be searched using that key. There are different data structures based on hashing, but the most commonly used data structure is the "hash table".

const collection = new Map();

collection.set("Nathan", "555-0182");
collection["size"] = false;

console.log(collection.get("size")); // undefined
console.log(collection.size); // 1

5.1. Filter out duplicate items


let items = ["apple", "pear", "orange", "banana", "apple",
         "orange", "apple", "pear", "banana", "orange",
         "apple", "kiwi", "pear", "apple", "orange"]

let set = new Set(["apple", "pear", "orange", "banana", "apple",
         "orange", "apple", "pear", "banana", "orange",
         "apple", "kiwi", "pear", "apple", "orange"])

console.log(set)
// Set(5) {"apple", "pear", "orange", "banana", "kiwi"}