Thread: Linked List question

When inserting data value into unsorted linked list, where is most efficient to add the new data value? Before first element? After last element?

When Inserting into unsorted array-based list, where is most efficient position to add new data value?

Also, most efficient way to delete data value from sorted array-based list?
-locate position and shift each value one position towards beginning of array, towards end of array?

Originally Posted by Mr.777

Add to front and delete from last.

add to front for both linked list and array-based?

And when you say delete from last, do you mean locate array position, shift value one position towards the end of array? Or locate position, then overwrite value to be deleted with last value stored in container?

Originally Posted by ee1215

When inserting data value into unsorted linked list, where is most efficient to add the new data value? Before first element? After last element?

When Inserting into unsorted array-based list, where is most efficient position to add new data value?

Also, most efficient way to delete data value from sorted array-based list?
-locate position and shift each value one position towards beginning of array, towards end of array?

I don't know why you specify an unsorted linked list. A linked list is not inherently sorted, its data may just happen to be sorted, just like an array. It is equally efficient to add an element to the start of the linked list as it is to add it to the end of the linked list. If you already have an iterator to another position, it's also just as efficient to add an element before the element represented by that iterator. This is assuming you're working with the STL std::list, otherwise it depends on the specific implementation of a linked list you're using, as always. The following applies to linked lists in general though - there is no need to delete a different element or shuffle other elements to make room for it.

Can you clarify what you mean by "sorted array-based list"? As far as I'm concerned, if you have "array-based" data, the term "list" can only apply in the everyday sense of the word, it's not a linked list.

If you really just have a sorted array of data and want to add a new element, there's really only one appropriate way to do it. First check that there's room in the array left for you to add an element. Then use a binary search to find the first element less than or equal than the element you want to insert. Then shift all of the elements after that forward by one and insert your element after that element you found with the binary search.