deleting a node from linked list based on the pointer from the vector

[nabh4u]

hi,
i have a double linked list containing some elements and i have a vector which stores the address of the elements in the list (pointer to the list). i want to delete a value from the list,like the nth value enetered in the list, in constant time. how do i do that?
i got the address of the element to be deleted from the vector but how do i relate that address with the element in the list and then delete it and rearrange the pointers for the previous and next elements in the list?
can i get a sample code for tht?
thank you very much in advance...

[DeMan]

If I understand your question correctly: you have a doubly linked list, and you have a Vector storing a reference to each element in the list in order....
The Vector is presumably added so that you can make this removal in constant time.....
There are several ways to approach this, but I think the easiest is (where Vector is v, and I assume you have methods to set next pointer and previous pointer of a node and a remove function in your Vector. (This is not necesasarily accurate c code but should give you an idea of the process)

(*v[n+1]).prevElement(*v[n-1]);  /* Set element after n to point befor en */
(*v[n-1]).nextElement(*v[n+1]); /* Set element pefore n to point after n */
v.remove(n);
 

This of course assumes that the vector n can do access operations in constant time (an array implementation certainly could, but most vector implementations I've seen would do this in linear time).

[nabh4u]

If I understand your question correctly: you have a doubly linked list, and you have a Vector storing a reference to each element in the list in order....
The Vector is presumably added so that you can make this removal in constant time.....
There are several ways to approach this, but I think the easiest is (where Vector is v, and I assume you have methods to set next pointer and previous pointer of a node and a remove function in your Vector. (This is not necesasarily accurate c code but should give you an idea of the process)

(*v[n+1]).prevElement(*v[n-1]);  /* Set element after n to point befor en */
(*v[n-1]).nextElement(*v[n+1]); /* Set element pefore n to point after n */
v.remove(n);
 

This of course assumes that the vector n can do access operations in constant time (an array implementation certainly could, but most vector implementations I've seen would do this in linear time).

you got my point but i didnt really understand what you meant to say. how can we access a function with vectors? and what does the remove function consist of? can you give me an example of the remove function.
one more point - if the user enters like delete the first element entered in the list, that means the first value entered in the vector which will be at index 0. now if we use (*v[n+1]).prevElement(* v[n-1]);
(*v[n-1]).nextElement(* v[n+1]);
then n-1 will be -1 which is not acceptable..
please give some sample code

[DeMan]

OK....

Not sure what you meabn by accessing a function with Vectros, but the idea of Object Oriented Programming is that given an object you can do things to it because it is that object (so if you know that v is a pointer to an object whose definition includes a toString method, you know that (*v).toString() will call that mehtod)

The remove function (presumably) is defined by the Vector class..... the specific implementation of this class will actually determine whether the operation is constant or linear (if you have to implement the Vector class, I would suggest an Array in this instance)

Good point....
You should probably check where your pointers are in the linked list (although since you have the Vector, this should be reasonably trivial (0 and (Size -1) should eb the tricky ones -> and you can make a special case for that))

[nabh4u]

OK....

Not sure what you meabn by accessing a function with Vectros, but the idea of Object Oriented Programming is that given an object you can do things to it because it is that object (so if you know that v is a pointer to an object whose definition includes a toString method, you know that (*v).toString() will call that mehtod)

The remove function (presumably) is defined by the Vector class..... the specific implementation of this class will actually determine whether the operation is constant or linear (if you have to implement the Vector class, I would suggest an Array in this instance)

Good point....
You should probably check where your pointers are in the linked list (although since you have the Vector, this should be reasonably trivial (0 and (Size -1) should eb the tricky ones -> and you can make a special case for that))

thank you very much

[DeMan]

Incidently (I was thinking about this last night)....The remove operatiobns is constant time in the Double Linked List, but I'm noit sure that the removal of an eleemnt in the Vector would be, so a puritan would probably say that this operation is not done in constant tim,e......

[nabh4u]

Incidently (I was thinking about this last night)....The remove operatiobns is constant time in the Double Linked List, but I'm noit sure that the removal of an eleemnt in the Vector would be, so a puritan would probably say that this operation is not done in constant tim,e......

i have resolved the problem of deleting....
now i have 2 vectors and first vector consists of the list values to be sorted. the second vector is the final vector where the sorted values will be there. while sorting i have to count inversions (eg. list has 2 1 then on sorting we get 1 2 and number of inversions will be 1. while if the list is 1 1 3 then the number of inversions will be zero.). while using the recurrsive function i want the first vector to be updated with the second vector values at same positions.
eg: if first vector [1 3 1]
second vector [1 1 3]. so i want the first vector to take d values of the second vector.

please suggest some solution...

thanks

[DeMan]

There are loads of approaches to this problem (and you may do well to google something like "sort c" or one of the many different sorting algorithms (do you maybe need to use a particular one, or is any reasonable?)

one (longish approach) would be to iterate through the whole vector to find the lowest value, then the next lowest etc....

Slightly more efficient in the average case (but at its' simplest equally bad in the worst case), you take the first value of Vector1 and store it in Vector2, then you take the next value in Vector1 and work out where it goes in Vector2.
To make this algorithm a little more efficient, you can use a binary search approach, to find where in the Vector2 you would need to insert the next node....To do this efficiently, you would probably need an array or something keeping track of nodes (whose overhead would counteract the saving).

If there is no requirement that you use Vectors, you could use a binary tree, which you populate from Vector1, and then traverse to populate Vector2....In the worst case (depending on how you implement the tree, but assuming you don't insist on a balanced tree (and depending on the size of the data, the overhead for a balanced tree may not be worth it), the worst case would still be as bad as the other options (n -squared I think)), but the average case would be n log n.

There are many other options also, but hopefully these give you some ideas....