## Table of Contents

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.