# Remove "smallest" element from a linked list?

Discussion in 'C Programming' started by eksamor, Mar 29, 2006.

1. ### eksamorGuest

I have a simple linked list:

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

struct list {
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

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??

eksamor, Mar 29, 2006

2. ### Vladimir S. OkaGuest

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...

--

Mother told me to be good, but she's been wrong before.

Vladimir S. Oka, Mar 29, 2006

3. ### Guest

>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:

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;
}

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

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

, Mar 29, 2006
4. ### JaspreetGuest

eksamor wrote:
> 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.

Jaspreet, Mar 29, 2006
5. ### CBFalconerGuest

eksamor wrote:
>
> 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/>

CBFalconer, Mar 29, 2006

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.