## Table of Contents

- Initialize a new empty linked list.
- Add a new node to the end of the linked list.
- Iterate over each node in the linked list and yields the value to a block.
- Return true if the linked list is empty.
- Return the first value in the linked list.
- Return the last value in the linked list.
- Return the number of nodes in the linked list.
- Remove the first node in the linked list that has the given value.
- Reverse the order of the nodes in the linked list.
- Return the value at the given index in the linked list.
- Doubly linked list in Ruby

Ruby has a built-in linked list class called `LinkedList`

, which is part of the `enumerator`

package. The `LinkedList`

class is a linear data structure that consists of a sequence of nodes, where each node contains a data element and a reference to the next node in the list.

Here is an example code to create and use a linked list in Ruby:

```
require 'enumerator'
class Node
attr_accessor :value, :next_node
def initialize(value, next_node = nil)
@value = value
@next_node = next_node
end
end
class LinkedList
include Enumerable
def initialize
@head = nil
end
def add(value)
if @head.nil?
@head = Node.new(value)
else
current = @head
while current.next_node != nil
current = current.next_node
end
current.next_node = Node.new(value)
end
end
def each(&block)
current = @head
while current != nil
yield current.value
current = current.next_node
end
end
end
# create a new linked list
list = LinkedList.new
# add elements to the list
list.add(1)
list.add(2)
list.add(3)
# print the elements in the list
list.each do |value|
puts value
end
```

In this example, we define a `Node`

class that represents a node in the linked list. The `LinkedList`

class is then defined, which includes the `Enumerable`

module to enable iteration over the elements in the list.

The `LinkedList`

class has an `add`

method that adds a new element to the list. The `each`

method is defined to iterate over the elements in the list, yielding each value to a block.

Finally, we create a new `LinkedList`

instance, add some elements to it, and then print out the elements using the `each`

method.

When we run the above code, it will output:

```
1
2
3
```

This shows that the linked list is functioning correctly, and we are able to iterate over its elements using the `each`

method.

The `LinkedList`

class can be further extended to include additional methods for manipulating the list, such as `remove`

, `insert`

, and `reverse`

. For example, here is an implementation of the `remove`

method:

```
def remove(value)
if @head == nil
return
end
if @head.value == value
@head = @head.next_node
return
end
current = @head
while current.next_node != nil
if current.next_node.value == value
current.next_node = current.next_node.next_node
return
end
current = current.next_node
end
end
```

This method removes the first node in the list that has the given value. If the list is empty or the value is not found in the list, the method does nothing.

### The LinkedList class in Ruby has the following methods:

`initialize`

: Initializes a new empty linked list.`add`

: Adds a new node to the end of the linked list.`each`

: Iterates over each node in the linked list and yields the value to a block.`empty?`

: Returns true if the linked list is empty.`first`

: Returns the first value in the linked list.`last`

: Returns the last value in the linked list.`length`

: Returns the number of nodes in the linked list.`remove`

: Removes the first node in the linked list that has the given value.`reverse`

: Reverses the order of the nodes in the linked list.`[](index)`

: Returns the value at the given index in the linked list.

## Initialize a new empty linked list.

Example code:

```
def initialize
@head = nil
end
```

Explanation: This method creates a new linked list with an empty head node.

Time complexity: O(1)

Space complexity: O(1)

## Add a new node to the end of the linked list.

Example code:

```
def add(value)
if @head.nil?
@head = Node.new(value)
else
current = @head
while current.next_node != nil
current = current.next_node
end
current.next_node = Node.new(value)
end
end
```

Explanation: This method adds a new node with the given value to the end of the linked list. If the list is empty, the new node becomes the head node. Otherwise, the method iterates through the list until it reaches the last node, and then adds the new node as its next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Iterate over each node in the linked list and yields the value to a block.

Example code:

```
def each(&block)
current = @head
while current != nil
yield current.value
current = current.next_node
end
end
```

Explanation: This method allows the linked list to be iterated over using the `each`

method. It yields each value in the list to the given block.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Return true if the linked list is empty.

Example code:

```
def empty?
@head.nil?
end
```

Explanation: This method checks if the linked list is empty by checking if the head node is nil.

Time complexity: O(1)

Space complexity: O(1)

## Return the first value in the linked list.

Example code:

```
def first
@head.value
end
```

Explanation: This method returns the value of the head node in the linked list.

Time complexity: O(1)

Space complexity: O(1)

## Return the last value in the linked list.

Example code:

```
def last
current = @head
while current.next_node != nil
current = current.next_node
end
current.value
end
```

Explanation: This method returns the value of the last node in the linked list. It iterates through the list until it reaches the last node, and then returns its value.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Return the number of nodes in the linked list.

Example code:

```
def length
count = 0
current = @head
while current != nil
count += 1
current = current.next_node
end
count
end
```

Explanation: This method returns the number of nodes in the linked list by iterating through the list and counting the nodes.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Remove the first node in the linked list that has the given value.

Example code:

```
def remove(value)
if @head == nil
return
end
if @head.value == value
@head = @head.next_node
return
end
current = @head
while current.next_node != nil
if current.next_node.value == value
current.next_node = current.next_node.next_node
return
end
current = current.next_node
end
end
```

Explanation: This method removes the first node in the linked list that has the given value. If the list is empty, the method does nothing. If the head node has the given value, it is removed and the next node becomes the new head. Otherwise, the method iterates through the list until it finds the node with the given value, removes it, and updates the links to connect the previous node to the next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Reverse the order of the nodes in the linked list.

Example code:

```
def reverse
previous = nil
current = @head
while current != nil
next_node = current.next_node
current.next_node = previous
previous = current
current = next_node
end
@head = previous
end
```

Explanation: This method reverses the order of the nodes in the linked list. It does this by iteratively changing the links between nodes so that each node points to its previous node instead of its next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Return the value at the given index in the linked list.

Example code:

```
def [](index)
count = 0
current = @head
while current != nil
if count == index
return current.value
end
count += 1
current = current.next_node
end
nil
end
```

Explanation: This method returns the value of the node at the given index in the linked list. It does this by iterating through the list until it reaches the node at the given index, and then returns its value. If the index is out of bounds, the method returns nil.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

## Doubly linked list in Ruby

we can modify the `LinkedList`

class to create a doubly linked list in Ruby. A doubly linked list is a type of linked list where each node has a reference to both its previous node and its next node.

Here is an example implementation of a doubly linked list using Ruby:

```
class Node
attr_accessor :value, :next_node, :prev_node
def initialize(value, next_node = nil, prev_node = nil)
@value = value
@next_node = next_node
@prev_node = prev_node
end
end
class DoublyLinkedList
include Enumerable
def initialize
@head = nil
@tail = nil
end
def add(value)
if @head.nil?
@head = Node.new(value)
@tail = @head
else
new_node = Node.new(value, nil, @tail)
@tail.next_node = new_node
@tail = new_node
end
end
def each(&block)
current = @head
while current != nil
yield current.value
current = current.next_node
end
end
def empty?
@head.nil?
end
def first
@head.value
end
def last
@tail.value
end
def length
count = 0
current = @head
while current != nil
count += 1
current = current.next_node
end
count
end
def remove(value)
if @head == nil
return
end
if @head.value == value
@head = @head.next_node
@head.prev_node = nil if @head
return
end
current = @head
while current.next_node != nil
if current.next_node.value == value
current.next_node = current.next_node.next_node
current.next_node.prev_node = current if current.next_node
return
end
current = current.next_node
end
end
def reverse
current = @head
while current != nil
temp_node = current.next_node
current.next_node = current.prev_node
current.prev_node = temp_node
current = temp_node
end
temp_node = @head
@head = @tail
@tail = temp_node
end
def [](index)
count = 0
current = @head
while current != nil
if count == index
return current.value
end
count += 1
current = current.next_node
end
nil
end
end
```

The `DoublyLinkedList`

class is similar to the `LinkedList`

class, except that each node has an additional reference to its previous node. The `add`

and `remove`

methods have been modified to handle the previous node reference, and the `reverse`

method has been updated to swap the previous and next node references.

Here is how you can use the `DoublyLinkedList`

class:

```
# create a new doubly linked list
list = DoublyLinkedList.new
# add elements to the list
list.add(1)
list.add(2)
list.add(3)
# print the elements in the list
list.each do |value|
puts value
end
# check if the list is empty
puts "Is the list empty? #{list.empty?}"
# get the first and last elements in the list
puts "First element: #{list.first}"
```

puts "Last element: #{list.last}"
# get the length of the list
puts "Length of list: #{list.length}"
# remove an element from the list
list.remove(2)
# print the elements in the list again
list.each do |value|
puts value
end
# reverse the order of the elements in the list
list.reverse
# print the elements in the list again
list.each do |value|
puts value
end