About the Data Structure Part 1

About the Data Structure

Data Structures play an extremely important role when it comes to storing data. These data structures determine how the data is going to be stored within the computer to ensure that it is used and retrieved efficiently. Data structures allow you to improve the efficiency, performance, speed, and scalability of your code/programs/applications.

All programming languages have built-in data structures, but the way they are coded are often different from each other. JavaScript, one of the most popular dynamic computer programming language around the world, comes with its own efficient set of data structures.

Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. — Rob Pike

There are three types of data structures.

• Stacks and Queues are just like array structure only differ with adding and removing the items
• Linked Lists, Trees, and Graphs are nodes structures. This node contains the references to other nodes
• Hash Tables structure that can map keys to values.

In this post, we will learn about the brief introduction of commonly used data structures. In the next post, we will discuss how it can be implemented in a coding manner.

Stack

A stack is a container of objects that are inserted and removed according to the “last-in-first-out” (LIFO) Protocole. In the stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. Push operation is used for adding an item at the top of the stack, the pop operation removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book at the top.

The basic example that you use in your coding is

• Reverse a word. You push a given word to stack — letter by letter — and then pop letters from the stack.
• “Undo-Redo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack

Queues

A queue is a linear data structure, just like a stack data structure, in which the first element is inserted from one end called the REAR(also called the tail), and the removal of an existing element from the other end called the FRONT(also called the head). This makes queue as “first-in-first-out” (FIFO) which means that element inserted first will be removed first.

Which is exactly how the queue system works in the real world. If you go to a ticket counter to buy movie tickets and are first in the queue, then you will be the first one to get the tickets.

The basic example that you see in the real world

• Bank line where people who come first will do his transaction first.
• Keypress sequence in a keyboard.
• Job scheduling in OS

Linked Lists

Linked List is non-contiguous memory allocation and very commonly used linear data structure that consists of a group of nodes in a sequence where each node point to the next node by using the pointer. This data structure allows for efficient insertion or removal of elements from any position in the sequence. A linked list whose Node contains the two fields: data and pointer (in the other word can say address/reference/link). The Last node address of the linked list point to the terminator that signify the end of the list.

Now the question arises when we have an array data structure to store list why do we need to use linked lists.

• In array, elements are stored in contiguous memory locations while in linked lists, it is not necessary elements are stored in contiguous memory locations.
• The cost of insertion/deletion is expensive while it is comparatively easy to delete/insert elements in the linked list. To insert an element in the beginning or somewhere in between the list, first, we need to shift the complete list to the right side and then insert element. The same is the case with the deletion of the element.
• Arrays are of fixed size declared at compile time while linked lists are of dynamic size declared at run time.

Linked list application

• Dynamic memory allocation.
• Image viewer — Previous and next images are linked, hence it can be accessed by next and previous button.
• Music Player — Songs in music players are linked to the previous and next song. you can play songs either from the starting or end of the list.
• To implement the other data structures like Stack, Queue, Trees, and Graph.
• Maintain the directory of names.
• The catch in your browser that allows you to hit the back button (a Linked List of URLs)

Trees

A tree is a non-linear hierarchical data structure in which nodes are connected by edges. In other words, you can say, each node can have no more than one parent or each node can have the child nodes. For instance, The React Virtual Document Object Model (DOM) is just like a tree structure in which the first component (document.getElementById(‘root’)) is the root node that has child components, and then these also further sub-divided into the other child components.

A binary tree is a special tree in which the parent node can have at most two children node referred to the left and right child.

Each node contains the three things

• Pointer to the left subtree
• Pointer to the right subtree
• Node data value

Note — If either the left or right node does not have a pointer, it means that there is no subtree associated with it.

Real-life examples

• Company organizational structure: divisions, departments, etc.
• Computer File System.
• As a workflow for compositing digital images for visual effects.
• AI implemented computer games.

Graphs

A graph is a graphical representation non-linear data structure. It is a collection of nodes where each node can point to other nodes. These nodes are connected through a set of edges.

The best example of a graph is social networking. In a social networking site, people are connected with other people. The whole system appears as a giant connected graph.

A graph G in data structures consists of two things:

• A set v of elements called nodes (or points or vertices).
• A set E of edges such that each edge e in E is identified with a unique (unordered) pair [u,v] of nodes in v, denoted by e=[u,v]sometimes we indicate the parts of a graph by writing G=(v,e).

The real-life example of the graph

• Social networking like Facebook, Twitter, Instagram e.t.c
• Computer networking
• GPS/MAP navigation to find the shortest path route

Hash Table

A hash table is a data structure that allows us to store key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table.

The Hash table consists of the two-component

1. Hash Function — A hash function is a mathematical function that converts a numerical input value(key) into another compressed numerical value(hash). The input to the hash function is of arbitrary length but the output is always of fixed length. It is a one-way transformation function that means the key can not be retrieved from the hash. It avoids the creation of the same hash from the different keys.
2. Array — The array holds all the key-value entries in the table. The size of the array should be set according to the amount of data expected.

The real-life example of the hash table

• Cryptography hash function used for password verification
• Detecting plagiarism
• Internet search engines
• Telephone book databases

Conclusion

As you’ve seen, data structures are the essential building blocks that we use to organize all of our digital information. Choosing the right data structure allows us to use the algorithms we want and keeps our code running smoothly. I hope that you guys got something. Thanks, guys for reading.