<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by S. M. Shamir Imtiaz on Medium]]></title>
        <description><![CDATA[Stories by S. M. Shamir Imtiaz on Medium]]></description>
        <link>https://medium.com/@shamirimtiaz?source=rss-27226a08ff9d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*dEMdmFbt_V5atsr9.</url>
            <title>Stories by S. M. Shamir Imtiaz on Medium</title>
            <link>https://medium.com/@shamirimtiaz?source=rss-27226a08ff9d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 04:48:55 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@shamirimtiaz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[A Comprehensive Guide to Implementing Stack, Queue and Deque Data Structures using Linked Lists in…]]></title>
            <link>https://shamirimtiaz.medium.com/a-comprehensive-guide-to-implementing-stack-queue-and-deque-data-structures-using-linked-lists-in-787f81b4dad2?source=rss-27226a08ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/787f81b4dad2</guid>
            <category><![CDATA[stack]]></category>
            <category><![CDATA[queue]]></category>
            <category><![CDATA[linked-lists]]></category>
            <category><![CDATA[deque]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[S. M. Shamir Imtiaz]]></dc:creator>
            <pubDate>Thu, 06 Apr 2023 19:43:19 GMT</pubDate>
            <atom:updated>2023-04-06T19:43:19.625Z</atom:updated>
            <content:encoded><![CDATA[<h3>A Comprehensive Guide to Implementing Stack, Queue and Deque Data Structures using Linked Lists in JavaScript</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-KBg50jjb5bEm46MD50T9Q.png" /><figcaption><a href="https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1206/lectures/stacks-queues/">By stanford.edu</a></figcaption></figure><h3><strong>Stack</strong></h3><p>A stack is a linear type data structure that follows the <strong>Last In First Out (LIFO)</strong> principle means that the last element inserted in stack comes out first. You can think of the stack data structure as the pile of plates on top of another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*XFfcF4hAsXdXez1nP_DAsg.jpeg" /><figcaption>Stack Example(From Wikipedia)</figcaption></figure><p>Stack has three main operations. They are:</p><ul><li><strong>Push: </strong>New element is added to the top of the stack</li><li><strong>Pop: </strong>Removes and returns the top element from the stack</li><li><strong>Top/peek: </strong>Looks into the stack and return the last element inserted onto the stack.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G7N1Rd4ZWSIwkXXa3A85Sg.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack">By sahinarslan.tech</a></figcaption></figure><p><strong>Overflow and underflow</strong></p><p><strong><em>Overflow</em></strong> happens when we try to push more items on a stack than it can be hold. In details, when we try to push an item into a stack that has already reached its maximum size then the insertion will generate an error. So we need to check the stack condition before insertion.</p><p><strong><em>Underflow</em></strong> happens when we try to pop an item from an empty stack. So in this situation pop operation will generate an error.</p><p><strong>Applications of Stack Data Structure</strong></p><ul><li>Function calls and recursion</li><li>Undo/Redo operations</li><li>Expression evaluation</li><li>Browser history</li><li>Balanced Parentheses</li><li>Backtracking Algorithms</li></ul><p><strong>Application of Stack in real life</strong></p><ul><li>CD/DVD stand</li><li>Stack of books in a book shop</li><li>Call center systems</li><li>Undo and Redo mechanism in text editors.</li><li>The history of a web browser is stored in the form of a stack.</li><li>Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.</li><li>YouTube downloads and notifications are also shown in LIFO format(the latest appears first).</li><li>Allocation of memory by an operating system while executing a process.</li></ul><p><strong>Big O of common operations</strong></p><figure><img alt="Big O of different type methods of stack" src="https://cdn-images-1.medium.com/max/578/1*K8xoYthzGgWarXSeguz1ww.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack">By sahinarslan.tech</a></figcaption></figure><p><strong>Stack implementation using Linked List</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/212c183d84796ac3e6c3b18a7aed539f/href">https://medium.com/media/212c183d84796ac3e6c3b18a7aed539f/href</a></iframe><h3><strong>Queue</strong></h3><blockquote><strong>From Wikipedia:</strong> In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.</blockquote><p>So opearations in queue are peformed in <strong>First In First Out (FIFO)</strong> order — the item that inserts in first will come out first. You can think of the queue data structure as the ticket queue outside of a cinema hall.</p><figure><img alt="Example of queue data structure" src="https://cdn-images-1.medium.com/max/1024/1*4CntzA-3G0Z0oJlzfN0QZg.png" /><figcaption>Example of queue data structure(from wikipedia)</figcaption></figure><p>Queue has three main operations. They are:</p><ul><li><strong>Enqueue:</strong> Add an element to the end of the queue</li><li><strong>Dequeue:</strong> Remove an element from the front of the queue</li><li><strong>Peek:</strong> Get the value at the top of the queue without removing it</li></ul><p><strong>Application of Queue Data Structure</strong></p><ul><li>Task Scheduling</li><li>Resource Allocation</li><li>Batch Processing</li><li>Message Buffering</li><li>Event Handling</li><li>Traffic Management</li><li>Operating systems</li><li>Network protocols</li><li>Printer queues</li><li>Web servers</li><li>When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.</li><li>When data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes. Examples include IO Buffers, pipes, etc.</li><li>Buffer for devices like keyboard</li><li>CPU Scheduling</li><li>Memory management</li><li>Queues in routers/ switches</li><li>Mail Queues</li></ul><p><strong>Issues in applications of Queue:</strong></p><ol><li><strong>Overflow</strong>: If a queue has a fixed size, it can become full, leading to a queue overflow. This can happen if elements are added to the queue faster than they are removed. To prevent overflow, some implementations use <em>dynamic resizing</em> or <em>circular buffers</em>.</li><li><strong>Underflow</strong>: If a queue is empty and an attempt is made to remove an element, this can lead to a queue underflow. This can happen if elements are removed from the queue faster than they are added. To prevent underflow, some implementations use <em>sentinel</em> <em>values</em> or <em>null pointers</em> to represent an empty queue.</li></ol><p><strong>Big O of common operations</strong></p><figure><img alt="Big O of different type of methods in queue" src="https://cdn-images-1.medium.com/max/572/1*BHSE8KOnZViOy4N9nE7-yA.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-queue">By sahinarslan.tech</a></figcaption></figure><p><strong>Queue implementation using Linked List</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/811411c8604132a029c3b16f9b4ed787/href">https://medium.com/media/811411c8604132a029c3b16f9b4ed787/href</a></iframe><h3><strong>Deque</strong></h3><blockquote><strong>From</strong> <strong>wikipedia</strong>: In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like “cheque”) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque.</blockquote><p>In short, it is a type of queue data structure that allows insertion and removal of elements from both ends(front or rear).</p><figure><img alt="Double Ended Queue(deque)" src="https://cdn-images-1.medium.com/max/1024/1*AQRGskOhqrKaudmu0RXh_Q.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue">By sahinarslan.tech</a></figcaption></figure><p><strong>Application of Deque Data Structure</strong></p><ul><li>Applied as both stack and queue, as it supports both operations.</li><li>Storing a web browser’s history.</li><li>Storing a software application’s list of undo operations.</li><li>Job scheduling algorithm</li><li>Palindrome checking</li><li>Graph traversal</li><li>Task scheduler</li><li>Multi-level undo/redo functionality</li><li>In computer science, deque can be used in many algorithms like LRU Cache, Round Robin Scheduling, Expression Evaluation.</li></ul><p><strong>Big O of common operations</strong></p><figure><img alt="Big O of different type of methods in deque" src="https://cdn-images-1.medium.com/max/571/1*CnqqyZEZKPYclGCYpMQUWw.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue">By sahinarslan.tech</a></figcaption></figure><p><strong>Deque implementation using Linked List</strong></p><p>The methods we will implement in this article is given below:</p><ul><li><strong>addToFront(value) </strong>— add to the beginning of Deque.</li><li><strong>addToRear(value)</strong>: add to the end of Deque.</li><li><strong>removeFromFront(): </strong>remove from the beginning of Deque</li><li><strong>removeFromRear(): </strong>remove from the end of Deque</li><li><strong>peekFront(): </strong>retrieve first element in the Deque</li><li><strong>peekRear(): </strong>retrieve last element in the Deque</li><li><strong>isEmpty(): </strong>helper method to check if Deque is empty</li><li><strong>print(): </strong>optional method print Deque elements</li></ul><p>Here’s an example of a deque implementation in JavaScript:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/be3563fdd2102cc87589cdd44a45cb6c/href">https://medium.com/media/be3563fdd2102cc87589cdd44a45cb6c/href</a></iframe><h3><strong>Difference between Stack and Queue</strong></h3><ol><li>A stack is a data structure that stores a collection of elements, with operations to push (add) and pop (remove) elements from the top of the stack. A queue is a data structure that stores a collection of elements, with operations to enqueue (add) elements at the back of the queue, and dequeue (remove) elements from the front of the queue.</li><li>Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.</li><li>Stacks are often used for tasks that require backtracking, such as parsing expressions or implementing undo functionality. Queues are often used for tasks that involve processing elements in a specific order, such as handling requests or scheduling tasks.</li><li>Insertion and deletion in stacks takes place only from one end of the list called the top. Insertion and deletion in queues takes place from the opposite ends of the list. The insertion takes place at the rear of the list and the deletion takes place from the front of the list.</li><li>Insert operation is called push operation. Insert operation is called enqueue operation.</li><li>Delete operation is called pop operation. Delete operation is called dequeue operation.</li><li>In stacks we maintain only one pointer to access the list, called the top, which always points to the last element present in the list. In queues we maintain two pointers to access the list. The front pointer always points to the first element inserted in the list and is still present, and the rear pointer always points to the last inserted element.</li><li>Stack is used in solving problems works on recursion. Queue is used in solving problems having sequential processing.</li><li>Stacks are often used for recursive algorithms or for maintaining a history of function calls. Queues are often used in multithreaded applications, where tasks are added to a queue and executed by a pool of worker threads.</li><li>Stack does not have any types. Queue has three types: <br> a. Circular Queue b. Priority queue c. double-ended queue.</li><li>Examples of stack-based languages include PostScript and Forth. Examples of queue-based algorithms include Breadth-First Search (BFS) and printing a binary tree level-by-level.</li></ol><h4><strong>References:</strong></h4><p>1. <a href="https://en.wikipedia.org/wiki/Stack_(abstract_data_type)">https://en.wikipedia.org/wiki/Stack_(abstract_data_type)</a></p><p>2. <a href="https://www.geeksforgeeks.org/stack-data-structure/">https://www.geeksforgeeks.org/stack-data-structure/</a></p><p>3. <a href="https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/">https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/</a></p><p>4. <a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack">https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack</a></p><p>5. <a href="https://en.wikipedia.org/wiki/Queue_(abstract_data_type)">https://en.wikipedia.org/wiki/Queue_(abstract_data_type)</a></p><p>6. <a href="https://www.geeksforgeeks.org/applications-of-queue-data-structure/">https://www.geeksforgeeks.org/applications-of-queue-data-structure/</a></p><p>7. <a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-queue">https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-queue</a></p><p>8. <a href="https://en.wikipedia.org/wiki/Double-ended_queue">https://en.wikipedia.org/wiki/Double-ended_queue</a></p><p>9. <a href="https://www.geeksforgeeks.org/deque-set-1-introduction-applications/">https://www.geeksforgeeks.org/deque-set-1-introduction-applications/</a></p><p>10. <a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue">https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue</a></p><p>11. <a href="https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/">https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/</a></p><p>Thank you for reading this article. Feel free to leave a comment if you have any thoughts, feedback, or suggestions about it!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=787f81b4dad2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding Doubly Linked List in JavaScript: Implementation and Examples]]></title>
            <link>https://shamirimtiaz.medium.com/understanding-doubly-linked-list-in-javascript-implementation-and-examples-7e177efcb6bf?source=rss-27226a08ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e177efcb6bf</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[doubly-linked-list]]></category>
            <category><![CDATA[linked-lists]]></category>
            <dc:creator><![CDATA[S. M. Shamir Imtiaz]]></dc:creator>
            <pubDate>Sun, 02 Apr 2023 10:16:11 GMT</pubDate>
            <atom:updated>2023-04-02T10:16:11.867Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3uuA4v23ByeS22QpvABiDQ.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-doubly-linked-list">By sahinarslan.tech</a></figcaption></figure><h3>Introduction</h3><p>We have previously discussed about singly liked list but now we will discuss another type of linked list name doubly linked list. The main characteristics of doubly linked list is, in here we need to store previous node reference as well as the current value and next node reference.</p><h3><strong>Difference between singly linked list and doubly linked list</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*v6FZfKdJDRWQp2HAQ3_kNA.jpeg" /><figcaption><a href="https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list">By GeeksForGeeks</a></figcaption></figure><h3><strong>Big O of common operations</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*NJmxAaN2p16nliwV9knbRg.jpeg" /><figcaption><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-doubly-linked-list">By sahinarslan.tech</a></figcaption></figure><h3><strong>Implementation</strong></h3><p>Similar to implementation of Singly Linked List, we will also follow the object-oriented way in here. So that first we need a node class and a linked list class.</p><p><strong>Class Node</strong></p><p>In <strong><em>Node class,</em></strong> with <strong><em>value</em></strong> property and <strong><em>next</em></strong> node reference we need to save <strong><em>prev</em></strong>(previous) node reference.</p><pre>class Node {<br>    constructor(value, next = null, prev = null) {<br>        this.value = value; <br>        this.next = next; <br>        this.prev = prev; <br>    }<br>} </pre><p><strong>Class DoublyLinkedList</strong></p><pre>class DoublyLinkedList {<br>  constructor(value) { <br>        let newNode = new Node(value); <br>        this.head = newNode;<br>        this.tail = newNode <br>        this.length = 1; <br>    } <br>}</pre><p><strong>Node append method</strong></p><pre>append(value) {<br>    let newNode = new Node(value); <br>    this.tail.next = newNode; <br>    newNode.prev = this.tail; <br>    this.tail = newNode; <br><br>    this.length++; <br>} </pre><p><strong>Node prepend method</strong></p><pre>prepend(value) {<br>    let newNode = new Node(value);<br>    newNode.next = this.head;<br>    this.head.prev = newNode;<br>    this.head = newNode;<br>    this.length++;<br>}</pre><p><strong>Insert a node at specific position</strong></p><pre>insertAtPosition(value, n) { <br>    if(n === 1) {<br>        this.prepend(value);<br>        return;<br>    } <br>    <br>    if(n &gt; this.length) {<br>        this.append(value)<br>        return<br>    }<br>    <br>    let newNode = new Node(value); <br>    let prevNode = this.find(n-1)<br>    let nextNode = prevNode.next<br>    if(!prevNode) return;<br>    <br>    prevNode.next = newNode<br>    newNode.prev = prevNode<br>    newNode.next = nextNode<br>    nextNode.prev = newNode<br>    this.length++;<br>}<br><br>find(n) {<br>    let data = this.head<br>    let position = 1<br><br>    while(data) {<br>        if (n === position) {<br>            return data<br>        }<br><br>        position++<br>        data = data.next<br>    }<br>}</pre><p><strong>Head delete method</strong></p><pre>deleteHead() {<br>    if (this.length === 1) {<br>        this.head = null<br>        this.tail = null<br>        this.prev = null<br>        this.length--<br>        return<br>    }<br><br>    let newHead = this.head.next<br>    newHead.prev = null<br>    this.head = newHead<br>    this.length--<br>}</pre><p><strong>Tail delete method</strong></p><pre>deleteTail() {<br>    if (this.length === 1) {<br>        this.head = null<br>        this.tail = null<br>        this.prev = null<br>        this.length--<br>        return<br>    }<br><br>    let newTail = this.tail.prev<br>    newTail.next = null<br>    this.tail = newTail<br>    this.length--<br>}</pre><p><strong>Delete at specific position method</strong></p><pre>delete(n) {<br>    if (this.length === 1) {<br>        this.head = null<br>        this.tail = null<br>        this.prev = null<br>        this.length--<br>        return<br>    }<br><br>    if(n === 1) {<br>        this.deleteHead();<br>        return;<br>    } <br>    <br>    if(n &gt; this.length) {<br>        this.deleteTail()<br>        return<br>    }<br>    <br>    let prevNode = this.find(n-1)<br>    let nextNode = prevNode.next.next<br>    <br>    prevNode.next = nextNode<br>    nextNode.prev = prevNode<br>    <br>    this.length--<br>}</pre><p><strong>Reverse a doubly linked list</strong></p><pre>reverse() {<br>    let currNode = this.head<br>    let prevNode = null<br>    let nextNode =null<br>    <br>    while(currNode) {<br>        prevNode = currNode.prev<br>        nextNode = currNode.next<br>        <br>        currNode.next = prevNode<br>        currNode.prev = nextNode<br>        <br>        currNode = nextNode<br>    }<br>    <br>    this.tail = this.head<br>    this.head = prevNode<br>}</pre><h3>Full Code:</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0d6043d2392c1924ae9cd130b1ce9cfe/href">https://medium.com/media/0d6043d2392c1924ae9cd130b1ce9cfe/href</a></iframe><p><strong>References:</strong></p><ol><li><a href="https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-doubly-linked-list">https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-doubly-linked-list</a></li><li><a href="https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list/">https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list/</a></li></ol><p>Thank you for reading this article. Feel free to leave a comment if you have any thoughts, feedback, or suggestions about it!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e177efcb6bf" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introduction to Linked List Data Structure in JavaScript]]></title>
            <link>https://shamirimtiaz.medium.com/introduction-to-linked-list-data-structure-in-javascript-a44cfb7b253?source=rss-27226a08ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/a44cfb7b253</guid>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[linked-lists]]></category>
            <category><![CDATA[singly-linked-list]]></category>
            <dc:creator><![CDATA[S. M. Shamir Imtiaz]]></dc:creator>
            <pubDate>Thu, 30 Mar 2023 06:19:25 GMT</pubDate>
            <atom:updated>2023-04-02T17:57:13.998Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*5wRMqVjLatOGX88VrZgacA.jpeg" /><figcaption><a href="https://kodr.me/en/linked-list-intro">By kodr.me</a></figcaption></figure><h4><strong>Introduction of linked list</strong></h4><p>When we save data in array like data structure then the first element is positioned at first in that array(<em>index 0</em>) then the second element is positioned at second(<em>index 1</em>), third element is positioned at third(<em>index 2</em>) and all other elements are positioned at sequentially. Now in this article we will learn about a new data structure name linked list. In linked list, data are not stored in sequentially but in different memory locations. So we can not get data by using index, like array. In here data are linked through pointers. In details, a linked list is a data structure that consists of a sequence of nodes where each node stores a reference to an object and a reference to the next node in the sequence. It is commonly used for their efficient insertion and deletion operations. Here is an image for better understanding:</p><figure><img alt="Singly Linked List" src="https://cdn-images-1.medium.com/max/767/1*vUpDpDC2S3q2USInWfZvuQ.png" /><figcaption><a href="https://www.geeksforgeeks.org/data-structures/linked-list/">By geeks for geeks</a></figcaption></figure><p>There are three common types of Linked List:</p><ul><li><strong>Singly Linked List</strong></li><li><strong>Doubly Linked List</strong></li><li><strong>Circular Linked List</strong></li></ul><p>In this article, we will look only details about singly linked list. But before going to details let’s see some real world use cases about linked list:</p><ol><li>Implementing in file systems</li><li>Music players</li><li>Web browsing history</li><li>Dynamic memory allocation</li><li>Graphical user interfaces</li><li>Hash tables</li><li>Image viewer</li><li>GPS navigation systems</li><li>Task Scheduling</li><li>Undo/Redo Functionality</li></ol><p><strong>Singly Linked List</strong></p><p>A singly linked list is the most basic type of linked list. Each node in the list stores a pointer to the next node in the sequence, except for the last node which stores a null reference.</p><p><strong>Implementation</strong></p><p>To implement a linked list in javascript we will follow the object-oriented way. So that we need a <strong><em>node class</em></strong> and a <strong><em>linked list class.</em></strong></p><p><strong>Class Node</strong></p><p>The purpose of the <strong><em>Node class</em></strong> is to represent the individual elements (nodes) that made up the linked list. To represent a node class, we need to have two properties. First is <strong><em>value </em></strong>that will represent the data to be stored and the <strong><em>next,</em></strong> the property represents a pointer to the next item in the list.</p><pre>class Node {<br>    constructor(value, next = null) {<br>        this.value = value; <br>        this.next = next; <br>    }<br>}</pre><p><strong>Class LinkedList</strong></p><p>The <strong><em>LinkedList class</em></strong> represents the linked list data structure, which is a collection of nodes that are linked together through their next properties. The purpose of the <strong><em>LinkedList class</em></strong> is to provide methods for manipulating the linked list such as adding, updating and deleting nodes. The <strong><em>LinkedList class</em></strong> also has properties such as <strong><em>head</em></strong>, <strong><em>tail </em></strong>and <strong><em>length </em></strong>to keep track of the first and last nodes in the list and the number of nodes in the list respectively.</p><p>Initially the first node will become <strong><em>head </em></strong>and <strong><em>tail </em></strong>and <strong><em>length </em></strong>is set to 1 of the <strong><em>LinkedList class</em></strong>, then in different type of methods we will update these properties periodically.</p><pre>class LinkedList {<br>  constructor(data) {<br>    let node = new Node(data); <br>    this.head = this.tail = node; <br>    this.length = 1; <br>  }<br>}</pre><p><strong>Node append method</strong></p><pre>append(value) {<br>  let node = new Node(value); <br>  this.tail.next = node; <br>  this.tail = node; <br>  this.length++; <br>} </pre><p>The <strong><em>append </em></strong>method is used for adding a new node at the end of the linked list. In this code snippet:</p><ul><li>The method takes a <strong><em>value </em></strong>parameter, which represents the value to be stored in the new node.</li><li>Now we create a new <strong><em>Node object</em></strong> using this value.</li><li>The next property of the current <strong><em>tail </em></strong>node (i.e. the last node in the list) is set to the new node.</li><li>Then the tail property of the <strong><em>LinkedList object</em></strong> is updated to the new node.</li><li>Update the <strong><em>length </em></strong>property by 1.</li></ul><p><strong>Node prepend method</strong></p><pre>prepend(value) {<br>  let node = new Node(value); <br>  node.next = this.head; <br>  this.head = node; <br>  this.length++; <br>}</pre><p>The <strong><em>prepend </em></strong>method is used for adding a new node at the beginning of the linked list. Here are the below steps of how it works:</p><ul><li>This method also takes a <strong><em>value </em></strong>parameter and a new <strong><em>Node</em></strong> object is created with this value parameter.</li><li>The next property of the new node is set to the current <strong><em>head </em></strong>node of the linked list.</li><li>The <strong><em>head </em></strong>property of the <strong><em>LinkedList</em></strong> object is updated to the new node.</li><li>Finally the <strong><em>length </em></strong>property of the object is incremented by 1.</li></ul><p><strong>Adding a node at specific position</strong></p><pre>appendAtPosition(value, n) { <br>  if(n === 1) {<br>      this.prepend(value); <br>      return; <br>  } <br><br>  if(n &gt; this.length) {<br>      this.append(value); <br>      return; <br>  }<br><br>  let node = new Node(value); <br>  let prevNode = this.findNode(n-1); <br>  const temp = prevNode.next; <br>  prevNode.next = node; <br>  node.next = temp; <br>  this.length++; <br>} <br><br>findNode(n) {<br>  let data = this.head; <br>  let count = 0; <br><br>  while(data) {<br>      count++; <br>      if(count === n) {<br>          break; <br>      } <br><br>      data = data.next; <br>  } <br><br>  return data; <br>}</pre><p>In this code snippet:</p><ul><li>The <strong><em>appendAtPosition </em></strong>method takes two arguments: <strong><em>value</em></strong>, which is the value to be added to the list and <strong><em>n</em></strong>, which is the position in the list where the new value should be inserted.</li><li>Now, first check if the new node can be added at the beginning of the list (i.e. if <strong><em>n </em></strong>is 1). If so, it calls the <strong><em>prepend </em></strong>method to add the new node at the beginning of the list.</li><li>Then, check the new node can be added at the end of the list (i.e. if <strong><em>n </em></strong>is greater than the length of the list). In this situation we call the <strong><em>append </em></strong>method.</li><li>If neither of these cases are true, then we create a new <strong><em>Node </em></strong>instance with the given value. Then call the <strong><em>findNode </em></strong>method to locate the previous node so that the new node can be inserted at the given position. Then assign this node to the variable <strong><em>prevNode</em></strong>.</li><li>Now, assign the next node of <strong><em>prevNode </em></strong>to a temporary variable <strong><em>temp</em></strong>. Then update the next property of <strong><em>prevNode </em></strong>to point to the new node. Finally, update the next property of node to point to the <strong><em>temp </em></strong>variable, which represents the original next node of <strong><em>prevNode</em></strong>.</li></ul><p><strong>Print values of linked list</strong></p><pre>print() {<br>  let data = this.head; <br>  while(data) {<br>      console.log(data.value);<br>      data = data.next; <br>  }<br>} </pre><p>In this code snippet:</p><p>We traverse the list element and printing the value of the property.</p><p><strong>Update node at specific position</strong></p><pre>update(value, n) {<br>  let node = this.findNode(n); <br>  node.value = value; <br>}</pre><p>In this code snippet:</p><p>First, we use the <strong><em>findNode </em></strong>method to locate the node at position <strong><em>n </em></strong>in the linked list. Then simply update the value of node with the new value.</p><p><strong>Delete node at specific position</strong></p><pre>delete(n) {<br>  if (n === 1) {<br>    this.head = this.head.next;<br>    if (!this.head) {<br>        this.tail = null;<br>    }<br>    this.length--;<br>    return;<br>  }<br><br>  let prevNode = this.findNode(n - 1);<br>  prevNode.next = prevNode.next.next;<br><br>  if (n === this.length) {<br>      this.tail = prevNode;<br>  }<br><br>  this.length--;<br>}</pre><p>To properly handle the deletion of a node in the linked list, first we check the node we are deleting is the first node, in that case we update the head property by pointing the next node of head and if there is no second node then we sets the tail property to null. This is necessary because in linked list with only one node, deleting that node should result in an empty linked list where we need to set null in both head and tail.</p><p>If the node is not first node then we need to find the previous node and update that next node of previous node.</p><p>And finally if <strong><em>n </em></strong>is equal to the length of the linked list then we need to delete the last node as well as need to update the tail.</p><p><strong>Reverse a linked list</strong></p><p>To reverse a linked list, we will need three pointers: <strong><em>currNode</em></strong>(currentNode), <strong><em>nextNode</em></strong> (null at the start) and <strong><em>previousNode</em></strong> (null at the start). Otherwise we will lose the pointer to the third element.</p><pre>reverse() {<br>  let currNode = this.head<br>  let nextNode = null<br>  let previousNode = null<br>  <br>  while(currNode) {<br>    nextNode = currNode.next<br>    currNode.next = previousNode<br>    previousNode = currNode<br>    currNode = nextNode<br>  }<br>  <br>  this.tail = this.head<br>  this.head = previousNode<br>}</pre><h4><strong>Full Code:</strong></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/58b593a45c2008bf9a7f3fb3b0f96f6c/href">https://medium.com/media/58b593a45c2008bf9a7f3fb3b0f96f6c/href</a></iframe><p><strong>References:</strong></p><ol><li><a href="https://www.geeksforgeeks.org/data-structures/linked-list/#introduction">https://www.geeksforgeeks.org/data-structures/linked-list/#introduction</a></li><li><a href="https://www.programiz.com/dsa/linked-list">https://www.programiz.com/dsa/linked-list</a></li><li><a href="https://blog.devgenius.io/linked-list-in-javascript-795595742087">https://blog.devgenius.io/linked-list-in-javascript-795595742087</a></li><li><a href="https://kodr.me/en/linked-list-intro">https://kodr.me/en/linked-list-intro</a></li></ol><p>Thank you for reading this article. Feel free to leave a comment if you have any thoughts, feedback, or suggestions about it!</p><p><strong>Next article:</strong> <a href="https://medium.com/@shamirimtiaz/understanding-doubly-linked-list-in-javascript-implementation-and-examples-7e177efcb6bf">Understanding Doubly Linked List in JavaScript: Implementation and Examples</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a44cfb7b253" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Comprehensive Guide to Time and Space Complexity]]></title>
            <link>https://shamirimtiaz.medium.com/a-comprehensive-guide-to-time-and-space-complexity-d1f12341690b?source=rss-27226a08ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/d1f12341690b</guid>
            <dc:creator><![CDATA[S. M. Shamir Imtiaz]]></dc:creator>
            <pubDate>Mon, 20 Mar 2023 10:15:33 GMT</pubDate>
            <atom:updated>2023-03-20T10:15:33.843Z</atom:updated>
            <content:encoded><![CDATA[<p>When we solve problems with different type of algorithms, we need to analyze the computational complexity of these solutions. There are two methods for analyzing the complexity of a problem. They are: time complexity and space complexity.</p><p><strong>Time Complexity</strong></p><blockquote>From wikipedia: In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.</blockquote><p>In simple word, time complexity is a measure of how much time an algorithm takes to execute as a function, based on the length of the input. It is usually expressed as a function of the input size, represented by the letter n example: <strong>O(n)</strong>. And we call it order of n or <strong>Big (O)</strong> of n. But what is <strong>Big(O)</strong> and why it is important?</p><p>In simple terms, if a program can able to handle a large amount of input and the amount of time it takes as same as the small amount of input, then we can rate it well according to <strong>Big O</strong> Notation. Let’s look at the key time and space complexities:</p><p>1. Constant: <strong>O(1)</strong></p><p>2. Linear time: <strong>O(n)</strong></p><p>3. Logarithmic time: <strong>O(n log n)</strong></p><p>4. Quadratic time: <strong>O(n²)</strong></p><p>5. Exponential time: <strong>2^(n)</strong></p><p>6. Factorial time: <strong>O(n!)</strong></p><p><strong>The Big-O complexity chart:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*dWZjY4494gbMQZiL-hO32w.jpeg" /><figcaption><a href="https://dev.to/madisonstankevich/big-o-notation-a-brief-overview-for-the-beginner-1o13">By Madison Stankevich (Dev.to)</a></figcaption></figure><p>It’s important to note that time complexity does not measure the actual time an algorithm takes to execute, but rather how the execution time increases with the size of the input. The actual execution time depends on several factors such as the hardware, programming language, and implementation of the algorithm. Okay enough talking, now let’s take a look at an example below and let’s analysis the time complexity:</p><pre>let sum = 0<br>for(let i = N; i &gt; 0; i++) {<br>  for(let j = 0; j &lt; i; j++) {<br>    sum += 1;<br>  }<br>}</pre><p>Now in the worst case, let’s consider the scenarios:</p><p>1. N*constant operations will run for input.</p><p>2. The outer loop i will run at N times.</p><p>3. For each i, the inner j will run at N times.</p><p>So total execution time will be<strong> N<em>*N*</em>constant + constant</strong>. Now we will ignore the lower order terms as those are relatively insignificant for large inputs, therefore only the highest order term will be taken (without constant) which is <strong>N*N</strong> in this case.</p><p><strong>Space Complexity</strong></p><blockquote>From wikipedia: The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input.</blockquote><p>In simple word: space complexity is a measure of how much memory an algorithm requires to execute as a function, based on the length of the input. It is also expressed as a function of the input size n. For example, if an algorithm takes <strong>O(n)</strong> space, it means that the amount of memory it uses grows linearly with the size of the input. For analyzing space complexity of a problem, we need to focus on two parts:</p><p><strong><em>1. A fixed part:</em></strong> It is required for storing certain data and variables which are independent of the input size like simple constants and variables used, instructions(code) etc.</p><p><strong><em>2. A variable part:</em></strong><em> </em>It is required for variables which are dependent on the size of the input like recursion stack, dynamic memory allocation etc. Okay now let’s take a look at an example below and analysis the space complexity:</p><pre>let sumArray = [];<br>let sum = 0;<br><br>for(let i = N; i &gt; 0; i++) {<br>  for(let j = 0; j &lt; i; j++) {<br>    sum += 1;<br>    sumArray.push(sum);<br>  }<br>}</pre><p>the total space required by the code can be calculated as:</p><p><strong>Space complexity = size of sumArray + size of sum + size of i + size of j</strong></p><p>Since <strong>sumArray </strong>has a size of <strong>N</strong> and sum <strong>i</strong> and <strong>j</strong> are all single integers, the space complexity can be simplified as:</p><p><strong>Space complexity = N + 3</strong></p><p>Therefore, the space complexity will be <strong>O(N)</strong>.</p><p><strong>Data Structure Complexity Chart</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/566/1*yVooB2navImtKDxqY4HjRw.png" /><figcaption>Complexity chart of different data structures</figcaption></figure><p><strong>Search Algorithms</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/569/1*9ScXWsX0O_mhjBbR7K14eQ.png" /><figcaption>Complexity chart of search algorithms</figcaption></figure><p><strong>Sorting Algorithms</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*RUe6bIVEmwHxsrN4tkHr6A.png" /><figcaption>Complexity chart of sort algorithms</figcaption></figure><p><strong>Complexity for Advanced Data Structures</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/563/1*jrxiaFOgR88FQ8VXdppFYA.png" /><figcaption>Complexity chart of advance data structures</figcaption></figure><p><strong>References:</strong></p><p>1. <a href="https://www.geeksforgeeks.org/time-complexity-and-space-complexity/">https://www.geeksforgeeks.org/time-complexity-and-space-complexity/</a></p><p>2. <a href="https://www.simplilearn.com/tutorials/data-structure-tutorial/time-and-space-complexity#GoTop">https://www.simplilearn.com/tutorials/data-structure-tutorial/time-and-space-complexity#GoTop</a></p><p>3. <a href="https://dev.to/madisonstankevich/big-o-notation-a-brief-overview-for-the-beginner-1o13">https://dev.to/madisonstankevich/big-o-notation-a-brief-overview-for-the-beginner-1o13</a></p><p>4. <a href="https://en.wikipedia.org/wiki/Time_complexity">https://en.wikipedia.org/wiki/Time_complexity</a></p><p>5. <a href="https://flexiple.com/algorithms/big-o-notation-cheat-sheet/">https://flexiple.com/algorithms/big-o-notation-cheat-sheet/</a></p><p>6. <a href="https://en.wikipedia.org/wiki/Space_complexity">https://en.wikipedia.org/wiki/Space_complexity</a></p><p>Thank you for reading this story. Feel free to leave a comment if you have any thoughts, feedback, or suggestions about it!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d1f12341690b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>