CODEWITHSUNDEEP
algorithmlinked-listcomplexity-theorytime-complexity
Doug Smith
Doug Smith

Reputation: 29326

What is this portion of The Algorithm Design Manual saying? I'm confused

This is from The Algorithm Design Manual when talking about Dictionaries being implemented with Linked Lists.

enter image description here

For one, with the portion that says "on insertion check whether last->next still equals NULL`. Why would we have to check that? If I'm inserting an element, how would that affect whether or not the last item rightfully points to NULL? If we're doing our implementations correctly, shouldn't it already? Couldn't we just say something like:

last->next = nodeToInsert;
last = last->next;

Why wouldn't that work?

Secondly, is the second last paragraph talking about the case where we delete the last item in a singly-linked list and have to identify the new last item? And that we'd just (with O(n) complexity) traverse to the second last item and set that to last and delete the former last? And we mix this with the pre-existing delete method, just adding a case for if it's the last item?

Upvotes: 1

Views: 157

Answers (3)

R2D2M2
R2D2M2

Reputation: 271

if(last->next != NULL) {   // insertion occurred at the tail end
    last = nodeToInsert;   // so update tail pointer to point to inserted node
}

The tail end insertion has set last->next already. It is no longer NULL because of the insertion. That is what tells us that last needs to be updated (last is now actually lastButOne). If last->next is still NULL then we don't need to do anything because the insertion occurred somewhere before last. The wording of your book is, perhaps, slightly misleading. Does this make sense now?

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Note that this section is talking about dictionaries being implemented as sorted lists.

This means that the insertion needs to happen at exactly the right point. Your suggested code adds to the end of the list:

last->next = nodeToInsert;
last = last->next;

This would be correct for unsorted lists, but not for sorted.

Also note that the author is using last as a pointer that is additional to the normal linked list.

I think you believe that last is part of the doubly linked list structure. If this were so, then you would be correct that it should have been updated during the insertion. However, as it is an independent pointer, the additional code described in the text is required to keep it consistent with the linked list.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272687

Why would we have to check that?

Because presumably you're not always inserting at the end of the list, so last doesn't always need to be updated.

Secondly, ...

Yes.

Upvotes: 3

Related Questions