Linked list implementation and operations in Ruby

In Ruby, a linked list is a data structure that consists of a sequence of nodes. Each node in the list contains a data element and a reference (or pointer) to the next node in the sequence. The first node is called the head of the list, and the last node is called the tail

The LinkedList class is a doubly linked list, which means that each node has a reference to both the next and the previous node in the sequence. This allows for efficient traversal in both directions.

Ruby has a built-in LinkedList class in the enumerator library that can be used to create and manipulate linked lists. Here’s an example of how to create a linked list using the built-in LinkedList class:

require 'enumerator'

list = LinkedList.new
list << 1
list << 2
list << 3

This creates a linked list with three nodes containing the values 1, 2, and 3, respectively. We can add nodes to the list using the << operator.

Here are some of the basic operations we can perform on a linked list using the LinkedList class:

• Insertion at beginning: list.push(0)
• Deletion at beginning: list.shift
• Traversal: list.each {|node| puts node.value}
• Searching for a node: list.find {|node| node.value == 2}
• Insertion at a specific position: list.insert(2, 2.5)
• Deletion at a specific position: list.delete_at(2)
• Reversing a linked list: list.reverse
• Finding the middle node: we can implement our own method as shown in the previous answer.

We will see some of the operations after implementing linked dlists in Ruby.

Here’s an example of a Node class that we can use to create our linked list:

class Node
  attr_accessor :data, :next

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

With this Node class, we can create a linked list by chaining together nodes. For example, here’s how we can create a linked list with three nodes:

node1 = Node.new(1)
node2 = Node.new(2)
node3 = Node.new(3)

node1.next = node2
node2.next = node3

head = node1 # The head of the linked list is the first node

Now that we have our Node class and our linked list, let’s go through each of the operations you’ve asked for.

Creation

As shown above, a linked list is created by creating node objects and linking them together by setting the next pointer of each node to the next node in the sequence. The head of the list is set to the first node in the sequence.

Insertion at beginning

To insert a new node at the beginning of the list, we need to create a new node object with the data we want to insert, set its next pointer to the current head of the list, and then set the head of the list to the new node. Here’s the code:

def insert_at_beginning(head, data)
  new_node = Node.new(data)
  new_node.next = head
  head = new_node
  return head
end

Deletion at beginning

To delete the first node in the list, we simply set the head of the list to the second node in the sequence. The first node is then no longer referenced and will eventually be garbage collected. Here’s the code:

def delete_at_beginning(head)
  head = head.next
  return head
end

Traversal

To traverse the linked list, we can start at the head of the list and follow the next pointer of each node until we reach the end of the list (i.e., the next pointer of the last node is nil). Here’s the code:

def traverse(head)
  current_node = head
  while current_node != nil
    puts current_node.data
    current_node = current_node.next
  end
end

Searching for a node

To search for a node with a specific value in the list, we can start at the head of the list and follow the next pointer of each node until we find a node with the value we’re looking for or we reach the end of the list. Here’s the code:

def search(head, value)
  current_node = head
  while current_node != nil
    if current_node.data == value
      return current_node
    end
    current_node = current_node.next
  end
  return nil # Node not found
end

Insertion at a specific position

To insert a new node at a specific position in the list, we need to find the node that currently occupies that position, create a new node object with the data we want to insert, set its next pointer to the node that was previously at that position, and then set the next pointer

of the previous code:

of the previous node to point to the new node. Here’s the code:

def insert_at_position(head, data, position)
  if position == 0
    return insert_at_beginning(head, data)
  end

  current_node = head
  (position - 1).times do
    if current_node == nil
      return head # position out of range
    end
    current_node = current_node.next
  end

  if current_node == nil
    return head # position out of range
  end

  new_node = Node.new(data)
  new_node.next = current_node.next
  current_node.next = new_node

  return head
end

Deletion at a specific position

To delete a node at a specific position in the list, we need to find the node that currently occupies that position, set the next pointer of the previous node to the node that follows the node we want to delete, and then delete the node. Here’s the code:

def delete_at_position(head, position)
  if position == 0
    return delete_at_beginning(head)
  end

  current_node = head
  (position - 1).times do
    if current_node == nil || current_node.next == nil
      return head # position out of range
    end
    current_node = current_node.next
  end

  if current_node == nil || current_node.next == nil
    return head # position out of range
  end

  current_node.next = current_node.next.next

  return head
end

Reversing a linked list

To reverse the linked list, we need to iterate through the list and flip the next pointers of each node so that they point in the opposite direction. We also need to keep track of the previous node so that we can update its next pointer. Finally, we set the head of the list to the last node we visited (i.e., the previous node when we reached the end of the list). Here’s the code:

def reverse(head)
  current_node = head
  previous_node = nil

  while current_node != nil
    next_node = current_node.next
    current_node.next = previous_node
    previous_node = current_node
    current_node = next_node
  end

  head = previous_node

  return head
end

Splitting a linked list

To split the linked list in two, we need to find the middle node and set its next pointer to nil. The first half of the list is the original list up to the middle node, and the second half of the list is the nodes after the middle node. Here’s the code:

def split(head)
  if head == nil || head.next == nil
    return [head, nil]
  end

  slow_pointer = head
  fast_pointer = head.next

  while fast_pointer != nil
    fast_pointer = fast_pointer.next
    if fast_pointer != nil
      slow_pointer = slow_pointer.next
      fast_pointer = fast_pointer.next
    end
  end

  second_half_head = slow_pointer.next
  slow_pointer.next = nil

  return [head, second_half_head]
end

Joining two linked lists

To join two linked lists, we need to find the last node of the first list and set its next pointer to the head of the second list. Here’s the code:

require 'enumerator'

# create first list
list1 = LinkedList.new
list1 << 1
list1 << 2
list1 << 3

# create second list
list2 = LinkedList.new
list2 << 4
list2 << 5
list2 << 6

# join the two lists
if list1.tail
  list1.tail.next = list2.head
else
  list1.head = list2.head
end

# print the joined list
list1.each {|node| puts node.value}

Finding the middle node

To find the middle node of the linked list, we can use the slow-pointer/fast-pointer approach that we used in the split method. We start with two pointers: a slow pointer that moves one node at a time, and a fast pointer that moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. Here’s the code:

def find_middle_node(head)
  if head == nil
    return nil
  end

  slow_pointer = head
  fast_pointer = head

  while fast_pointer != nil
    fast_pointer = fast_pointer.next
    if fast_pointer != nil
      slow_pointer = slow_pointer.next
      fast_pointer = fast_pointer.next
    end
  end

  return slow_pointer
end

Time and Space complexity

Time and space complexity of each operation on a linked list:

• Creation: O(1) time complexity, O(n) space complexity (for n nodes in the list)
• Insertion at beginning: O(1) time complexity, O(1) space complexity
• Deletion at beginning: O(1) time complexity, O(1) space complexity
• Traversal: O(n) time complexity, O(1) space complexity
• Searching for a node: O(n) time complexity, O(1) space complexity
• Insertion at a specific position: O(n) time complexity in the worst case (when inserting at the end of the list), O(1) time complexity in best case (when inserting at the beginning), O(1) space complexity
• Deletion at a specific position: O(n) time complexity in the worst case (when deleting the last node), O(1) time complexity in best case (when deleting the first node), O(1) space complexity
• Reversing a linked list: O(n) time complexity, O(1) space complexity
• Splitting a linked list: O(n) time complexity, O(1) space complexity
• Joining two linked lists: O(n) time complexity (where n is the length of the first list), O(1) space complexity
• Finding the middle node: O(n) time complexity, O(1) space complexity

These are just general time and space complexity estimates, and actual performance may vary depending on factors such as the size of the input data and the implementation details. Additionally, these estimates assume that the linked list is implemented using a basic node structure as shown in the previous answers; using more complex node structures or adding additional features to the linked list may affect the time and space complexity of the operations.