Linked Lists! The linear but dynamic data structure! - 401-advanced-javascript-aimurphy/seattle-javascript-401n13 GitHub Wiki

What it is:

A data structure! It is sequential, dynamic (meaning it can adapt and change and will not lock up blocks of memory like an array) and therefore a bit scattered; great for adding and removing large segments.

What it is not:

It is not an array; static, fixed and contiguous; terrible for fine-point searches.

2 Flavors and their Anatomy

(new, but not necessarily better, graphics to come):

---

Linked lists come in two flavors: SINGLY and DOUBLY. Singly means they are singly linked--the relationship is unidirectional and each node only knows where to go next and nothing about the previous node. Doubly linked lists contain nodes that have information on both directions: who its neighbors are on either side of its position in the list. Each node in the list is made up of 2 parts: 1. some data, and 2. a reference to its neighbor (the next in sequence if it is singly linked, and both if doubly). If it it the HEAD it will only know the next, and if it is the tail, the next will actually be pointing to a null value to signify the end of the list. But there are always exceptions! See the circular linked list? More on that later.

---

Growing a Linked List and a bit on Big O Notation

In a nutshell, Big O refers to how quickly things will run (...relative to the input, as the input grows).

More on that at Interview Cake, but for now, grow that list!

---

TO BE CONTINUED Growing the easy way... From the beginning! O(1)

Growing the hard way... From anywhere else. O(n)

---

Resources: Code Fellows Medium: What's A Linked List Anyway? Pts 1&2