When it comes to data types the array & linked list are birds of a feather. Both have their strengths & weaknesses. With an array, it's quick to access the required data with the help of an index. By contrast to request data from a linked list you have to traverse the entire data structure until the related data is found.

That being said, the linked list is faster when it comes to inserting a value in the middle of the data structure. All one would have to do is change the "next" value of the linked list's previous node. To do the same with an array all values after the insertion would have to be shifted over one index.

Here is a ruby implementation that shows how a linked list can be implemented with two classes. First the node:

```
class Node
attr_accessor :next
attr_reader :value
def initialize(value)
@value = value
@next = nil
end
def to_s
"Node with value: #{@value}"
end
end
```

We create two variables, "value" and "next" with value as read-only, & "next" with read / write access as to insert a value into the list, one would only have to change the value of "next".

Now for the list itself:

```
class LinkedList
def initialize
@head = nil
end
def append(value)
if @head
find_tail.next = Node.new(value)
else
@head = Node.new(value)
end
end
def find_tail
node = @head
return node if !node.next
return node if !node.next while (node = node.next)
end
def append_after(target, value)
node = find(target)
return unless node
old_next = node.next
node.next = Node.new(value)
node.next.next = old_next
end
def find(value)
node = @head
return node if node.value == value
return false if !node.next
while (node = node.next)
return node if node.value == value
end
end
def delete(value)
if @head.value == value
@head = @head.next
return
end
node = find_before(value)
node.next = node.next.next
end
def find_before(value)
node = @head
return false if !node.next
return node if node.next.value == value
while (node = node.next)
return node if node.next && node.next.value == value
end
end
def print
node = @head
puts node
while (node = node.next)
puts node
end
end
end
```

Here we find a number of helper methods which allow the linked list to be updated or maintained. #append iterates through the list, having #find_tail use a while statement to locate the node with a value equal to "null".

The method #append_after does the same iteration looking for a node with the help of #find. #find locates a value first by checking to see if it is the first node in the list, then check to see if there's no following nodes returning false if so, if not then using another while statement for iteration.

The #delete method doesn't necessarily "delete" the node, but changes the values of "node.next" in the previous and following nodes.

Searching with #find_before does the same iterations as above, this time only checking to see if the value asked for is equal to node.next.

As you can see a good linked list implementation can be done with only a way to represent the node, & a way to organize, search, & append to said list. Creating and maintaining a hash table as the list is created & updated is one way to solve for the search inadequacies.

Happy storing!

## Top comments (0)