linked-list.md

Linked List Instructor Notes

Objectives

• Explain what Linked Lists are.
• Describe why linked lists are important.
• Draw the following actions on a singly linked and double linked list.
  • push
  • pop
  • shift
  • unshift
  • insert

Explain what Linked Lists are.

• Turn to your neighbor and define a SinglyLinkedList Node class
• Turn to your neighbor and define a SinglyLinkedList class
• Turn to your neighbor and define a DoublyLinkedList Node class
• Turn to your neighbor and define a DoublyLinkedList class
• On your table, draw a SinglyLinkedList with 3 items
• On your table, draw a DoublyLinkedList with 3 items
• On your table, add a Node at the beginning of SinglyLinkedList and DoublyLinkedList
• On your table, write a __getNodeAt(index) method that returns a reference to the node at the given index
• On your table, add a Node in the middle of SinglyLinkedList and DoublyLinkedList
• On your table, add a Node at the end of SinglyLinkedList and DoublyLinkedList

Describe why linked lists are important.

• Turn to your neighbor and discuss what the Big O of adding an
  • item to the beginning of an array is.
  • item to the end of an array is.
  • item to the middle of an array is.
  • item to the beginning of a LinkedList is.
  • item to the end of a LinkedList is.
  • item to the middle of a LinkedList is.
• Turn to your neighbor and discuss what the Big O of
  • retrieving a value of an array is.
  • retrieving a value of a LinkedList is.
• Turn to your neighbor and discuss why linked lists are important

Draw the following actions on a singly linked and double linked list.

Turn to your neighbor diagram each of the following actions:

• push
• pop
• shift
• unshift
• insert