Group Group Group Group Group Group Group Group Group

Inserting a Node into a LinkedList Questions

#1

I have read through the book entirely with out doing any of the coding examples and now I am re-reading the content with doing the examples.

Upon reaching the LinkedList section we can view the insert function:

@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {

  guard tail !== node else {
    append(value)
    return tail!
  }

  node.next = Node(value: value, next: node.next)
  return node.next!
}”

There are a few questions that come up when reviewing this code that are more apparent when writing it out.

  1. What if the node does not exists in the LinkedList?
    i. Generally these are developer errors so can be overlooked, but in some scenarios we would cause a fatalerror. I understand that causing a fatalError would be O(n) of work and thus can ruin the efficiency of a LinkedList. Is that why we don’t opt in to guard out early?

  2. I am misunderstanding the relevance of the condition tail !== node. In the event that the tail is identical (not equal) to the current node wouldn’t our code be sufficient enough to handle this case? (code below)
    i. The benefit of calling append would also check if head != nil, but if our head is equal to nil then our linked list is empty and therefore the node does not exists in our linked list. Moving back up to the insert call, the tail !== node would evaluate to nil !== node which is true so we would continue to attach our node to the stray node.

node.next = Node(value: value, next: node.next)
return node.next!

My question comes down to, is there some point I am missing or do we not need to add that additional test?

#2

After doing more of the examples I realized the answer to my question regarding the conditional statement. The reason we need to call append is because the tail node is re-assigned, this is important since the tail node is not a random node but a specific reference in our linked list that we have to manage.

As a result the tail needs to be reassigned during specific operations and the append function handles that.

Considering adding a node to a stray node wouldn’t cause any problems other than creating a linked list where the head and tail are not accounted for there really is no reason why a developer would call that function with out the node existing in the linked list. The check of if a node exists in the linked list may only be functionality that would benefit a debugging environment as opposed to a production environment.

1 Like
#3

@kelvin_lau Can you please help with this when you get a chance? Thank you - much appreciated! :]

#4

You’re correct!

The append function also ensures that head and tail gets property updated. Instead of handling that logic in this insert method, we delegate that responsibility to append when necessary.