Read: Class 05 Linked Lists - 401-advanced-javascript-muna/amman-javascript-401d1 GitHub Wiki

Linked Lists

Data structures:

which are the different ways that we can organize our data; variables, arrays, hashes, and objects are all types of data structures.

  1. Linear data structures:there is a sequence and an order to how they are constructed and traversed.

  2. Non-linear data structures: items don’t have to be arranged in order, which means that we could traverse the data structure non-sequentially.

linear vs non linear

linked lists is that they are linear data structures

Linked lists don’t need to take up a single block of memory; instead, the memory that they use can be scattered throughout.

linklist memory

PS: a linked list to have its memory scattered everywhere.

Parts of a linked list

  • series of nodes:the elements of the list Each node It has just two parts:
    1. data, or the information that the node contains 1. a reference to the next node(pointer references to — the next node in the list)

  • head: the first node

  • next node.

  • The end of the list isn’t a node, but rather a node that points to null, or an empty value.

  • Singly linked lists:we start at the head node, and traverse from the root until the last node, which will end at an empty null value.

  • doubly linked list :have two references : next node and previous node

  • circular linked list :we can turn both a singly linked list and a doubly linked list into a circular linked list!

Big O Notation

is a way of evaluating the performance of an algorithm.

Big O Notation takes into account: the speed and efficiency with which something functions when its input grows to be any (crazy big!) size.

  1. O(1) function takes constant time, which is to say that it doesn’t matter how many elements we have, or how huge our input is: it’ll always take the same amount of time and memory to run our algorithm.
  2. O(n) function is linear, which means that as our input grows (from ten numbers, to ten thousand, to ten million), the space and time that we need to run that algorithm grows linearly.
  3. O(n²) function, which clearly takes exponentially more time and memory the more elements that you have.