## Table of Contents

1. Understanding Linked Lists

2. Implementing a Linked List in Ruby

2.1. print_list method

2.2. append Method

2.3. pop Method

2.4. prepend Method

2.5. shift Method

2.6. get method

2.7. set_value method

2.8. insert method

2.9. reverse Method

## Understanding Linked Lists

A linked list is a collection of nodes where each node contains a value and a reference to the next node in the sequence. The first node is called the head, and the last node is called the tail. The tail node's reference points to `nil`

, indicating the end of the list.

In this blog post, we will explore a simple implementation of a linked list in Ruby and discuss each method along with its time complexity.

## Implementing a Linked List in Ruby

Let's start by examining the provided Ruby code that implements a linked list. The `LinkedList`

class represents the linked list, and each node is represented by the `Node`

class.

```
class LinkedList
attr_accessor :head, :tail, :length
def initialize(value)
new_node = Node.new(value)
@head = new_node
@tail = new_node
@length = 1
end
# Other methods...
end
class Node
attr_accessor :value, :next
def initialize(value)
@value = value
@next = nil
end
end
```

- The
`initialize`

method is the constructor of the`LinkedList`

class and`Node`

class. - It creates a new instance of the linked list with an initial value and a new instance of the node.
- When a new node is created, its value will be the provided value, and the next node will be
`nil`

. - When a new linked list is created, it creates a new node object with the given value.
- This node is set as both the head and tail of the linked list.
- The length attribute is initialized to 1 since there is only one node in the list at the beginning.

###
`print_list`

method

The print_list method iterates through the linked list and prints the value of each node.

```
def print_list
temp = head
while temp
puts temp.value
temp = temp.next
end
end
```

- Starting from the head node, the method iterates through the list by following the next reference of each node.
- It prints the value of each node and continues until it reaches the end of the list (when temp becomes
`nil`

). - The time complexity of the
`print_list`

method is O(n), where n is the length of the linked list. - It needs to visit each node once to print its value.

###
`append`

Method

The append method adds a new node with the given value at the end of the linked list.

```
def append(value)
new_node = Node.new(value)
if @head
@tail.next = new_node
@tail = new_node
else
@tail = new_node
@head = new_node
end
@length += 1
true
end
```

- First, a new node is created with the provided value.
- If the linked list is not empty (the
`@head`

node exists), the next reference of the current tail node is set to the new node, and the tail is updated to the new node. This way, the new node becomes the new tail. - If the linked list is empty, both the head and tail are set to the new node.
- At last, we increment length by one
- The time complexity of the
`append`

method is O(1) since it performs a constant number of operations regardless of the size of the linked list. It directly accesses and updates the tail node.

###
`pop`

Method

The pop method removes and returns the last node from the linked list.

```
def pop
return if @length.zero?
temp = @head
pre = @head
while temp.next
pre = temp
temp = temp.next
end
@tail = pre
@tail.next = nil
@length -= 1
return temp unless @length.zero?
@head = nil
@tail = nil
temp
end
```

- To remove the last node, the method iterates through the list until it reaches the second-to-last node.
- The
`pre`

variable keeps track of the previous node while the`temp`

variable moves forward. - After reaching the last node, it updates the tail to the second-to-last node, removes the reference to the last node, and decrements the length of the list.
- If the list becomes empty after removing the last node, both the head and tail are set to
`nil`

. - The time complexity of the
`pop`

method is O(n), where n is the length of the linked list. - It needs to traverse the list to reach the second-to-last node for removal.

###
`prepend`

Method

The prepend method adds a new node with the given value at the beginning of the linked list.

```
def prepend(value)
new_node = Node.new(value)
new_node.next = @head
@head = new_node
@tail = new_node if @length.zero?
@length += 1
true
end
```

- First, a new node is created with the provided value.
- The next reference of the new node is set to the current head node.
- Then, the head is updated to the new node.
- If the linked list was initially empty (length was zero), the tail is also set to the new node since it is the only node in the list.
- At last, we increment length by one
- The time complexity of the
`prepend`

method is O(1) since it performs a constant number of operations regardless of the size of the linked list. - It directly accesses and updates the head node.

###
`shift`

Method

The shift method removes and returns the first node from the linked list.

```
def shift
return if @length.zero?
temp = @head
@head = temp.next
temp.next = nil
@tail = nil if @length == 1
@length -= 1
temp
end
```

- The method removes the head node by updating the head to its next node.
- It also updates the next reference of the removed node to
`nil`

to detach it from the list. - If the list becomes empty after removal (length was initially one), the tail is set to
`nil`

. - At last, we decrement length by one.
- The time complexity of the
`shift`

method is O(1) since it performs a constant number of operations regardless of the size of the linked list. - It directly accesses and updates the head node.

###
`get`

method

The get method returns the node at the specified index in the linked list.

```
def get(index)
return if index >= @length || index.negative?
temp = @head
(0...index).each do |_i|
temp = temp.next
end
temp
end
```

- The method first checks if the provided index is valid (within the range of the list).
- If the index is not valid (greater than or equal to the length or negative), it returns
`nil`

. - Otherwise, it iterates through the list to reach the desired index and returns the corresponding node.
- The time complexity of the
`get`

method is O(n), where n is the length of the linked list. - It needs to traverse the list to reach the desired index.

###
`set_value`

method

The set_value method sets the value of the node at the specified index in the linked list.

```
def set_value(index, value)
temp = get(index)
if temp
temp.value = value
true
else
false
end
end
```

- The method first uses the
`get`

method to retrieve the node at the specified index. - If the node exists, it updates its value with the provided value and returns true.
- Otherwise, it returns false.
- The time complexity of the
`set_value`

method is O(n), where n is the length of the linked list. - It utilizes the
`get`

method, which has a time complexity of O(n), to retrieve the node at the specified index.

###
`insert`

method

The insert method inserts a new node with the given value at the specified index in the linked list.

```
def insert(index, value)
return if index >= @length || index.negative?
return prepend(value) if index.zero?
return append(value) if index == @length - 1
temp = get(index - 1)
new_node = Node.new(value)
new_node.next = temp.next
temp.next = new_node
@length += 1
true
end
```

- First, it checks if the provided index is valid. If not, it returns
`nil`

. - If the index is zero, it uses the
`prepend`

method to add the new node at the beginning. - If the index is equal to the length minus one, it uses the
`append`

method to add the new node at the end. - Otherwise, it retrieves the node at the previous index (index - 1) using the
`get`

method. - Then, it creates a new node with the provided value and inserts it into the list by updating the next references accordingly.
- At last, we increment length by one
- The time complexity of the
`insert`

method is O(n), where n is the length of the linked list. - It utilizes the
`get`

method, which has a time complexity of O(n), to retrieve the node at the specified index.

###
`remove`

method

The remove method removes and returns the node at the specified index in the linked list.

```
def remove(index)
return if index >= @length || index.negative?
return shift if index.zero?
return pop if index == @length - 1
prev = get(index - 1)
temp = prev.next
prev.next = temp.next
temp.next = nil
@length -= 1
temp
end
```

- The method first checks if the provided index is valid. If not, it returns
`nil`

. - If the index is zero, it uses the
`shift`

method to remove and return the head node. - If the index is equal to the length minus one, it uses the
`pop`

method to remove and return the tail node. - Otherwise, it retrieves the node at the previous index (index - 1) using the
`get`

method. - It updates the next references to detach the node at the specified index from the list.
- At last, we decrement length by one.
- The time complexity of the
`remove`

method is O(n), where n is the length of the linked list. - It utilizes the
`get`

method, which has a time complexity of O(n), to retrieve the node at the specified index.

###
`reverse`

Method

The reverse method reverses the linked list by changing the order of the nodes.

```
def reverse
temp = @head
@head = @tail
@tail = temp
after = temp.next
before = nil
(0...@length).each do |_i|
after = temp.next
temp.next = before
before = temp
temp = after
end
end
```

- The method starts by swapping the head and tail nodes.
- Then, it iterates through the list and reverses the next references of each node.
- It uses three variables (
`temp`

,`before`

, and`after`

) to keep track of the nodes being reversed. - The loop continues until all nodes are reversed.
- The time complexity of the
`reverse`

method is O(n), where n is the length of the linked list. - It needs to traverse the list once to reverse the nodes.

## Top comments (0)