Remove minimum element in linked list

JavascriptWeb DevelopmentFront End TechnologyObject Oriented Programming

Table of Contents Show

Suppose, we have a singly linked list like this −

const list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: { value: 5, next: { value: 6, next: { value: 7, next: null } } } } } } };

We are required to write a JavaScript function that takes in one such list as the first argument and a number as the second argument.

The function should search whether there exists a node with that value in the list, if it does, the function should remove the node from the list.

Example

The code for this will be −

Output

And the output in the console will be −

true { "value": 1, "next": { "value": 2, "next": { "value": 4, "next": { "value": 6, "next": { "value": 7, "next": null } } } } }

Updated on 25-Nov-2020 11:56:39

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

8982

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... -- BR, Vladimir Mother told me to be good, but she's been wrong before.

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

Jaspreet

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.

CBFalconer

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

Replies have been disabled for this discussion.