However, JavaScript only comes with primitive data structures such as arrays and objects by default. But with the introduction of ECMAScript 6 (ES6) classes, you can now create custom data structures such as stacks and queues with the help of primitive data structures.
Stack Data Structure
The stack data structure permits you to push new data on top of the existing data in a LIFO (last-in, first-out) manner. This linear data structure is easy to visualize using a simple example. Consider a stack of plates kept on a table. You can add or remove a plate from the top of the stack only.
Here’s how you can implement the stack data structure using JavaScript arrays and ES6 classes:
Let’s explore and build some of the operations that you can perform on a stack.
Push Operation
The push operation is used to insert new data into the stack. You need to pass the data as a parameter while calling the push method. Before inserting the data, the top pointer of the stack is incremented by one, and the new data is inserted at the top position.
Pop Operation
The pop operation is used to remove the uppermost data element of the stack. While performing this operation, the top pointer is reduced by 1.
Peek Operation
The peek operation is used to return the value present at the top of the stack. The time complexity for retrieving this data is O(1).
Learn More: What Is Big-O Notation?
Linked List Data Structure
A linked list is a linear data structure consisting of numerous nodes connected to each other with the help of pointers. Each node in the list contains the data and a pointer variable that points to the next node in the list.
Learn More: An Introduction to Pointers for Programmers
Unlike a stack, linked list implementations in JavaScript require two classes. The first class is the Node class for creating a node, and the second class is the LinkedList class to perform all operations on the linked list. The head pointer points to the first node of the linked list, and the tail pointer points to the last node of the linked list.
Here are some primary operations that you can perform on a linked list:
Append Operation
The append operation is used to add a new node to the end of the linked list. You have to pass the data as a parameter for inserting a new node. Firstly, create a new node object using the new keyword in JavaScript.
If the linked list is empty, both the head and the tail pointer will point to the new node. Otherwise, only the tail pointer will point to the new node.
Insert Operation
To insert a new node at a particular index, you can make use of the insert operation. This method takes two parameters: the data to insert and the index at which it is to be inserted. In the worst case, this method has a time complexity of O(N) as it may have to traverse through the entire list.
Delete Operation
The delete operation traverses through the linked list to get the reference to the node that is to be deleted and removes the link of the previous node. Similar to the insert operation, the delete operation also has a time complexity of O(N) in the worst case.
Queue Data Structure
The queue data structure is similar to a bunch of people standing in a queue. The person who enters the queue first is served before others. Similarly, this linear data structure follows the FIFO (first in, first out) approach to insert and remove data. This data structure can be recreated in JavaScript using a linked list in this manner:
Here’s how you can insert and remove data from a queue in JavaScript:
Enqueue Operation
The enqueue operation inserts new data into the queue. While calling this method, if the queue data structure is empty, both the front and rear pointers point to the newly inserted node in the queue. If the queue is not empty, the new node is added to the end of the list and the rear pointer points to this node.
Dequeue Operation
The dequeue operation removes the first element in the queue. During the dequeue operation, the head pointer is moved ahead to the second node in the list. This second node now becomes the head of the queue.
The Next Step After Data Structures
Data structures can be a tricky concept to grasp, especially if you’re new to programming. But just like any other skill, practice can help you truly understand and appreciate the efficiency it provides for storing and managing data in your applications.
Algorithms are just as useful as data structures and could become the next logical step in your programming journey. So, why not start with a sorting algorithm such as bubble sort?
