Linked List Lesson Notes

linked-list.md

Linked Lists

Objectives

• Describe how objects are stored in memory
• Diagram how objects that refer to other objects are stored in memory
• Create a Node class that can hold referential information (nested data)
• Implement a SinglyLinkedList class that stores a list of Nodes
  • push: adds a new Node to the end
  • pop: removes a Node from the end
• Explain the Big O complexity of common linked-list methods

Guiding Questions

• How are objects (reference types) stored in memory?

  Your answer...

• Draw the call stack and the heap for the following code:

  const tree = { heigth: 15, color: 'green' }
  const flower = { type: 'daisy', color: 'yellow' }

• Draw the call stack and the heap for the following code:

  const salsa = { ingredient: 'tomatoes' }
  
  const dip = {
    ingredient: 'black beans',
    nextLayer: salsa 
  }

  When you're finished, add your next favorite layer to the dip! How does your data structure mantain the order of the ingredients?

Challenge

Implement a Node class

• val property can hold any standard data type
• next property stores a reference to another Node or null

Implement a SinglyLinkedList class that stores a list of Nodes

• Include head and tail properties
• Include push and pop methods

Big O

• What is the worst-case Big O complexity of push?
• What is the worst-case Big O complexity of pop?