# 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

```jsx
let arr = [1, 2, 3, 4]

arr[1] // 2
```

![array](https://cdn.hashnode.com/res/hashnode/image/upload/v1630575111055/aspwuzidO.png)

## 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](https://cdn.hashnode.com/res/hashnode/image/upload/v1630575113665/RVQhe4Mi1.jpeg)

## 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](https://cdn.hashnode.com/res/hashnode/image/upload/v1630575115988/sWZDU9umY.jpeg)

## 4. Linked Lists

![Linked List](https://cdn.hashnode.com/res/hashnode/image/upload/v1630575118040/i6olN4qaT.png)

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. 

```jsx
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
```jsx
class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}
```

Then we can create linkedList which takes a node as an argument.
```jsx
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}
```

```jsx
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](https://cdn.hashnode.com/res/hashnode/image/upload/v1630575119775/u5tcUpSwK.png)

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".

```jsx
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

```jsx

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"}
```

## Helpful Links & Resources

- [4 Common Data Structures](https://dev.to/highcenburg/common-data-structures-1fh)
- [The top data structures you should know for your next coding interview](https://www.freecodecamp.org/news/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3/)
- [How to Implement a Linked List in JavaScript](https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/)