Linked Lists

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