4 ms·
Let's draw a list IntListItem -> IntListItem -> IntListItem and then draw the position of the list head: IntList -> IntListItem -> IntListItem -> IntList
by wanderer2323 6y ago
Let's draw a list
IntListItem -> IntListItem -> IntListItem
and then draw the position of the list head:
IntList -> IntListItem -> IntListItem -> IntListItem
You can see that the if-branch in the cs101 answer comes because there is a ('virtual') element of the list (the IntList head) that is different from the other elements of the list.
If we were to make them the same (C# code):
interface IListItem
{
IntListItem Next {get;set;}
}
class IntListItem : IListItem
{
int Value {get; set;}
IntListItem Next {get; set;}
}
class IntList : IListItem
{
IntListItem Head {get; set;}
IntListItem Next
{
get { return Head; }
set { Head = value; }
}
}
then our cs101 code simplifies itself, folding into a prettier algorithm:
void remove_cs102(IntList l, IntListItem target)
{
IListItem p = (IListItem) l;
while (p.Next != target)
{
p = (IListItem) p.Next;
}
p.Next = p.Next.Next;
}
the use of indirect pointers was masking the real issue: some algorithms look better if you add a virtual head (or a virtual tail) to your linked list. Emphasis on look though -- they work almost the same.
- ghusbands 6y agoYou've just introduced the extra indirection of virtual function pointers, perhaps through an extra indirection layer of interfaces, which will be a big performance hit, so you've hardly hit upon the "real issue".
- scscsc 6y agoThat looks interesting. The code is not simpler to understand nor is it more efficient, but it seems to work, assuming target is in the list. How would you represent the empty list? Not sure why you are being downvoted.
- wanderer2323 6y agoThe representation of the empty list does not change, it's still an IntList object with a null Head field. The downvotes probably come from my blatant disregard of the real-world performance in the search of what I considered the real take-away from the article.