Remove "smallest" element from a linked list?

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

  1. eksamor

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

    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??
    eksamor, Mar 29, 2006
    #1
    1. Advertising

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

    --
    BR, Vladimir

    Mother told me to be good, but she's been wrong before.
    Vladimir S. Oka, Mar 29, 2006
    #2
    1. Advertising

  3. eksamor

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

    // 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.
    , Mar 29, 2006
    #3
  4. eksamor

    Jaspreet Guest

    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
    #4
  5. eksamor

    CBFalconer Guest

    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/>
    Also see <http://www.safalra.com/special/googlegroupsreply/>
    CBFalconer, Mar 29, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

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.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    475
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    462
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    501
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    664
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    747
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page