linked-list

linked-list copied to clipboard

List tail should always be set for non-empty lists, including when a list has only one item. In the one item case, head and tail should be the same, both pointing to the single item in the list. This preserves the defining capabilities of a doubly linked list:

• start at the head and walk forward through the entire list using next
• start at the tail and walk backward through the entire list using prev

At this time, linked-list sets the tail to null if there is only one item in the list. This is incorrect, IMO, and difficult to work with.

Consider using List to implement a FIFO queue.

• The writer is obvious. It calls list.prepend(item) whenever it needs to add an item to the queue.
• The reader should also be obvious. It should be able to drain the queue with this simple loop:

while (list.tail) {
  process(list.tail.detach())
}

Sadly, the current implementation of List requires something like

while (list.size > 0) {
  const item = (list.size === 1) ? list.head : list.tail
  process(item.detach())
}

which is uglier, but maybe more clear, or

while (list.tail || list.head) {
  process((list.tail || list.head).detach())
}

which is prettier, but mysterious.

Both of these loops are implementation specific, and I find them difficult to understand.

There is special case code here to make tail go away when the list shrinks to a single item, and two one-liners are omitted here and here to leave tail null when the first item is added. This behavior is also asserted in test.js, so I'm guessing there was a reason for this null tail behavior.

Thoughts?

It is intentional. This is very old though, so I can’t my original reasoning is vague. And it also means that I’m less inclined to change things.

A clearer loop, in my opinion, would be:

let item = list.tail || list.head

while (item) {
    doThing(item.detach())
    item = list.tail || list.head
}

Or, use item.prev:

let item = list.tail || list.head

while (item) {
    let prev = item.prev
    doThing(prev.detach())
    item = prev
}

cool. thanks for the speedy reply

Is using prev fine for you?

Closing :)