Linked Lists in Lua

Question

I've recently been looking up linked lists in Lua and have a quick question that so far I haven't been able to find an answer for

local head = nil

head = {next = head, value = "d"}
head = {next = head, value = "c"}
head = {next = head, value = "b"}
head = {next = head, value = "a"}

local entry = head

while entry do
  print(entry.value)

  entry = entry.next
end

This will end up printing out "a,b,c,d". I understand why it would print out backwards, as the first 'node' available would be the final one created (with value = a). My question is why the 'head's created before the final one still exist and have not simply been overwritten in the memory.

Answer 1

What do you mean by "overwritten in the memory"? Nothing you're doing would cause that to happen.

Let's look at what you're doing step by step.

local head = nil

There now exists a local variable called head. It has the value nil.

head = {next = head, value = "d"}

Let's break this down into the sequence of operations here. This is equivalent to the following:

do
  local temp = {}
  temp.next = head  --This is still `nil`
  temp.value = "d"
  head = temp
end

Every table you construct is a unique value. So let's call this first table table-d. It is constructed, stored in the temporary variable temp. The table is given a next value of nil. And it gets a value value of "d". And the result is stored in the local variable head.

So now head has the value table-d. Next step:

head = {next = head, value = "c"}

Same thing:

do
  local temp = {}
  temp.next = head  --Not nil anymore.
  temp.value = "c"
  head = temp
end

OK, we create a new table. For the sake of clarity, we'll call this table table-c.

We store this in temp. We then set it's next field to the value in head. That value is table-d. We set the value field to "c". And then store table-c into head.

The table-c table looks like this:

{
  next = { value = "d" }
  value = "c"
}

That is the table stored in head.

This continues like this. So where would something be "overwritten"?