Remove "smallest" element from a linked list?

[eksamor]

I have a simple linked list:


struct element {
struct element *next;
int start;
};

struct list {
struct element *head;
struct element *tail;
};


I would not like to make a function that removes the element with the
smallest start value.

If I have three elements in my list with the following start values:
12->5->14, the list should after the remove operation look like this:

12->14

I was thinking that I would run through all the elements in the list
and store their start value in an array:

struct element *find = list.head;
while(find != 0)
{
// store the value in an array

// jump to the next element
find = find->next;
}

I would now search through this array and return the index of the
smallest value. This value +1 is the number of times I need to travel
the head of the lists next pointer to find the smallest element in the
list. I would then have another procedure to return this element and
fix the list.


The above method seems a bit messy, is there a more optimal solution to
remove a value from a linked list with a smallest key??

 

[Vladimir S. Oka]

eksamor opined:

I have a simple linked list:


struct element {
struct element *next;
int start;
};

struct list {
struct element *head;
struct element *tail;
};


I would not like to make a function that removes the element with the

^^^

I assume you mean "now"...

smallest start value.

If I have three elements in my list with the following start values:
12->5->14, the list should after the remove operation look like this:

12->14

I was thinking that I would run through all the elements in the list
and store their start value in an array:

struct element *find = list.head;
while(find != 0)
{
// store the value in an array

// jump to the next element
find = find->next;
}

I would now search through this array and return the index of the
smallest value. This value +1 is the number of times I need to travel
the head of the lists next pointer to find the smallest element in
the list. I would then have another procedure to return this element
and fix the list.

The above method seems a bit messy, is there a more optimal solution
to remove a value from a linked list with a smallest key??

Yes, by keeping the pointer to the smallest element you found, as well.
Then, you can go directly there, and pluck it out. On second thought,
you'd also need the pointer to the one preceding it...

Not really a C question, though...

 

[manochavishal]

I have a simple linked list:

struct element {
struct element *next;
int start;




struct list {
struct element *head;
struct element *tail;



I would not like to make a function that removes the element with the
smallest start value.

If I have three elements in my list with the following start values:
12->5->14, the list should after the remove operation look like this:



I was thinking that I would run through all the elements in the list
and store their start value in an array:

why would you do that? You already have elements stored in linked list.
Just search the linked list for the smallest value

int check;
struct element *smallest;
struct element *previous;
struct element *prev;



struct element *find = list.head;
check = find->start;
while(find != 0)
{
// store the smallest value in check
if(check<find->start)
{
check = find->start;
smallest = find;
prev = previous;
}

// jump to the next element
previous = find;
find = find->next;
}


[snip]

I have not tested this code but i hope this gives you an idea of how to
remove the smallest element without using the array. As using array of
same number of elements will be against the whole idea of using the
linked list.

You can use the *smallest* as the node with smallset value and delete
it and use *prev* as the pointer to the previous node.

 

[Jaspreet]

I have a simple linked list:


struct element {
struct element *next;
int start;
};

struct list {
struct element *head;
struct element *tail;
};


I would not like to make a function that removes the element with the
smallest start value.

Not ???

If I have three elements in my list with the following start values:
12->5->14, the list should after the remove operation look like this:

12->14

I was thinking that I would run through all the elements in the list
and store their start value in an array:

struct element *find = list.head;
while(find != 0)
{
// store the value in an array

// jump to the next element
find = find->next;
}

I would now search through this array and return the index of the
smallest value. This value +1 is the number of times I need to travel
the head of the lists next pointer to find the smallest element in the
list. I would then have another procedure to return this element and
fix the list.


The above method seems a bit messy, is there a more optimal solution to
remove a value from a linked list with a smallest key??

So here's what you do :
1. One complete traversal of list to iterate through all elements and
put them into array.
2. One complete traversal of array to find the smallest element.
3. Another traversal of list to move to the smalles value element (Keep
another pointer one node before that for easy deletion or follow that
trick of deleting the element on which you are currently by copying the
value of next element into current node and then deleting the next
node, more mess)

Instead why not traverse through the list at step 1 and simultaneously
find out the smallest element and delete that. That would avoid Steps 2
and 3 above. I guess it would be better than your existing solution.

 

[CBFalconer]

I have a simple linked list:

struct element {
struct element *next;
int start;
};

struct list {
struct element *head;
struct element *tail;
};

I would not like to make a function that removes the element with
the smallest start value.

If I have three elements in my list with the following start values:
12->5->14, the list should after the remove operation look like this:

12->14

I was thinking that I would run through all the elements in the list
and store their start value in an array:

struct element *find = list.head;
while(find != 0)
{
// store the value in an array

// jump to the next element
find = find->next;
}

I would now search through this array and return the index of the
smallest value. This value +1 is the number of times I need to
travel the head of the lists next pointer to find the smallest
element in the list. I would then have another procedure to return
this element and fix the list.

The above method seems a bit messy, is there a more optimal
solution to remove a value from a linked list with a smallest key??

You define lists as starting with a dummy element, whose only
purpose is to point to the first element on the list proper. Then
you define searching for an element as searching for the element
before the one you want, i.e. the one which points to the actual
required element. Then you have no difficulty deleting elements,
inserting before elements, etc.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>