On Wed, Dec 18, 2024 at 10:51 AM Franco Martelli <martelli...@gmail.com> wrote:
>
> On 17/12/24 at 22:09, Jeffrey Walton wrote:
> > [...]
> > There may be one logic error in the code -- if you insert one item,
> > then you may double free the node because you free 'p' and then you
> > free 'last'.
> >
> > I would rewrite the cleanup code like so:
> >
> > void dealloc()
> > {
> > DIGIT *next, *p = head;
> > while( p )
> > next = p->next, free( p ), p = next;
> > }
> >
> > Then add three test cases instead of one. Have a test case for 0
> > items, 1 item, and N items (like 8).
>
> I like the "for loop" statement because let me to define variables that
> are in use only inside the loop, so I can avoid variables that are
> visible in the full function block but are in use only in a (while(…)) loop:
>
> void dealloc()
> {
> for( DIGIT *next, *p = head; p ; )
> next = p->next, free( p ), p = next;
> }
>
> The use of comma operator for me doesn't hurt, I always read the code
> from left to right.
> Thanks for this new optimization.
Another area you can optimize is `add_element` around line 23:
/* Otherwise, find the last element in the list */
for (p = head; p->next != NULL; p = p->next)
; /* null statement */
The code as written is Big O(n^2) since it walks the entire list on
each insert. So the code visits 1 node on the first insert, 2 nodes on
the second insert, 3 nodes on the 3rd insert, etc. 1+2+3+...+N is
(n*(n-1))/2, which is Big O(n^2).
You might try using `tail` to do the insert. Using `tail` will be
constant time or Big O(1).
If you want to measure the time, then use a string of 1000 or 5000
characters or so. The longer the string, the more time it will take to
insert under the current code.
Jeff
