Linked Lists

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!