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.