Linked Lists
Published: 2020-06-20 23:50:49

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!