notes on linked list

Things that are simple and easy for arrays might get messy in linked list and debugging is harder.

Some tips:

1. know the primitives

delete after prev: prev->next = prev->next->next
if you need prev->next, save the pointer.
it is usually simpler to have a dummy node so you always have a valid prev pointer.

insert p after prev: p->next = prev->next; prev->next = p;

2. maintain a tail pointer if necessary
for(p=head; p->next != NULL; p=p->next) ;
tail = p; // since p->next is NULL after loop terminates, p is tail now
when recursion, consider returning both head and tail pointer, otherwise you might have to walk through the list one more time to reach tail pointer.

3. have a conceptual picture
when doing things like reverse list, sort list, split into odd even, it is usually easier to have separate heads of lists, and you remove nodes from the input list, and grow lists in the output list.

an example is sorting, say selection sort.
you keep removing max node from input list, and insert into head of output list.

4. check NULL whenever you want to dereference using ->

5. do initialization properly, if you need to get min node or max node, initialize the minval and ptr2minval with the first node.

6. draw a picture to help with the links.

7. walk the list with two pointers make the code simpler, an example is mergesort when you need to split the list into two halves.
for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
p2 = p1->next; p1->next = NULL; p1=head;
it is easy to show that when length is even, then we cut after pos=(n/2)-1 with length n/2 in each half,
when length is odd, the first half ends at pos=(n-1)/2 with length=(n+1)/2
since p1 always walks floor((n-1)/2) steps.
and for mergesort, the merge step ends with appending p1 or p2 to output list and it is simply tail->next = p1 or p2