Introduction to Linked Lists in Ruby

As our graduation from Flatiron looms closer, my cohort and I have been trying to focus on algorithm and data structure knowledge in preparation for future interviews. Which is why I thought it'd be a great idea to go over a notably asked interviewing concept: linked lists!

Overview

Linked lists are just that: lists of data that are literally linked to one another. They are linear data structures, meaning that they are made up of separate elements arranged in a sequential order.

It may be helpful to discuss first what the difference between linear and non-linear data structures are.

Linear Data Structures
Linear data structures are those in which data elements attached one after the other in a line, hence linear and sequentially. This makes each element linked to its previous and next element in order. In order to find information about an element inside of a linear data structure, you must go through each element one by one, starting from the first element. You can access all of the data inside of a linear data structure with one iteration.

Non-linear Data Structures
Non-linear data structures, on the other hand, are non-sequential, meaning the information they contain does not need to be ordered one after another. In addition, one element could be connected to two or even more elements, making it unlikely for you to be able to traverse through all of the data in one iteration. Typically, implementing linear data structures tends to be easier than implementing non-linear ones.

Types of Linked Lists

With this new found knowledge, let's get back to linked lists. Below you can see an example of a singly linked list.

Singly Linked List
This is the most basic example and gives us all of the main components of a linked list. Each element, or node, in a linked list contains two pieces of information: the data or values we want to store and knowledge about the placement of the next item in the list. The nodes are linked together through this knowledge of where in memory the next node exists. When iterating through the linked list, you must first start at the head node. By having knowledge of the next node of the head, we are able to see the complete list of nodes. And the last node in the list does not contain information about the next node, as it doesn't exist, thus only holds a knowledge value of nil or 0.

Doubly Linked List
There are also doubly linked lists which has three parts that make up a node, two of which are knowledge points for the previous node and the next node. This makes it easier to access data or nodes within the list without having to start over at the beginning or head node again. They do, however, take up more space which brings us to our next idea.

Memory Storage & Big O

One key factor of linked lists that separates them from their more popular and easier to get along with sister arrays is their use of space and time, or Big O notation.

As depicted in the diagram, each square represents a byte of memory and arrays have a predetermined length and thus predetermined amount of memory that they will occupy. Even if all of the spaces aren't currently being filled with data, the array will still hold these bytes of memory for itself. This can make them bulky and slow, or even worse if it is decided that the array needs to be longer. It must be copied and found a new block or place to be stored in the memory.

Linked lists though, can be stored as just their nodes, separated throughout memory as the machine pleases. In the diagram you can see that linked lists only occupy the space necessary for their nodes to exist, and then they are connected through their reference to the next. This allows for much more flexibility in memory for other items to be stored and doesn't waste any unused space.

The time it takes to access all of the elements in a linked list is directly proportional to the size of the list. If the size of the list is n, then the time complexity would be 0(n). To contrast this with arrays, typically arrays only take O(1) time as their sizes are fixed and thusly stored continuously in a block. With arrays you are able to reach an item in the middle of the structure by indexing, but with linked lists that is not possible.

Linked lists really shine in terms of insertion and deletions. Given a smaller list or an optimal search, both can take constant or 0(1) time. But as it depends mostly on the size of the list, they can also be 0(n) as it is necessary to traverse the entire list to find where an insertion or deletion needs to be made.

Implementation

With all of this in mind, we can walk through an example of implementing a linked list in Ruby.

A linked list is typically created as two classes: a node class and a linked list class.

class Node
  attr_accessor :value, :next_node

  def initialize(value, next_node)
    @value = value
    @next_node = next_node
  end
end

The first node class is initialized with a value and a next_node which is the pointer for the next value. Upon creating a new node instance, next will be initialized as nil.

class LinkedList
  def initialize(value)
    @head = Node.new(value, nil)
  end

  def addition(value)
    current_node = @head
    while current_node.next_node != nil
      current_node = current_node.next_node
    end
      current_node.next_node = Node.new(value, nil)
  end

  def find(value)
    current_node = @head
    puts current_node.value
    return false if !current_node.next_node
    return current_node if current_node.value == value
    while (current_node = current_node.next_node)
      return current_node if current_node.value == value
    end
  end

  def deletion(value)
    current_node = @head
    if current_node.value == value
      @head = current_node.next_node
    else
      while (current_node.next_node != nil) && (current_node.next_node.value != value)
        if (current_node.next_node == nil) || (current_node.next_node.value == value)
          current_node.next_node = current_node.next_node.next_node
        else
          current_node = current_node.next_node
        end
      end
      current_node.next_node = current_node.next_node.next_node
    end
  end

  def print_list
    current_node = @head
    puts current_node.value
    while (current_node = current_node.next_node)
      puts current_node.value
    end
  end

end

I've included three basic methods for a linked list (addition, deletion, and find) as well as a method for printing the values to the console.

Addition
First, the current node is set as the head, or first, node in the list. It traverses through the linked list until there aren't any nodes left. When it finds the last node, it stops before and appends a new one as the next, and last, node.

Find
Again, the current node is set to the head node and the first two returns are edge cases. Assuming the list is not empty and the head node is not the matching value, the list will be iterated through one by one until the value is found.

Deletion
This is the trickiest method as values aren't necessarily deleted in linked lists, they are simply unlinked and passed over in the new list. The first if statement is an edge case in the event that the value to be deleted is contained in the head node. If that is the case then we will set our new current_node to be the next value, thus skipping over the "old" head node. If this is not the case, then we will traverse through the list until the end or until the value matches with a node. In which case we will set the current_node to the next next node, passing over the node that is to be "deleted".

We will always need to be looking two nodes ahead in this case, as when we find the one to be deleted, we will simply skip over it and assign the current_node to the next next one.

Print_List
The last method, print_list, is simply to have the entire linked list printed to the console for simple viewing.

list = LinkedList.new(2)
list.addition(5)
list.addition(7)
list.addition(10)
list.deletion(5)
list.print_list

# 2, 7, 10

Takeaways

Linked lists are useful for adding and deleting items and they can be very space efficient. They are often compared with arrays and with good reason. They function very similarly but have some fairly distinct advantages and disadvantages which are highlighted below:

Advantages:

• more time efficient than arrays when adding and removing items
• no unused memory
• easier to implement than non-linear data structures

Disadvantages:

• slower than arrays when finding the index of an item
• need to be aware of memory allocation for storing the reference to the next node
• more difficult to implement than an array

Hope this could be helpful if you've decided to implement a linked list in your next application or you happen to get asked about this interesting data structure in your next interview. Happy coding!