Timeline for Standardized Data Structure Interface
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 1, 2012 at 20:05 | comment | added | Caleb | That's one reason that people sometimes choose a doubly-linked list instead of a singly-linked list. Once again, each structure has its own combination of strengths and weaknesses -- I don't think you're going to find one common interface that works well with all of them. The interfaces are different for a reason. | |
| May 1, 2012 at 18:37 | comment | added | max | That's why I'm asking for an efficient common interface. If you already iterated through a list, and you want to delete the element you found, you need to be given, during the iteration, a pointer to the previous element. When you already iterated through an array, and you want to delete an element you found, you need to be given, during the iteration, the index of the element. Of course some operations would still take longer; e.g., removal from an array is slower than from a list - but at least I won't have to search for the element before I can remove it! | |
| May 1, 2012 at 18:21 | comment | added | Caleb |
If you want to find the 17th element in a linked list, start at the head and follow the first 16 next links. Works fine but it's slow because a linked list is not an array. Want to insert an element at the beginning of an array? Move all the others up one spot first. Again, works fine but it's slow because an array is not a linked list. This is just what I was saying above: to impose a standard interface on these different structures is to lose the features which make them different and useful.
|
|
| May 1, 2012 at 17:47 | comment | added | max | One example of what I'm struggling with. To efficiently delete an element from a linked list I need the pointer to the previous element; from an array, the element's index; from a set, the element itself; and so on. I was trying to design an iteration protocol that provides me such things uniformly from all classes, but I feel if it makes sense, it would have been done already. So perhaps I'm on the wrong path. | |
| May 1, 2012 at 17:26 | comment | added | Caleb | So create one. Create a list class, and then implement it in terms of array, linked list, heap, and whatever else you like. | |
| May 1, 2012 at 17:17 | comment | added | max | Suppose my algorithm stays the same. Sort, if the structure isn't sorted. Iterate, and observe differences. Find the two closest elements. Remove them. This can be done without loss of performance in each of these data structures; trouble is, I cannot find a common interface to do it with. | |
| May 1, 2012 at 16:57 | history | answered | Caleb | CC BY-SA 3.0 |