15 ways to make a linked list

15_ways_to_make_a_linked_list.rb

# ----- Common Linked List Methods -----

def add_to_front(list, data)
  build_list(data, list)
end

def add_to_back(list, data)
  return build_list(data, empty_list) if empty?(list)
  new_tail = add_to_back(tail(list), data)
  build_list(head(list), new_tail)
end

def empty?(list)
  list == empty_list
end

def show(list)
  array = []
  until empty? list
    array << head(list)
    list = tail(list)
  end
  array
end

def empty_list
  nil
end


# ----- Arrays -----

def build_list(head, tail)
  [head, tail]
end

def head(list)
  list[0]
end

def tail(list)
  list[1]
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => ["c", nil]
list = add_to_front list, 'b' # => ["b", ["c", nil]]
list = add_to_front list, 'a' # => ["a", ["b", ["c", nil]]]
list = add_to_back  list, 'd' # => ["a", ["b", ["c", ["d", nil]]]]
list = add_to_back  list, 'e' # => ["a", ["b", ["c", ["d", ["e", nil]]]]]
list = add_to_back  list, 'f' # => ["a", ["b", ["c", ["d", ["e", ["f", nil]]]]]]

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Arrays with fancy syntax -----

def build_list(*list)
  list
end

def head((head, tail))
  head
end

def tail((head, tail))
  tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => ["c", nil]
list = add_to_front list, 'b' # => ["b", ["c", nil]]
list = add_to_front list, 'a' # => ["a", ["b", ["c", nil]]]
list = add_to_back  list, 'd' # => ["a", ["b", ["c", ["d", nil]]]]
list = add_to_back  list, 'e' # => ["a", ["b", ["c", ["d", ["e", nil]]]]]
list = add_to_back  list, 'f' # => ["a", ["b", ["c", ["d", ["e", ["f", nil]]]]]]

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Hashes -----

def build_list(head, tail)
  {head: head, tail: tail}
end

def head(list)
  list[:head]
end

def tail(list)
  list[:tail]
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => {:head=>"c", :tail=>nil}
list = add_to_front list, 'b' # => {:head=>"b", :tail=>{:head=>"c", :tail=>nil}}
list = add_to_front list, 'a' # => {:head=>"a", :tail=>{:head=>"b", :tail=>{:head=>"c", :tail=>nil}}}
list = add_to_back  list, 'd' # => {:head=>"a", :tail=>{:head=>"b", :tail=>{:head=>"c", :tail=>{:head=>"d", :tail=>nil}}}}
list = add_to_back  list, 'e' # => {:head=>"a", :tail=>{:head=>"b", :tail=>{:head=>"c", :tail=>{:head=>"d", :tail=>{:head=>"e", :tail=>nil}}}}}
list = add_to_back  list, 'f' # => {:head=>"a", :tail=>{:head=>"b", :tail=>{:head=>"c", :tail=>{:head=>"d", :tail=>{:head=>"e", :tail=>{:head=>"f", :tail=>nil}}}}}}

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- OpenStruct -----

require 'ostruct'

def build_list(head, tail)
  OpenStruct.new head: head, tail: tail
end

def head(list)
  list.head
end

def tail(list)
  list.tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<OpenStruct head="c", tail=nil>
list = add_to_front list, 'b' # => #<OpenStruct head="b", tail=#<OpenStruct head="c", tail=nil>>
list = add_to_front list, 'a' # => #<OpenStruct head="a", tail=#<OpenStruct head="b", tail=#<OpenStruct head="c", tail=nil>>>
list = add_to_back  list, 'd' # => #<OpenStruct head="a", tail=#<OpenStruct head="b", tail=#<OpenStruct head="c", tail=#<OpenStruct head="d", tail=nil>>>>
list = add_to_back  list, 'e' # => #<OpenStruct head="a", tail=#<OpenStruct head="b", tail=#<OpenStruct head="c", tail=#<OpenStruct head="d", tail=#<OpenStruct head="e", tail=nil>>>>>
list = add_to_back  list, 'f' # => #<OpenStruct head="a", tail=#<OpenStruct head="b", tail=#<OpenStruct head="c", tail=#<OpenStruct head="d", tail=#<OpenStruct head="e", tail=#<OpenStruct head="f", tail=nil>>>>>>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Normal Objects -----

class MyList
  attr_reader :head, :tail
  def initialize(head, tail)
    @head = head
    @tail = tail
  end
end

def build_list(head, tail)
  MyList.new(head, tail)
end

def head(list)
  list.head
end

def tail(list)
  list.tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<MyList:0x007faac2037f90 @head="c", @tail=nil>
list = add_to_front list, 'b' # => #<MyList:0x007faac2037d10 @head="b", @tail=#<MyList:0x007faac2037f90 @head="c", @tail=nil>>
list = add_to_front list, 'a' # => #<MyList:0x007faac2037a40 @head="a", @tail=#<MyList:0x007faac2037d10 @head="b", @tail=#<MyList:0x007faac2037f90 @head="c", @tail=nil>>>
list = add_to_back  list, 'd' # => #<MyList:0x007faac2037270 @head="a", @tail=#<MyList:0x007faac2037298 @head="b", @tail=#<MyList:0x007faac20372c0 @head="c", @tail=#<MyList:0x007faac20372e8 @head="d", @tail=nil>>>>
list = add_to_back  list, 'e' # => #<MyList:0x007faac2036d70 @head="a", @tail=#<MyList:0x007faac2036d98 @head="b", @tail=#<MyList:0x007faac2036dc0 @head="c", @tail=#<MyList:0x007faac2036de8 @head="d", @tail=#<MyList:0x007faac2036e38 @head="e", @tail=nil>>>>>
list = add_to_back  list, 'f' # => #<MyList:0x007faac20367a8 @head="a", @tail=#<MyList:0x007faac20367f8 @head="b", @tail=#<MyList:0x007faac2036820 @head="c", @tail=#<MyList:0x007faac2036848 @head="d", @tail=#<MyList:0x007faac2036870 @head="e", @tail=#<MyList:0x007faac2036898 @head="f", @tail=nil>>>>>>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Singleton objects -----

def build_list(head, tail)
  list = Object.new
  list.define_singleton_method(:head) { head }
  list.define_singleton_method(:tail) { tail }
  list
end

def head(list)
  list.head
end

def tail(list)
  list.tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<Object:0x007faac2035dd0>
list = add_to_front list, 'b' # => #<Object:0x007faac2035a60>
list = add_to_front list, 'a' # => #<Object:0x007faac2035718>
list = add_to_back  list, 'd' # => #<Object:0x007faac2034f98>
list = add_to_back  list, 'e' # => #<Object:0x007faac2034778>
list = add_to_back  list, 'f' # => #<Object:0x007faac202fd68>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Blocks (enclosing local vars) -----

def build_list(head, tail)
  lambda { |which| which == :head ? head : tail }
end

def head(list)
  list.call :head
end

def tail(list)
  list.call :tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<Proc:0x007faac202f4a8@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>
list = add_to_front list, 'b' # => #<Proc:0x007faac202f250@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>
list = add_to_front list, 'a' # => #<Proc:0x007faac202efd0@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>
list = add_to_back  list, 'd' # => #<Proc:0x007faac202ebc0@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>
list = add_to_back  list, 'e' # => #<Proc:0x007faac202e850@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>
list = add_to_back  list, 'f' # => #<Proc:0x007faac202e468@/var/folders/7g/mbft22555w3_2nqs_h1kbglw0000gn/T/seeing_is_believing_temp_dir20150721-14109-qjz80f/program.rb:197 (lambda)>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Fibers -----

def build_list(head, tail)
  Fiber.new do |y|
    loop do
      Fiber.yield(head)
      Fiber.yield(tail)
    end
  end
end

def head(list)
  head = list.resume
  tail = list.resume
  head
end

def tail(list)
  head = list.resume
  tail = list.resume
  tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<Fiber:0x007faac202d9f0>
list = add_to_front list, 'b' # => #<Fiber:0x007faac202d6a8>
list = add_to_front list, 'a' # => #<Fiber:0x007faac202cfc8>
list = add_to_back  list, 'd' # => #<Fiber:0x007faac202c780>
list = add_to_back  list, 'e' # => #<Fiber:0x007faac202c348>
list = add_to_back  list, 'f' # => #<Fiber:0x007faac2027bb8>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Queues -----

def build_list(head, tail)
  Queue.new << head << tail
end

def head(list)
  head = list.shift
  tail = list.shift
  list << head << tail
  head
end

def tail(list)
  head = list.shift
  tail = list.shift
  list << head << tail
  tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<Thread::Queue:0x007faac2027460>
list = add_to_front list, 'b' # => #<Thread::Queue:0x007faac2027208>
list = add_to_front list, 'a' # => #<Thread::Queue:0x007faac2026fb0>
list = add_to_back  list, 'd' # => #<Thread::Queue:0x007faac2026bc8>
list = add_to_back  list, 'e' # => #<Thread::Queue:0x007faac2026790>
list = add_to_back  list, 'f' # => #<Thread::Queue:0x007faac2026290>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Structs -----

def build_list(head, tail)
  Struct.new(:head, :tail).new(head, tail)
end

def head(list)
  list.head
end

def tail(list)
  list.tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<struct head="c", tail=nil>
list = add_to_front list, 'b' # => #<struct head="b", tail=#<struct head="c", tail=nil>>
list = add_to_front list, 'a' # => #<struct head="a", tail=#<struct head="b", tail=#<struct head="c", tail=nil>>>
list = add_to_back  list, 'd' # => #<struct head="a", tail=#<struct head="b", tail=#<struct head="c", tail=#<struct head="d", tail=nil>>>>
list = add_to_back  list, 'e' # => #<struct head="a", tail=#<struct head="b", tail=#<struct head="c", tail=#<struct head="d", tail=#<struct head="e", tail=nil>>>>>
list = add_to_back  list, 'f' # => #<struct head="a", tail=#<struct head="b", tail=#<struct head="c", tail=#<struct head="d", tail=#<struct head="e", tail=#<struct head="f", tail=nil>>>>>>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- JSON -----

require 'json'

def build_list(head, tail)
  JSON.dump head: head, tail: tail
end

def head(list)
  JSON.parse(list, symbolize_names: true)[:head]
end

def tail(list)
  JSON.parse(list, symbolize_names: true)[:tail]
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => "{\"head\":\"c\",\"tail\":null}"
list = add_to_front list, 'b' # => "{\"head\":\"b\",\"tail\":\"{\\\"head\\\":\\\"c\\\",\\\"tail\\\":null}\"}"
list = add_to_front list, 'a' # => "{\"head\":\"a\",\"tail\":\"{\\\"head\\\":\\\"b\\\",\\\"tail\\\":\\\"{\\\\\\\"head\\\\\\\":\\\\\\\"c\\\\\\\",\\\\\\\"tail\\\\\\\":null}\\\"}\"}"
list = add_to_back  list, 'd' # => "{\"head\":\"a\",\"tail\":\"{\\\"head\\\":\\\"b\\\",\\\"tail\\\":\\\"{\\\\\\\"head\\\\\\\":\\\\\\\"c\\\\\\\",\\\\\\\"tail\\\\\\\":\\\\\\\"{\\\\\\\\\\\\\\\"head\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\"d\\\\\\\\\\\\\\\",\\\\\\\\\\\\\\\"tail\\\\\\\\\\\\\\\":null}\\\\\\\"}\\\"}\"}"
list = add_to_back  list, 'e' # => "{\"head\":\"a\",\"tail\":\"{\\\"head\\\":\\\"b\\\",\\\"tail\\\":\\\"{\\\\\\\"head\\\\\\\":\\\\\\\"c\\\\\\\",\\\\\\\"tail\\\\\\\":\\\\\\\"{\\\\\\\\\\\\\\\"head\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\"d\\\\\\\\\\\\\\\",\\\\\\\\\\\\\\\"tail\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\"{\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"head\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"e\\\\\\\\\\\\\\\\\\\\\\\\\\...
list = add_to_back  list, 'f' # => "{\"head\":\"a\",\"tail\":\"{\\\"head\\\":\\\"b\\\",\\\"tail\\\":\\\"{\\\\\\\"head\\\\\\\":\\\\\\\"c\\\\\\\",\\\\\\\"tail\\\\\\\":\\\\\\\"{\\\\\\\\\\\\\\\"head\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\"d\\\\\\\\\\\\\\\",\\\\\\\\\\\\\\\"tail\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\"{\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"head\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\":\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"e\\\\\\\\\\\\\\\\\\\\\\\\\\...

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- YAML -----

require 'yaml'

def build_list(head, tail)
  YAML.dump head: head, tail: tail
end

def head(list)
  YAML.load(list)[:head]
end

def tail(list)
  YAML.load(list)[:tail]
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => "---\n:head: c\n:tail: \n"
list = add_to_front list, 'b' # => "---\n:head: b\n:tail: \"---\\n:head: c\\n:tail: \\n\"\n"
list = add_to_front list, 'a' # => "---\n:head: a\n:tail: |\n  ---\n  :head: b\n  :tail: \"---\\n:head: c\\n:tail: \\n\"\n"
list = add_to_back  list, 'd' # => "---\n:head: a\n:tail: |\n  ---\n  :head: b\n  :tail: |\n    ---\n    :head: c\n    :tail: \"---\\n:head: d\\n:tail: \\n\"\n"
list = add_to_back  list, 'e' # => "---\n:head: a\n:tail: |\n  ---\n  :head: b\n  :tail: |\n    ---\n    :head: c\n    :tail: |\n      ---\n      :head: d\n      :tail: \"---\\n:head: e\\n:tail: \\n\"\n"
list = add_to_back  list, 'f' # => "---\n:head: a\n:tail: |\n  ---\n  :head: b\n  :tail: |\n    ---\n    :head: c\n    :tail: |\n      ---\n      :head: d\n      :tail: |\n        ---\n        :head: e\n        :tail: \"---\\n:head: f\\n:tail: \\n\"\n"

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- ActiveRecord -----

require 'active_record'
ActiveRecord::Base.establish_connection adapter: 'sqlite3', database: ':memory:'
ActiveRecord::Schema.define do
  self.verbose = false
  create_table :ar_lists do |t|
    t.string  :head
    t.integer :tail_id
  end
end

class ArList < ActiveRecord::Base
  has_one :tail, class_name: 'ArList', foreign_key: 'tail_id'
end

def build_list(head, tail)
  ArList.create! head: head, tail: tail
end

def head(list)
  list.head
end

def tail(list)
  list.tail
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => #<ArList id: 1, head: "c", tail_id: nil>
list = add_to_front list, 'b' # => #<ArList id: 2, head: "b", tail_id: nil>
list = add_to_front list, 'a' # => #<ArList id: 3, head: "a", tail_id: nil>
list = add_to_back  list, 'd' # => #<ArList id: 7, head: "a", tail_id: nil>
list = add_to_back  list, 'e' # => #<ArList id: 12, head: "a", tail_id: nil>
list = add_to_back  list, 'f' # => #<ArList id: 18, head: "a", tail_id: nil>

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Strings of object ids -----

def build_list(head, tail)
  "#{head.object_id} #{tail.object_id}"
end

def head(list)
  head_id = list.split.first.to_i
  ObjectSpace._id2ref(head_id)
end

def tail(list)
  tail_id = list.split.last.to_i
  ObjectSpace._id2ref(tail_id)
end

list = empty_list             # => nil
list = add_to_front list, 'c' # => "70185689726120 8"
list = add_to_front list, 'b' # => "70185689725800 70185689726060"
list = add_to_front list, 'a' # => "70185689725320 70185689725720"
list = add_to_back  list, 'd' # => "70185689725320 70185689724500"
list = add_to_back  list, 'e' # => "70185689725320 70185689723440"
list = add_to_back  list, 'f' # => "70185689725320 70185689722100"

show list # => ["a", "b", "c", "d", "e", "f"]


# ----- Processes -----

def self.empty_list
  -1
end

# due to the interface I defined not having a base, we have nowhere to store this var
# so making it global, even though in reality, this is a stupid interface
$children = []
at_exit do
  $children.each { |child| child.puts "exit" }
end

def build_list(head, tail)
  fd = IO.popen [RbConfig.ruby, '-l', '-n', '-e', "
    if $_ == 'head'
      puts #{head.inspect}
    elsif $_ == 'tail'
      puts #{tail.inspect}
    else
      exit
    end
    $stdout.flush
  "], "w+"
  $children << fd
  $children.index(fd)
end

def head(list)
  child = $children[list]
  child.puts "head"
  child.gets.chomp
end

def tail(list)
  child = $children[list]
  child.puts "tail"
  child.gets.to_i
end

list = empty_list             # => -1
list = add_to_front list, 'c' # => 0
list = add_to_front list, 'b' # => 1
list = add_to_front list, 'a' # => 2
list = add_to_back  list, 'd' # => 6
list = add_to_back  list, 'e' # => 11
list = add_to_back  list, 'f' # => 17

show list # => ["a", "b", "c", "d", "e", "f"]