QueuesĪ queue is a line of items, neatly arranged next to each other. The top of the stack is easily accessible.
Since a stack operates by a LIFO process, the complexity to push an item to the top of the stack or to pop it off is a constant of O(1). The last item in is always the first item out ( LIFO). Reversely, each item can be popped off, one at a time, from the top of the stack. A new item can be pushed onto the top of a stack, one at a time, building to the height of the stack. StacksĪ stack is a pile of items neatly arranged atop each other. Although, an O(1/2 n) tends to be simplified as O(n). If the “box” or “item” is located at the 2nd half of the list, traveling from the tail will not require traveling through the 1st half of the list. That is, their complexities are half of O(n). The new tail required for popping a tail off is reachable from the current tail.Īnother advantage of being able to travel from two different end points (head or tail) is that to insert/remove any “box” or to get/set “items” in a “box” along the body of a list takes half the time of a singly linked list. The complexity to unshift, shift, push or pop is O(1).
An advantage is that both the head & tail are easily accessible to add “boxes” to or remove “boxes” from. This means you can move forward from the head or the tail. Similarly, to insert/remove a “box,” or to get/set items in any “box” along the body of a list requires traveling from the head, and so their complexities are in general O(n).Ī doubly linked list is a two-way linked list. An n number of “boxes” requires n number of steps (operations) to reach the second to last “box” & reassign it as the new tail. The complexity to push a “box” to the end is also O(1) for a similar reason, the tail is immediately accessible.īut, to pop off the tail requires reassigning a new tail, which is reachable only by moving forward starting from the head, hence a linear complexity ( O(n)). This is because adding a “box” to or removing it from the beginning requires only accessing the head of the list. The complexity to unshift & shift is a constant ( O(1)). This means that you can only move forward from the head to the tail. It requires starting at the head (or tail) and moving from a current “box” to the next one, before you can get to your desired “box.”Ī singly linked list is a one-way linked list. But, to insert or remove “boxes” along the body of this linked list, to set items into a “box” that is beyond the head or tail, is more difficult. You can also easily shift or pop off “boxes” from the head or tail.
You can easily unshift or push “boxes” to the head or tail of the linked list. There is no index to act as a guide for leaping to any one box. Upon arriving at any one box, you are pointed towards the direction of the next box. To get to any one box requires starting at one end (head or tail) and following the links, from one box to the next. Linked ListsĪ linked list is like a set of boxes chained together and stored in a dark room. Like a road along a path, linked lists, stacks & queues are direct ways to move from one unit of data to the next. Leung Linear Data Structures: Linked Lists, Stacks, and Queues in JS Photo by Pranam Gurung on Unsplashīuilding from Simple Algorithms & Data Structures in JS, here we’ll look at data structures beyond arrays and key-value objects, beyond “labelled & deposit” boxes.