Thread: Removing odd indicies from linked list

Hello...

I have a solution to this problem, but I think it is too complicated to be optimal. I need it as simple as possible before I start coding it in assembly.

Here is what I am given (v's are values and A's are addresses pointing to the next pair):

LIST--> (v1, A1-)->(v2, A2-)->(v3,A3-)->(v4,A4-)->(v5,A5-)->(v6,A6-)->(v7,A7-)-> etc

I need to "remove" or "re-link" the list to make it look like:

LIST--> (v2,A3-)->(v4,A5-)->(v6,A7-)->etc

(The first pair being indexed at "1", with the last address in the list being NULL.)

Anyway, I tend to overcomplicate things. Here is my C code (after many revisions):

Code:

int* remOdd( int* l )
{
  int addr_pos = 1 ;
  int swap_pos = 3 ;

  // Entire list or first address is NULL
  if ( !l || !*( l + addr_pos ) )
    {
      l = NULL ;
      return l ;
    }

  // Shift to right
  l = l + 2 ;

  // Address is not NULL
  while ( *( l + addr_pos ) )
    {
      swap_pos = addr_pos + 2 ;

      // List ends on next address
      if ( !*( l + swap_pos ) )
	return l ;
      
      // Swap addresses
      *( l + addr_pos ) = *( l + swap_pos ) ; 
      addr_pos += 4 ;
    }

  return l ;
}

/* Somewhere else... */

linked_list = remOdd( linked_list ) ;

I am particularly concerned about the fact that I have to shift the list and reassign from somewhere outside of the function. (Which I may not have to do, but I couldn't figure out any other way...)

I would like to make it one big recursive function if at all possible.

Anybody know if there is any way to make this notably simpler?

That's not a linked list. That's an array of integers.

Code:

memmove( list + offset, list + offset + skip, (listlen - offset - skip) * sizeof *list );
memset( list + offset + skip, 0, skip * sizeof *list );

That looks about right. Or, if you want to roll your own, use a for loop with the above for determining how many places you move, and copy them by hand.

Long story short: You don't have a linked list, it's an array. "deleting" from an array means you shift the array elements around. No way around it.


Quzah.

The actual problem I am dealing with in assembly is a linked list. I just made an array for modelling purposes because it is easier to translate into MIPS assembly. Assembly is rather annoying when it comes to this sort of stuff.

That said, I think the above was way wrong.

I am actually writing the assembly right now and it looks like I have to do this:

- Copy contents of 2nd pair into BASE

- Recursively go to address in current (i.e. BASE NEXT-->X) and set X's NEXT to X+1's NEXT, etc

Like this, sort of:

Code:

void remOdd( )
{
  if ( !list )
    return ;

  // Shift head
  list = list->next ;
  struct node* node = list ;

  // Relink
  while ( node )
    {
      if ( !node->next )
	return ;
      
      node->next = ( node->next )->next ;
      node = node->next ;
    }
  
  return ;
}

If all you are doing is snipping out chunks, find the first node you want to keep:

Code:

while( keep->next != kepttail )
{
    temp = keep->next;
    keep->next = keep->next->next; 
    free( temp );
}

I'm not sure why this is hard, just loop until it's lined up right.


Quzah.

Originally Posted by Ryan.

The actual problem I am dealing with in assembly is a linked list.

Then don't post code for an array, as it will simply confuse others. The bold example you gave is sufficient to explain the problem.

To perform optimisation of this kind, first start with the simple way of coding it that actually works. Next, once it works, think about improvements.
Always make your improvements on a copy. Keep the orignal good working (but possibly slow) code around for several reasons:
You can easily verify that they behave the same in all cases, and
you have something to compare your optimised code to to know if it is in fact faster in any way.
In case you haven't heard it before: "Get it working first, then get it fast".

Now, why do you want to write any of this in assembly? From a performance and maintainability perspective that most likely isn't beneficial here.

Ah right. I wonder then if there are any forums out there for MIPS assembly that would be even more useful.