Back to School: Linked List With Ruby

CS106B is awesome! Today was a lecture about Linked List as I’ve already mention about this Data structures.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, and symbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation. wikipedia

With C++ we can represent a cell in the linked list as a structure, like

1
2
3
4
struct Cell {
  string value;
  Cell* next;
};

in Ruby we can also use Struct and code our LinkedList will be like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# create a struct with :value and :next
Cell = Struct.new(:value, :next)

# create a head of our list
list = Cell.new("head. hi", nil)

# method which create one more cell and return the struct
def linked_list(value, cell)
  return Cell.new(value, cell)
end

# method which recursively print value until the asteroid...
def recursive_print(list)
  p list.value
  recursive_print(list.next) unless list.next == nil
end

# create Linked List
# #<struct Cell value=10, ... next=#<struct Cell value=1, next=#<struct Cell value="head. hi", next=nil>

i = 0
10.times {
  i += 1
  list = linked_list(i, list)
}

recursive_print(list) # print out recursively our list

Let’s test Linked List and Arrays to insert value in the top.

simple_bench.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# create a struct with :value and :next
Cell = Struct.new(:value, :next)

# create a head of our list
list = Cell.new("head. hi", nil)

# array
a = []

# method which create one more cell and return the struct
def linked_list(value, cell)
  return Cell.new(value, cell)
end

# simple benchmark timer. t1 - t2 = waiting time ;)
def bench type
  t1 = Time.now
  yield
  t2 = Time.now
  p "#{type}'s took #{t2 - t1}s"
end


bench ("array") {
  100000.times { a.insert 0,10} # O(n)
}

bench ("linked list") {
  100000.times { list = linked_list(10, list) } # O(1)
}

# results
#
# "array's took 2.661794s"
# "linked list's took 0.050272s"

I’m not sure this is good example of benchmarking, will check it later. What doest it all mean? If you want insert value in the head of array, array gets a new array and move everything over every time when you insert something.

[1, 2, 3, 4, 5, 6] -> inserting 10071983 value -> [10071983, 1, 2, 3, 4, 5, 6], so now inserting an element into a top of array can be very costly - O(n) because everytime move everything over.

with linked list you just create cell with element and pointer on next cell. [1, pointer->nil] and if we want to add new element, we just set pointer like [10071983, pointer->next] where pointer->next is reference to [1, nil]. Of course Arrays are cool, because you can do many other things faster than linked list (trade offs), but don’t forget about Algorithmic Analysis where you can find what will be faster to use in your case.