Introduction to Linked Lists in Ruby

Introduction to Linked Lists

Hello there! Today, we will explore Linked Lists, a core data structure crucial for organized data management and establishing relationships between data. We will mark some essential milestones: an introduction to Linked Lists, their real-world applications, their implementation in Ruby, and the different operations you can perform on them. By the end of this lesson, you will be well-equipped to implement and operate Linked Lists using Ruby . Let's get started!

Understanding the Concept

A Linked List is a linear data structure similar to arrays. But, unlike arrays, they are not stored in contiguous memory locations. Each element in a Linked List is part of a node . A node comprises data and a reference (or link) to the next node in the sequence. This structure facilitates efficient insertions and deletions. The head is also an essential concept in Linked Lists. It is the first node in the list and serves as a reference to the entire list. The head is nil if the Linked List is empty. Singly linked lists come up quite often in coding interviews. Interviewers from tech giants, start-ups, and just about every company testing your coding abilities will pose challenges based on this concept. Here's another interesting point: While singly linked lists might not be extensively used in real-world applications, they form the foundational knowledge for understanding doubly linked lists, which are indeed quite common. A singly linked list contains nodes with a single link pointing to the next node, whereas a doubly linked list has nodes with links to both the next and the previous nodes.

Implementing Linked Lists - Creating a Node

To begin implementing Linked Lists, we first need to understand the structure of a node, the building block of a Linked List. In Ruby, we'll create a class to serve as a blueprint for a node . A Node class mainly consists of data (the data you want to store) and next_node (the reference to the next node). In our case, we'll create a Node class to store integer data, with an initialize method to set up the node. Ruby class Node attr_accessor :data, :next_node def initialize(data) @data = data @next_node = nil end end Fantastic! You now know how to set up a node in a Linked List.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Ruby

class Node
  attr_accessor :data, :next_node

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def append(data)
    node = Node.new(data)

    if @head.nil?
      @head = node
    else
      last = @head
      last = last.next_node while last.next_node
      last.next_node = node
    end
  end
end

class Node
  attr_accessor :data, :next_node

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def append(data)
    node = Node.new(data)

    if @head.nil?
      @head = node
    else
      last = @head
      last = last.next_node while last.next_node
      last.next_node = node
    end
  end
end

Ruby

def add_first(data)
  node = Node.new(data)

  if @head
    node.next_node = @head
  end
  @head = node
end

def add_first(data)
  node = Node.new(data)

  if @head
    node.next_node = @head
  end
  @head = node
end

Ruby

def delete(data)
  return if @head.nil?

  if @head.data == data
    @head = @head.next_node
    return
  end

  current = @head
  while current.next_node
    if current.next_node.data == data
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

def delete(data)
  return if @head.nil?

  if @head.data == data
    @head = @head.next_node
    return
  end

  current = @head
  while current.next_node
    if current.next_node.data == data
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

Ruby

class Node
  attr_accessor :data, :next_node

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def append(data)
    node = Node.new(data)

    if @head.nil?
      @head = node
    else
      last = @head
      last = last.next_node while last.next_node
      last.next_node = node
    end
  end
end

Ruby

def add_first(data)
  node = Node.new(data)

  if @head
    node.next_node = @head
  end
  @head = node
end

Ruby

def delete(data)
  return if @head.nil?

  if @head.data == data
    @head = @head.next_node
    return
  end

  current = @head
  while current.next_node
    if current.next_node.data == data
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

Introduction to Linked Lists

Understanding the Concept

Implementing Linked Lists - Creating a Node

Join the 1M+ learners on CodeSignal

Implementing Linked Lists - Append Method

Implementing Linked Lists - Add First Method

Implementing Linked Lists - Delete Method

Complexity Analysis

Summary and What's Next