ifndef::imagesdir[]
:imagesdir: ../../images
:codedir: ../../../src
endif::[]

=== Array vs. Linked List & Queue vs. Stack

In this part of the book, we explored the most used linear data structures such as Arrays, Linked Lists, Stacks, and Queues. We implemented them and discussed the runtime of their operations.

.Use Arrays when…
* You need to access data in random order fast (using an index).
* Your data is multi-dimensional (e.g., matrix, tensor).

.Use Linked Lists when:
* You will access your data sequentially.
* You want to save memory and only allocate memory as you need it.
* You want constant time to remove/add from extremes of the list.

.Use a Queue when:
* You need to access your data on a first-come, first-served basis (FIFO).
* You need to implement a <<part03-graph-data-structures#bfs-tree, Breadth-First Search>>

.Use a Stack when:
* You need to access your data as last-in, first-out (LIFO).
* You need to implement a <<part03-graph-data-structures#dfs-tree, Depth-First Search>>
(((Tables, Linear DS, Array/Lists/Stack/Queue complexities)))

[[linear-data-structures-table]]
// tag::table[]
.Time/Space Complexity of Linear Data Structures (Array, LinkedList, Stack & Queues)
|===
.2+.^s| Data Structure 2+^s| Searching By 3+^s| Inserting at the 3+^s| Deleting from .2+.^s| Space
^|_Index/Key_ ^|_Value_ ^|_beginning_ ^|_middle_ ^|_end_ ^|_beginning_ ^|_middle_ ^|_end_
| <<array-chap>> ^|O(1) ^|O(n) ^|O(n) ^|O(n) ^|O(1) ^|O(n) ^|O(n) ^|O(1) ^|O(n)
| <<part02-linear-data-structures#singly-linked-list>> ^|O(n) ^|O(n) ^|O(1) ^|O(n) ^|*O(n)* ^|O(1) ^|O(n) ^|*O(n)* ^|O(n)
| <<part02-linear-data-structures#doubly-linked-list>> ^|O(n) ^|O(n) ^|O(1) ^|O(n) ^|*O(1)* ^|O(1) ^|O(n) ^|*O(1)* ^|O(n)
| <<part02-linear-data-structures#stack>> ^|- ^|- ^|- ^|- ^|O(1) ^|- ^|- ^|O(1) ^|O(n)
| Queue (w/array) ^|- ^|- ^|- ^|- ^|O(1) ^|*O(n)* ^|- ^|- ^|O(n)
| <<part02-linear-data-structures#queue>> (w/list) ^|- ^|- ^|- ^|- ^|O(1) ^|*O(1)* ^|- ^|- ^|O(n)
|===
// end::table[]