-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path2021-03-22_Fundamental-Data-Structures-in-JavaScript-88466fae0fbb.html
More file actions
586 lines (583 loc) · 51.4 KB
/
Copy path2021-03-22_Fundamental-Data-Structures-in-JavaScript-88466fae0fbb.html
File metadata and controls
586 lines (583 loc) · 51.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Fundamental Data Structures in JavaScript</title>
<link rel="stylesheet" href="./style.css">
</head>
<body>
<article class="h-entry">
<header>
<h1 class="p-name">Fundamental Data Structures in JavaScript</h1>
</header>
<section data-field="subtitle" class="p-summary">
A simple to follow guide to Lists Stacks and Queues, with animated gifs, diagrams, and code examples!
</section>
<section data-field="body" class="e-content">
<section name="1afa" class="section section--body section--first">
<div class="section-divider">
<hr class="section-divider">
</div>
<div class="section-content">
<div class="section-inner sectionLayout--insetColumn">
<h3 name="a9b6" id="a9b6" class="graf graf--h3 graf--leading graf--title">Fundamental Data Structures in
JavaScript</h3>
<h4 name="b410" id="b410" class="graf graf--h4 graf-after--h3 graf--subtitle">A simple to follow guide to
Lists Stacks and Queues, with animated gifs, diagrams, and code examples!</h4>
</div>
<div class="section-inner sectionLayout--fullWidth">
<figure name="4027" id="4027" class="graf graf--figure graf--layoutFillWidth graf-after--h4"><img
class="graf-image" data-image-id="0*ph952PPOmG5uz_Pv" data-width="1252" data-height="882"
src="https://cdn-images-1.medium.com/max/2560/0*ph952PPOmG5uz_Pv"></figure>
</div>
<div class="section-inner sectionLayout--insetColumn">
<figure name="ff1a" id="ff1a" class="graf graf--figure graf-after--figure"><img class="graf-image"
data-image-id="0*zhC6dP1hb2rq2qt2.png" data-width="1000" data-height="500" data-is-featured="true"
alt="Stack & Queue Data Structure Image"
src="https://cdn-images-1.medium.com/max/800/0*zhC6dP1hb2rq2qt2.png"></figure>
<h3 name="5669" id="5669" class="graf graf--h3 graf-after--figure">Linked Lists</h3>
<figure name="53de" id="53de" class="graf graf--figure graf-after--h3"><img class="graf-image"
data-image-id="0*znES1vYRV3Zvk9-e.gif" data-width="1024" data-height="768"
src="https://cdn-images-1.medium.com/max/800/0*znES1vYRV3Zvk9-e.gif"></figure>
<p name="b9f5" id="b9f5" class="graf graf--p graf-after--figure">In the university setting, it’s common
for Linked Lists to appear early on in an undergraduate’s Computer Science coursework. While they don’t
always have the most practical real-world applications in industry, Linked Lists make for an important
and effective educational tool in helping develop a student’s mental model on what data structures
actually are to begin with.</p>
<p name="f7f2" id="f7f2" class="graf graf--p graf-after--p">Linked lists are simple. They have many
compelling, reoccurring edge cases to consider that emphasize to the student the need for care and
intent while implementing data structures. They can be applied as the underlying data structure while
implementing a variety of other prevalent abstract data types, such as Lists, Stacks, and Queues, and
they have a level of versatility high enough to clearly illustrate the value of the Object Oriented
Programming paradigm.</p>
<p name="3aa7" id="3aa7" class="graf graf--p graf-after--p">They also come up in software engineering
interviews quite often.</p>
<figure name="5a4f" id="5a4f" class="graf graf--figure graf-after--p"><img class="graf-image"
data-image-id="0*OYmTpAK6tyDQzoIE.gif" data-width="600" data-height="194"
src="https://cdn-images-1.medium.com/max/800/0*OYmTpAK6tyDQzoIE.gif"></figure>
<h3 name="bce6" id="bce6" class="graf graf--h3 graf-after--figure">What is a Linked List?</h3>
<p name="c91f" id="c91f" class="graf graf--p graf-after--h3">A Linked List data structure represents a
linear sequence of “vertices” (or “nodes”), and tracks three important properties.</p>
<p name="a8ba" id="a8ba" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong">Linked List Properties:</strong></p>
<figure name="7596" id="7596" class="graf graf--figure graf-after--p"><img class="graf-image"
data-image-id="1*z-i1wE6QPOtqxGiW_B6WuA.png" data-width="390" data-height="89"
src="https://cdn-images-1.medium.com/max/800/1*z-i1wE6QPOtqxGiW_B6WuA.png"></figure>
<p name="b9fc" id="b9fc" class="graf graf--p graf-after--figure">The data being tracked by a particular
Linked List does not live inside the Linked List instance itself. Instead, each vertex is actually an
instance of an even simpler, smaller data structure, often referred to as a “Node”.</p>
<p name="f1cc" id="f1cc" class="graf graf--p graf-after--p">Depending on the type of Linked List (there
are many), Node instances track some very important properties as well.</p>
<p name="9309" id="9309" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong">Linked List Node Properties:</strong></p>
<figure name="ae71" id="ae71" class="graf graf--figure graf-after--p"><img class="graf-image"
data-image-id="1*vagMBs5Quwv8b8tvF4W6Og.png" data-width="489" data-height="112"
src="https://cdn-images-1.medium.com/max/800/1*vagMBs5Quwv8b8tvF4W6Og.png"></figure>
<p name="41c6" id="41c6" class="graf graf--p graf-after--figure">Property Description <code
class="markup--code markup--p-code">value</code>: The actual value this node represents.<code
class="markup--code markup--p-code">next</code>The next node in the list (relative to this node).<code
class="markup--code markup--p-code">previous</code>The previous node in the list (relative to this
node).</p>
<p name="2f6a" id="2f6a" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong">NOTE:</strong> The <code
class="markup--code markup--p-code">previous</code> property is for Doubly Linked Lists only!</p>
<p name="434b" id="434b" class="graf graf--p graf-after--p">Linked Lists contain <em
class="markup--em markup--p-em">ordered</em> data, just like arrays. The first node in the list is,
indeed, first. From the perspective of the very first node in the list, the <em
class="markup--em markup--p-em">next</em> node is the second node. From the perspective of the second
node in the list, the <em class="markup--em markup--p-em">previous</em> node is the first node, and the
<em class="markup--em markup--p-em">next</em> node is the third node. And so it goes.</p>
<h4 name="249d" id="249d" class="graf graf--h4 graf--startsWithDoubleQuote graf-after--p">“So…this sounds
a lot like an Array…”</h4>
<p name="2ea8" id="2ea8" class="graf graf--p graf-after--h4">Admittedly, this does <em
class="markup--em markup--p-em">sound</em> a lot like an Array so far, and that’s because Arrays and
Linked Lists are both implementations of the List ADT. However, there is an incredibly important
distinction to be made between Arrays and Linked Lists, and that is how they <em
class="markup--em markup--p-em">physically store</em> their data. (As opposed to how they <em
class="markup--em markup--p-em">represent</em> the order of their data.)</p>
<p name="853c" id="853c" class="graf graf--p graf-after--p">Recall that Arrays contain <em
class="markup--em markup--p-em">contiguous</em> data. Each element of an array is actually stored <em
class="markup--em markup--p-em">next to</em> it’s neighboring element <em
class="markup--em markup--p-em">in the actual hardware of your machine</em>, in a single continuous
block in memory.</p>
<p name="0b19" id="0b19" class="graf graf--p graf-after--p"><em class="markup--em markup--p-em">An Array’s
contiguous data being stored in a continuous block of addresses in memory.</em></p>
<p name="398d" id="398d" class="graf graf--p graf-after--p">Unlike Arrays, Linked Lists contain <em
class="markup--em markup--p-em">non-contiguous</em> data. Though Linked Lists <em
class="markup--em markup--p-em">represent</em> data that is ordered linearly, that mental model is
just that — an interpretation of the <em class="markup--em markup--p-em">representation</em> of
information, not reality.</p>
<p name="0527" id="0527" class="graf graf--p graf-after--p">In reality, in the actual hardware of your
machine, whether it be in disk or in memory, a Linked List’s Nodes are not stored in a single continuous
block of addresses. Rather, Linked List Nodes live at randomly distributed addresses throughout your
machine! The only reason we know which node comes next in the list is because we’ve assigned its
reference to the current node’s <code class="markup--code markup--p-code">next</code> pointer.</p>
<p name="09de" id="09de" class="graf graf--p graf-after--p"><em class="markup--em markup--p-em">A Singly
Linked List’s non-contiguous data (Nodes) being stored at randomly distributed addresses in
memory.</em></p>
<p name="1dd9" id="1dd9" class="graf graf--p graf-after--p">For this reason, Linked List Nodes have <em
class="markup--em markup--p-em">no indices</em>, and no <em class="markup--em markup--p-em">random
access</em>. Without random access, we do not have the ability to look up an individual Linked List
Node in constant time. Instead, to find a particular Node, we have to start at the very first Node and
iterate through the Linked List one node at a time, checking each Node’s <em
class="markup--em markup--p-em">next</em> Node until we find the one we’re interested in.</p>
<p name="a379" id="a379" class="graf graf--p graf-after--p">So when implementing a Linked List, we
actually must implement both the Linked List class <em class="markup--em markup--p-em">and</em> the Node
class. Since the actual data lives in the Nodes, it’s simpler to implement the Node class first.</p>
<h3 name="dd2b" id="dd2b" class="graf graf--h3 graf-after--p">Types of Linked Lists</h3>
<p name="b976" id="b976" class="graf graf--p graf-after--h3">There are four flavors of Linked List you
should be familiar with when walking into your job interviews.</p>
<p name="fc44" id="fc44" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong">Linked List Types:</strong></p>
<figure name="c408" id="c408" class="graf graf--figure graf-after--p"><img class="graf-image"
data-image-id="1*ZoYIEJaOpPiYAuqtPLt8yw.png" data-width="691" data-height="132"
src="https://cdn-images-1.medium.com/max/800/1*ZoYIEJaOpPiYAuqtPLt8yw.png"></figure>
<p name="3998" id="3998" class="graf graf--p graf-after--figure"><strong
class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">Note:</em></strong><em
class="markup--em markup--p-em"> These Linked List types are not always mutually exclusive.</em></p>
<p name="cd5e" id="cd5e" class="graf graf--p graf-after--p">For instance:</p>
<ul class="postList">
<li name="a0e8" id="a0e8" class="graf graf--li graf-after--p">Any type of Linked List can be implemented
Circularly (e.g. A Circular Doubly Linked List).</li>
<li name="c0ff" id="c0ff" class="graf graf--li graf-after--li">A Doubly Linked List is actually just a
special case of a Multiply Linked List.</li>
</ul>
<p name="49c5" id="49c5" class="graf graf--p graf-after--li">You are most likely to encounter Singly and
Doubly Linked Lists in your upcoming job search, so we are going to focus exclusively on those two
moving forward. However, in more senior level interviews, it is very valuable to have some familiarity
with the other types of Linked Lists. Though you may not actually code them out, <em
class="markup--em markup--p-em">you will win extra points by illustrating your ability to weigh the
tradeoffs of your technical decisions</em> by discussing how your choice of Linked List type may
affect the efficiency of the solutions you propose.</p>
<h3 name="5711" id="5711" class="graf graf--h3 graf-after--p">Linked List Methods</h3>
</div>
<div class="section-inner sectionLayout--outsetColumn">
<figure name="5ebb" id="5ebb" class="graf graf--figure graf--layoutOutsetCenter graf-after--h3"><img
class="graf-image" data-image-id="1*9EnhpQAeV03_DyEZIyiTCw.png" data-width="1255" data-height="674"
src="https://cdn-images-1.medium.com/max/1200/1*9EnhpQAeV03_DyEZIyiTCw.png"></figure>
</div>
<div class="section-inner sectionLayout--insetColumn">
<p name="9921" id="9921" class="graf graf--p graf-after--figure">Linked Lists are great foundation
builders when learning about data structures because they share a number of similar methods (and edge
cases) with many other common data structures. You will find that many of the concepts discussed here
will repeat themselves as we dive into some of the more complex non-linear data structures later on,
like Trees and Graphs.</p>
<figure name="628f" id="628f" class="graf graf--figure graf--iframe graf-after--p">
<script src="https://gist.github.com/bgoonz/50b1eedffde6353523e0909bcb903330.js"></script>
</figure>
<h3 name="c512" id="c512" class="graf graf--h3 graf-after--figure">Time and Space Complexity Analysis</h3>
<p name="2471" id="2471" class="graf graf--p graf-after--h3">Before we begin our analysis, here is a quick
summary of the Time and Space constraints of each Linked List Operation. The complexities below apply to
both Singly and Doubly Linked Lists:</p>
</div>
<div class="section-inner sectionLayout--outsetColumn">
<figure name="570c" id="570c" class="graf graf--figure graf--layoutOutsetCenter graf-after--p"><img
class="graf-image" data-image-id="1*Enb9YaqRxzS87ML83Loasw.png" data-width="1282" data-height="406"
src="https://cdn-images-1.medium.com/max/1200/1*Enb9YaqRxzS87ML83Loasw.png"></figure>
</div>
<div class="section-inner sectionLayout--insetColumn">
<p name="e787" id="e787" class="graf graf--p graf-after--figure">Before moving forward, see if you can
reason to yourself why each operation has the time and space complexity listed above!</p>
<h3 name="37ec" id="37ec" class="graf graf--h3 graf-after--p">Time Complexity — Access and Search</h3>
<h4 name="339c" id="339c" class="graf graf--h4 graf-after--h3">Scenarios</h4>
<ol class="postList">
<li name="16fe" id="16fe" class="graf graf--li graf-after--h4">We have a Linked List, and we’d like to
find the 8th item in the list.</li>
<li name="a9f7" id="a9f7" class="graf graf--li graf-after--li">We have a Linked List of sorted alphabet
letters, and we’d like to see if the letter “Q” is inside that list.</li>
</ol>
<h4 name="572c" id="572c" class="graf graf--h4 graf-after--li">Discussion</h4>
<p name="c598" id="c598" class="graf graf--p graf-after--h4">Unlike Arrays, Linked Lists Nodes are not
stored contiguously in memory, and thereby do not have an indexed set of memory addresses at which we
can quickly lookup individual nodes in constant time. Instead, we must begin at the head of the list (or
possibly at the tail, if we have a Doubly Linked List), and iterate through the list until we arrive at
the node of interest.</p>
<p name="40ab" id="40ab" class="graf graf--p graf-after--p">In Scenario 1, we’ll know we’re there because
we’ve iterated 8 times. In Scenario 2, we’ll know we’re there because, while iterating, we’ve checked
each node’s value and found one that matches our target value, “Q”.</p>
<p name="6ebb" id="6ebb" class="graf graf--p graf-after--p">In the worst case scenario, we may have to
traverse the entire Linked List until we arrive at the final node. This makes both Access & Search
<strong class="markup--strong markup--p-strong">Linear Time</strong> operations.</p>
<h3 name="e56f" id="e56f" class="graf graf--h3 graf-after--p">Time Complexity — Insertion and Deletion
</h3>
<h4 name="f162" id="f162" class="graf graf--h4 graf-after--h3">Scenarios</h4>
<ol class="postList">
<li name="2462" id="2462" class="graf graf--li graf-after--h4">We have an empty Linked List, and we’d
like to insert our first node.</li>
<li name="ae0b" id="ae0b" class="graf graf--li graf-after--li">We have a Linked List, and we’d like to
insert or delete a node at the Head or Tail.</li>
<li name="290b" id="290b" class="graf graf--li graf-after--li">We have a Linked List, and we’d like to
insert or delete a node from somewhere in the middle of the list.</li>
</ol>
<h4 name="57d9" id="57d9" class="graf graf--h4 graf-after--li">Discussion</h4>
<p name="c3c4" id="c3c4" class="graf graf--p graf-after--h4">Since we have our Linked List Nodes stored in
a non-contiguous manner that relies on pointers to keep track of where the next and previous nodes live,
Linked Lists liberate us from the linear time nature of Array insertions and deletions. We no longer
have to adjust the position at which each node/element is stored after making an insertion at a
particular position in the list. Instead, if we want to insert a new node at position <code
class="markup--code markup--p-code">i</code>, we can simply:</p>
<ol class="postList">
<li name="7675" id="7675" class="graf graf--li graf-after--p">Create a new node.</li>
<li name="adf9" id="adf9" class="graf graf--li graf-after--li">Set the new node’s <code
class="markup--code markup--li-code">next</code> and <code
class="markup--code markup--li-code">previous</code> pointers to the nodes that live at positions
<code class="markup--code markup--li-code">i</code> and <code class="markup--code markup--li-code">i -
1</code>, respectively.</li>
<li name="1bf6" id="1bf6" class="graf graf--li graf-after--li">Adjust the <code
class="markup--code markup--li-code">next</code> pointer of the node that lives at position <code
class="markup--code markup--li-code">i - 1</code> to point to the new node.</li>
<li name="9580" id="9580" class="graf graf--li graf-after--li">Adjust the <code
class="markup--code markup--li-code">previous</code> pointer of the node that lives at position
<code class="markup--code markup--li-code">i</code> to point to the new node.</li>
</ol>
<p name="34de" id="34de" class="graf graf--p graf-after--li">And we’re done, in Constant Time. No
iterating across the entire list necessary.</p>
<p name="0bfb" id="0bfb" class="graf graf--p graf--startsWithDoubleQuote graf-after--p">“But hold on one
second,” you may be thinking. “In order to insert a new node in the middle of the list, don’t we have to
lookup its position? Doesn’t that take linear time?!”</p>
<p name="3470" id="3470" class="graf graf--p graf-after--p">Yes, it is tempting to call insertion or
deletion in the middle of a Linked List a linear time operation since there is lookup involved. However,
it’s usually the case that you’ll already have a reference to the node where your desired insertion or
deletion will occur.</p>
<p name="87ac" id="87ac" class="graf graf--p graf-after--p">For this reason, we separate the Access time
complexity from the Insertion/Deletion time complexity, and formally state that Insertion and Deletion
in a Linked List are <strong class="markup--strong markup--p-strong">Constant Time</strong> across the
board.</p>
<p name="e2c6" id="e2c6" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">Note:</em></strong><em
class="markup--em markup--p-em"> Without a reference to the node at which an insertion or deletion
will occur, due to linear time lookup, an insertion or deletion in the middle of a Linked List will
still take Linear Time, sum total.</em></p>
<h3 name="1f48" id="1f48" class="graf graf--h3 graf-after--p">Space Complexity</h3>
<h4 name="c97e" id="c97e" class="graf graf--h4 graf-after--h3">Scenarios</h4>
<ol class="postList">
<li name="12d2" id="12d2" class="graf graf--li graf-after--h4">We’re given a Linked List, and need to
operate on it.</li>
<li name="7c5f" id="7c5f" class="graf graf--li graf-after--li">We’ve decided to create a new Linked List
as part of strategy to solve some problem.</li>
</ol>
<h4 name="0a10" id="0a10" class="graf graf--h4 graf-after--li">Discussion</h4>
<p name="ea2b" id="ea2b" class="graf graf--p graf-after--h4">It’s obvious that Linked Lists have one node
for every one item in the list, and for that reason we know that Linked Lists take up Linear Space in
memory. However, when asked in an interview setting what the Space Complexity <em
class="markup--em markup--p-em">of your solution</em> to a problem is, it’s important to recognize the
difference between the two scenarios above.</p>
<p name="4159" id="4159" class="graf graf--p graf-after--p">In Scenario 1, we <em
class="markup--em markup--p-em">are not</em> creating a new Linked List. We simply need to operate on
the one given. Since we are not storing a <em class="markup--em markup--p-em">new</em> node for every
node represented in the Linked List we are provided, our solution is <em
class="markup--em markup--p-em">not necessarily</em> linear in space.</p>
<p name="6549" id="6549" class="graf graf--p graf-after--p">In Scenario 2, we <em
class="markup--em markup--p-em">are</em> creating a new Linked List. If the number of nodes we create
is linearly correlated to the size of our input data, we are now operating in Linear Space.</p>
<p name="8523" id="8523" class="graf graf--p graf-after--p graf--trailing"><strong
class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">Note</em></strong><em
class="markup--em markup--p-em">: Linked Lists can be traversed both iteratively and recursively. If
you choose to traverse a Linked List recursively, there will be a recursive function call added to the
call stack for every node in the Linked List. Even if you’re provided the Linked List, as in Scenario
1, you will still use Linear Space in the call stack, and that counts.</em></p>
</div>
</div>
</section>
<section name="1d05" class="section section--body">
<div class="section-divider">
<hr class="section-divider">
</div>
<div class="section-content">
<div class="section-inner sectionLayout--insetColumn">
<h3 name="c32d" id="c32d" class="graf graf--h3 graf--leading">Stacks and Queues</h3>
<p name="fb62" id="fb62" class="graf graf--p graf-after--h3">Stacks and Queues aren’t really “data
structures” by the strict definition of the term. The more appropriate terminology would be to call them
abstract data types (ADTs), meaning that their definitions are more conceptual and related to the rules
governing their user-facing behaviors rather than their core implementations.</p>
<p name="96ba" id="96ba" class="graf graf--p graf-after--p">For the sake of simplicity, we’ll refer to
them as data structures and ADTs interchangeably throughout the course, but the distinction is an
important one to be familiar with as you level up as an engineer.</p>
<p name="f8a6" id="f8a6" class="graf graf--p graf-after--p">Now that that’s out of the way, Stacks and
Queues represent a linear collection of nodes or values. In this way, they are quite similar to the
Linked List data structure we discussed in the previous section. In fact, you can even use a modified
version of a Linked List to implement each of them. (Hint, hint.)</p>
<p name="d0ac" id="d0ac" class="graf graf--p graf-after--p">These two ADTs are similar to each other as
well, but each obey their own special rule regarding the order with which Nodes can be added and removed
from the structure.</p>
<p name="da7c" id="da7c" class="graf graf--p graf-after--p">Since we’ve covered Linked Lists in great
length, these two data structures will be quick and easy. Let’s break them down individually in the next
couple of sections.</p>
<h3 name="b0c0" id="b0c0" class="graf graf--h3 graf-after--p">What is a Stack?</h3>
<p name="488e" id="488e" class="graf graf--p graf-after--h3">Stacks are a Last In First Out (LIFO) data
structure. The last Node added to a stack is always the first Node to be removed, and as a result, the
first Node added is always the last Node removed.</p>
<p name="4f50" id="4f50" class="graf graf--p graf-after--p">The name Stack actually comes from this
characteristic, as it is helpful to visualize the data structure as a vertical stack of items.
Personally, I like to think of a Stack as a stack of plates, or a stack of sheets of paper. This seems
to make them more approachable, because the analogy relates to something in our everyday lives.</p>
<p name="0875" id="0875" class="graf graf--p graf-after--p">If you can imagine adding items to, or
removing items from, a Stack of…literally anything…you’ll realize that every (sane) person naturally
obeys the LIFO rule.</p>
<p name="65c8" id="65c8" class="graf graf--p graf-after--p">We add things to the <em
class="markup--em markup--p-em">top</em> of a stack. We remove things from the <em
class="markup--em markup--p-em">top</em> of a stack. We never add things to, or remove things from,
the <em class="markup--em markup--p-em">bottom</em> of the stack. That’s just crazy.</p>
<p name="c440" id="c440" class="graf graf--p graf-after--p">Note: We can use JavaScript Arrays to
implement a basic stack. <code class="markup--code markup--p-code">Array#push</code> adds to the top of
the stack and <code class="markup--code markup--p-code">Array#pop</code> will remove from the top of the
stack. In the exercise that follows, we’ll build our own Stack class from scratch (without using any
arrays). In an interview setting, your evaluator may be okay with you using an array as a stack.</p>
<figure name="36e3" id="36e3" class="graf graf--figure graf--iframe graf-after--p graf--trailing">
<script src="https://gist.github.com/bgoonz/a3c27a5126ed87a5f708b11bb3032994.js"></script>
</figure>
</div>
</div>
</section>
<section name="c9a7" class="section section--body">
<div class="section-divider">
<hr class="section-divider">
</div>
<div class="section-content">
<div class="section-inner sectionLayout--insetColumn">
<h3 name="e178" id="e178" class="graf graf--h3 graf--leading">What is a Queue?</h3>
<p name="f317" id="f317" class="graf graf--p graf-after--h3">Queues are a First In First Out (FIFO) data
structure. The first Node added to the queue is always the first Node to be removed.</p>
<p name="665f" id="665f" class="graf graf--p graf-after--p">The name Queue comes from this characteristic,
as it is helpful to visualize this data structure as a horizontal line of items with a beginning and an
end. Personally, I like to think of a Queue as the line one waits on for an amusement park, at a grocery
store checkout, or to see the teller at a bank.</p>
<p name="8468" id="8468" class="graf graf--p graf-after--p">If you can imagine a queue of humans
waiting…again, for literally anything…you’ll realize that <em class="markup--em markup--p-em">most</em>
people (the civil ones) naturally obey the FIFO rule.</p>
<p name="031c" id="031c" class="graf graf--p graf-after--p">People add themselves to the <em
class="markup--em markup--p-em">back</em> of a queue, wait their turn in line, and make their way
toward the <em class="markup--em markup--p-em">front</em>. People exit from the <em
class="markup--em markup--p-em">front</em> of a queue, but only when they have made their way to being
first in line.</p>
<p name="92ae" id="92ae" class="graf graf--p graf-after--p">We never add ourselves to the front of a queue
(unless there is no one else in line), otherwise we would be “cutting” the line, and other humans don’t
seem to appreciate that.</p>
<p name="3952" id="3952" class="graf graf--p graf-after--p">Note: We can use JavaScript Arrays to
implement a basic queue. <code class="markup--code markup--p-code">Array#push</code> adds to the back
(enqueue) and <code class="markup--code markup--p-code">Array#shift</code> will remove from the front
(dequeue). In the exercise that follows, we’ll build our own Queue class from scratch (without using any
arrays). In an interview setting, your evaluator may be okay with you using an array as a queue.</p>
<h3 name="0ae7" id="0ae7" class="graf graf--h3 graf-after--p">Stack and Queue Properties</h3>
<p name="0011" id="0011" class="graf graf--p graf-after--h3">Stacks and Queues are so similar in
composition that we can discuss their properties together. They track the following three properties:
</p>
<p name="a7fa" id="a7fa" class="graf graf--p graf-after--p"><strong
class="markup--strong markup--p-strong">Stack Properties | Queue Properties:</strong></p>
<figure name="7c4b" id="7c4b" class="graf graf--figure graf-after--p"><img class="graf-image"
data-image-id="1*aZCnZJzaeY74DTb2CTRuFA.png" data-width="662" data-height="562" alt="Stacks and Queues are so similar in composition that we can discuss their properties together. They track the following three properties:
Stack Properties | Queue Properties:
Stack Property Description Queue Property Description
top The first node in the Stack front The first node in the Queue.
— — Stacks do not have an equivalent back The last node in the Queue.
length The number of nodes in the Stack; the Stack’s length. length The number of nodes in the Queue; the Queue’s length.
N" src="https://cdn-images-1.medium.com/max/800/1*aZCnZJzaeY74DTb2CTRuFA.png"></figure>
<p name="d438" id="d438" class="graf graf--p graf-after--figure graf--trailing">Notice that rather than
having a <code class="markup--code markup--p-code">head</code> and a <code
class="markup--code markup--p-code">tail</code> like Linked Lists, Stacks have a <code
class="markup--code markup--p-code">top</code>, and Queues have a <code
class="markup--code markup--p-code">front</code> and a <code
class="markup--code markup--p-code">back</code> instead. Stacks don’t have the equivalent of a <code
class="markup--code markup--p-code">tail</code> because you only ever push or pop things off the top
of Stacks. These properties are essentially the same; pointers to the end points of the respective List
ADT where important actions way take place. The differences in naming conventions are strictly for human
comprehension.</p>
</div>
</div>
</section>
<section name="27ad" class="section section--body section--last">
<div class="section-divider">
<hr class="section-divider">
</div>
<div class="section-content">
<div class="section-inner sectionLayout--insetColumn">
<p name="9128" id="9128" class="graf graf--p graf--leading">Similarly to Linked Lists, the values stored
inside a Stack or a Queue are actually contained within Stack Node and Queue Node instances. Stack,
Queue, and Singly Linked List Nodes are all identical, but just as a reminder and for the sake of
completion, these List Nodes track the following two properties:</p>
<h3 name="7d43" id="7d43" class="graf graf--h3 graf-after--p">Time and Space Complexity Analysis</h3>
<p name="756f" id="756f" class="graf graf--p graf-after--h3">Before we begin our analysis, here is a quick
summary of the Time and Space constraints of each Stack Operation.</p>
<p name="2a25" id="2a25" class="graf graf--p graf-after--p">Data Structure Operation Time Complexity
(Avg)Time Complexity (Worst)Space Complexity (Worst)Access<code
class="markup--code markup--p-code">Θ(n)O(n)O(n)</code>Search<code
class="markup--code markup--p-code">Θ(n)O(n)O(n)</code>Insertion<code
class="markup--code markup--p-code">Θ(1)O(1)O(n)</code>Deletion<code
class="markup--code markup--p-code">Θ(1)O(1)O(n)</code></p>
<p name="4028" id="4028" class="graf graf--p graf-after--p">Before moving forward, see if you can reason
to yourself why each operation has the time and space complexity listed above!</p>
<h4 name="c6cc" id="c6cc" class="graf graf--h4 graf-after--p">Time Complexity — Access and Search</h4>
<p name="ea59" id="ea59" class="graf graf--p graf-after--h4">When the Stack ADT was first conceived, its
inventor definitely did not prioritize searching and accessing individual Nodes or values in the list.
The same idea applies for the Queue ADT. There are certainly better data structures for speedy search
and lookup, and if these operations are a priority for your use case, it would be best to choose
something else!</p>
<p name="5a0b" id="5a0b" class="graf graf--p graf-after--p">Search and Access are both linear time
operations for Stacks and Queues, and that shouldn’t be too unclear. Both ADTs are nearly identical to
Linked Lists in this way. The only way to find a Node somewhere in the middle of a Stack or a Queue, is
to start at the <code class="markup--code markup--p-code">top</code> (or the <code
class="markup--code markup--p-code">back</code>) and traverse downward (or forward) toward the <code
class="markup--code markup--p-code">bottom</code> (or <code
class="markup--code markup--p-code">front</code>) one node at a time via each Node’s <code
class="markup--code markup--p-code">next</code> property.</p>
<p name="9706" id="9706" class="graf graf--p graf-after--p">This is a linear time operation, O(n).</p>
<h4 name="fa3e" id="fa3e" class="graf graf--h4 graf-after--p">Time Complexity — Insertion and Deletion
</h4>
<p name="3681" id="3681" class="graf graf--p graf-after--h4">For Stacks and Queues, insertion and deletion
is what it’s all about. If there is one feature a Stack absolutely must have, it’s constant time
insertion and removal to and from the <code class="markup--code markup--p-code">top</code> of the Stack
(FIFO). The same applies for Queues, but with insertion occurring at the <code
class="markup--code markup--p-code">back</code> and removal occurring at the <code
class="markup--code markup--p-code">front</code> (LIFO).</p>
<p name="0fee" id="0fee" class="graf graf--p graf-after--p">Think about it. When you add a plate to the
top of a stack of plates, do you have to iterate through all of the other plates first to do so? Of
course not. You simply add your plate to the top of the stack, and that’s that. The concept is the same
for removal.</p>
<p name="456e" id="456e" class="graf graf--p graf-after--p">Therefore, Stacks and Queues have constant
time Insertion and Deletion via their <code class="markup--code markup--p-code">push</code> and <code
class="markup--code markup--p-code">pop</code> or <code
class="markup--code markup--p-code">enqueue</code> and <code
class="markup--code markup--p-code">dequeue</code> methods, O(1).</p>
<h4 name="f038" id="f038" class="graf graf--h4 graf-after--p">Space Complexity</h4>
<p name="e561" id="e561" class="graf graf--p graf-after--h4">The space complexity of Stacks and Queues is
very simple. Whether we are instantiating a new instance of a Stack or Queue to store a set of data, or
we are using a Stack or Queue as part of a strategy to solve some problem, Stacks and Queues always
store one Node for each value they receive as input.</p>
<p name="4909" id="4909" class="graf graf--p graf-after--p">For this reason, we always consider Stacks and
Queues to have a linear space complexity, O(n).</p>
<h3 name="bd0e" id="bd0e" class="graf graf--h3 graf-after--p">When should we use Stacks and Queues?</h3>
<p name="580f" id="580f" class="graf graf--p graf-after--h3">At this point, we’ve done a lot of work
understanding the ins and outs of Stacks and Queues, but we still haven’t really discussed what we can
use them for. The answer is actually…a lot!</p>
<p name="a404" id="a404" class="graf graf--p graf-after--p">For one, Stacks and Queues can be used as
intermediate data structures while implementing some of the more complicated data structures and methods
we’ll see in some of our upcoming sections.</p>
<p name="6ab5" id="6ab5" class="graf graf--p graf-after--p">For example, the implementation of the
breadth-first Tree traversal algorithm takes advantage of a Queue instance, and the depth-first Graph
traversal algorithm exploits the benefits of a Stack instance.</p>
<p name="90ac" id="90ac" class="graf graf--p graf-after--p">Additionally, Stacks and Queues serve as the
essential underlying data structures to a wide variety of applications you use all the time. Just to
name a few:</p>
<h4 name="901a" id="901a" class="graf graf--h4 graf-after--p">Stacks</h4>
<ul class="postList">
<li name="f63a" id="f63a" class="graf graf--li graf-after--h4">The Call Stack is a Stack data structure,
and is used to manage the order of function invocations in your code.</li>
<li name="6b24" id="6b24" class="graf graf--li graf-after--li">Browser History is often implemented
using a Stack, with one great example being the browser history object in the very popular React
Router module.</li>
<li name="098f" id="098f" class="graf graf--li graf-after--li">Undo/Redo functionality in just about any
application. For example:</li>
<li name="f15d" id="f15d" class="graf graf--li graf-after--li">When you’re coding in your text editor,
each of the actions you take on your keyboard are recorded by <code
class="markup--code markup--li-code">push</code>ing that event to a Stack.</li>
<li name="e303" id="e303" class="graf graf--li graf-after--li">When you hit [cmd + z] to undo your most
recent action, that event is <code class="markup--code markup--li-code">pop</code>ed off the Stack,
because the last event that occured should be the first one to be undone (LIFO).</li>
<li name="9248" id="9248" class="graf graf--li graf-after--li">When you hit [cmd + y] to redo your most
recent action, that event is <code class="markup--code markup--li-code">push</code>ed back onto the
Stack.</li>
</ul>
<h4 name="12c3" id="12c3" class="graf graf--h4 graf-after--li">Queues</h4>
<ul class="postList">
<li name="7c8d" id="7c8d" class="graf graf--li graf-after--h4">Printers use a Queue to manage incoming
jobs to ensure that documents are printed in the order they are received.</li>
<li name="89e7" id="89e7" class="graf graf--li graf-after--li">Chat rooms, online video games, and
customer service phone lines use a Queue to ensure that patrons are served in the order they arrive.
</li>
<li name="c02a" id="c02a" class="graf graf--li graf-after--li">In the case of a Chat Room, to be
admitted to a size-limited room.</li>
<li name="353e" id="353e" class="graf graf--li graf-after--li">In the case of an Online Multi-Player
Game, players wait in a lobby until there is enough space and it is their turn to be admitted to a
game.</li>
<li name="6a8e" id="6a8e" class="graf graf--li graf-after--li">In the case of a Customer Service Phone
Line…you get the point.</li>
<li name="0ad5" id="0ad5" class="graf graf--li graf-after--li">As a more advanced use case, Queues are
often used as components or services in the system design of a service-oriented architecture. A very
popular and easy to use example of this is Amazon’s Simple Queue Service (SQS), which is a part of
their Amazon Web Services (AWS) offering.</li>
<li name="48e7" id="48e7" class="graf graf--li graf-after--li">You would add this service to your system
between two other services, one that is sending information for processing, and one that is receiving
information to be processed, when the volume of incoming requests is high and the integrity of the
order with which those requests are processed must be maintained.</li>
</ul>
<figure name="8851" id="8851" class="graf graf--figure graf--iframe graf-after--li">
<script src="https://gist.github.com/bgoonz/af7cddac66b05b47f797a539929e8976.js"></script>
</figure>
<p name="eba3" id="eba3" class="graf graf--p graf-after--figure"><strong
class="markup--strong markup--p-strong">If you found this guide helpful feel free to checkout my other
articles:</strong></p>
<div name="9171" id="9171" class="graf graf--mixtapeEmbed graf-after--p"><a
href="https://bryanguner.medium.com/a-list-of-all-of-my-articles-to-link-to-future-posts-1f6f88ebdf5b"
data-href="https://bryanguner.medium.com/a-list-of-all-of-my-articles-to-link-to-future-posts-1f6f88ebdf5b"
class="markup--anchor markup--mixtapeEmbed-anchor"
title="https://bryanguner.medium.com/a-list-of-all-of-my-articles-to-link-to-future-posts-1f6f88ebdf5b"><strong
class="markup--strong markup--mixtapeEmbed-strong">A list of all of my articles to link to future
posts</strong><br><em class="markup--em markup--mixtapeEmbed-em">You should probably skip this one…
seriously it’s just for internal use!</em>bryanguner.medium.com</a><a
href="https://bryanguner.medium.com/a-list-of-all-of-my-articles-to-link-to-future-posts-1f6f88ebdf5b"
class="js-mixtapeImage mixtapeImage mixtapeImage--empty u-ignoreBlock"
data-media-id="dd1d7f5e952c9d85244acd597e1e7811"></a></div>
<p name="ce89" id="ce89" class="graf graf--p graf-after--mixtapeEmbed"><strong
class="markup--strong markup--p-strong">Further resources:</strong></p>
<div name="1c2f" id="1c2f" class="graf graf--mixtapeEmbed graf-after--p"><a
href="https://gist.github.com/bgoonz" data-href="https://gist.github.com/bgoonz"
class="markup--anchor markup--mixtapeEmbed-anchor" title="https://gist.github.com/bgoonz"><strong
class="markup--strong markup--mixtapeEmbed-strong">bgoonz’s gists</strong><br><em
class="markup--em markup--mixtapeEmbed-em">Instantly share code, notes, and snippets. Web Developer,
Electrical Engineer JavaScript | CSS | Bootstrap | Python |…</em>gist.github.com</a><a
href="https://gist.github.com/bgoonz" class="js-mixtapeImage mixtapeImage u-ignoreBlock"
data-media-id="ab25adbb500306703daab23d08a7739a" data-thumbnail-img-id="0*3O67jrqm3EHjTK2H"
style="background-image: url(https://cdn-images-1.medium.com/fit/c/160/160/0*3O67jrqm3EHjTK2H);"></a>
</div>
<div name="3585" id="3585" class="graf graf--mixtapeEmbed graf-after--mixtapeEmbed"><a
href="https://github.com/bgoonz" data-href="https://github.com/bgoonz"
class="markup--anchor markup--mixtapeEmbed-anchor" title="https://github.com/bgoonz"><strong
class="markup--strong markup--mixtapeEmbed-strong">bgoonz — Overview</strong><br><em
class="markup--em markup--mixtapeEmbed-em">Web Developer, Electrical Engineer JavaScript | CSS |
Bootstrap | Python | React | Node.js | Express | Sequelize…</em>github.com</a><a
href="https://github.com/bgoonz" class="js-mixtapeImage mixtapeImage u-ignoreBlock"
data-media-id="6ee74d5200d495ddc7ddad0c92bd6dce" data-thumbnail-img-id="0*Udg3rbeFyslZ9dyl"
style="background-image: url(https://cdn-images-1.medium.com/fit/c/160/160/0*Udg3rbeFyslZ9dyl);"></a>
</div>
<div name="4bce" id="4bce" class="graf graf--mixtapeEmbed graf-after--mixtapeEmbed"><a
href="https://web-dev-resource-hub.netlify.app/" data-href="https://web-dev-resource-hub.netlify.app/"
class="markup--anchor markup--mixtapeEmbed-anchor"
title="https://web-dev-resource-hub.netlify.app/"><strong
class="markup--strong markup--mixtapeEmbed-strong">Web-Dev-Resource-Hub</strong><br><em
class="markup--em markup--mixtapeEmbed-em">Edit
description</em>web-dev-resource-hub.netlify.app</a><a
href="https://web-dev-resource-hub.netlify.app/"
class="js-mixtapeImage mixtapeImage mixtapeImage--empty u-ignoreBlock"
data-media-id="142b348a1c3b7cab095decda3afd6236"></a></div>
<p name="52f4" id="52f4" class="graf graf--p graf-after--mixtapeEmbed"><strong
class="markup--strong markup--p-strong">Here’s a live code editor where you can mess with any of the
examples:</strong></p>
</div>
<div class="section-inner sectionLayout--outsetColumn">
<figure name="a042" id="a042"
class="graf graf--figure graf--iframe graf--layoutOutsetCenter graf-after--p"><iframe
src="https://repl.it/@bgoonz/DS-ALGO-OFFICIAL-2?lite=true" width="1192" height="894" frameborder="0"
scrolling="no"></iframe></figure>
</div>
<div class="section-inner sectionLayout--insetColumn">
<figure name="3c28" id="3c28" class="graf graf--figure graf-after--figure graf--trailing"><img
class="graf-image" data-image-id="0*zhC6dP1hb2rq2qt2.png" data-width="1000" data-height="500"
data-is-featured="true" alt="Stack & Queue Data Structure Image"
src="https://cdn-images-1.medium.com/max/800/0*zhC6dP1hb2rq2qt2.png"></figure>
</div>
</div>
</section>
</section>
<footer>
<p>By <a href="https://medium.com/@bryanguner" class="p-author h-card">Bryan Guner</a> on <a
href="https://medium.com/p/88466fae0fbb"><time class="dt-published"
datetime="2021-03-22T22:03:38.928Z">March 22, 2021</time></a>.</p>
<p><a href="https://medium.com/@bryanguner/lists-stacks-and-queues-in-javascript-88466fae0fbb"
class="p-canonical">Canonical link</a></p>
<p>Exported from <a href="https://medium.com">Medium</a> on April 3, 2021.</p>
</footer>
</article>
</body>
</html>