Question Click to View Answer A linked list maintains a relative positioning of items. Each node in the list knows the next node in the list. The first node is called the "head" of the linked list. Create a `Node` class and a `LinkedList` class so the following code will work. ```n3 = Node.new(data: :happy) n2 = Node.new(data: 99, next_node: n3) n1 = Node.new(data: "cat", next_node: n2) list = LinkedList.new(head: n1) ``` This code will construct the `"cat" => 99 => :happy` list. The `Node` class stores data and a reference to the next node in the list. The `LinkedList` class only needs to know the head node of the linked list. ```class Node attr_accessor :data, :next_node def initialize(data:, next_node: nil) @data = data @next_node = next_node end end class LinkedList attr_reader :head def initialize(head:) @head = head end end ``` Add a `size` method to the LinkedList class that traverses the linked list and returns the size of the list. The `size` method iterates through every node in the linked list and keeps track of the count. ```class LinkedList attr_reader :head def initialize(head:) @head = head end def size current = head count = 0 until current.nil? count += 1 current = current.next_node end count end end n3 = Node.new(data: :happy) n2 = Node.new(data: 99, next_node: n3) n1 = Node.new(data: "cat", next_node: n2) list = LinkedList.new(head: n1) p list.size # => 3 ``` Add a `pretty_print` method that returns an array of all the data elements in a linked list. The `pretty_print` method iterates through every element in the linked list and adds the data elements to an array. This method will make it easier to verity that other linked list methods are working as intended. ```def pretty_print current = head result = [] until current.nil? result.push(current.data) current = current.next_node end result end ``` Add an `include` method to the `LinkedList` class to see if an element is in the linked list. The `include?` method iterates over every element in the linked list and returns true if the element is included. ```def include?(data) current = head until current.nil? return true if current.data == data current = current.next_node end false end # using the same list from earlier problems list.include?(:happy) # => true list.include?(99) # => true list.include?("cat") # => true list.include?("fat") # => false ``` Add a `remove` method to delete a node from a linked list. Removing an item from a linked list is a bit trickier because the `next_node` attribute of the previous node needs to be updated, so it's not left pointing to a node that has been deleted. When the first node of a linked list is removed, the `@head` instance variable needs to be updated. ```def remove(data) current = head previous = nil until current.nil? if current.data == data if previous.nil? @head = current.next_node return end previous.next_node = current.next_node return end previous = current current = current.next_node end false end ``` Add an `add` method that will add a node to the beginning of a linked list. The `add` method sets the `next_node` of the current node to be the current head and then resets the head to the newly added node. ```def add(node) node.next_node = head @head = node end ``` Add a `reverse` method that reverses the linked list. This video provides an awesome tutorial on how to reverse a linked list. At each step of the iteration, we need to keep track of the current node, the previous node, and the next node. During each step of the iteration, the `next_node` is reset to the previous node. ```def reverse current = head previous = nil next_node = nil until current.nil? next_node = current.next_node current.next_node = previous previous = current current = next_node end @head = previous end ```