Addition or deletion of elements of a dynamic array

Question

Is there any consensus among programmers (or a common convention) on the "right way" to deal with the addition or deletion of one or more elements of a dynamic (mutable) array at runtime while gracefully handling changes to the references to the other elements?

For example within a loop in JavaScript, to remove some elements

• does one use delete() to replace the items with 'undefined' while keeping the length of the array unchanged, so that references to the other elements have not changed?
• Or do you slice() or splice(x,1) the array and then somehow update all current references?
• Or do you make a copy of the array at the beginning of a function call, for example, then use delete() while still in that function, then at the end use filter() to remove the undefined slots and then write that back out to the original object?

What if more than one user or thread is trying to access this array simultaneously? Is the only choice a locking mechanism for writes? Or perhaps the answer is simply, "it just depends on what you want/need it to do".

Thanks in advance for your opinions.

Answer 1

The consensus I am aware of (I only know a couple languages, not all of them) is as follows:

If the use of the array is somewhat complex, such as in the case of multithreaded access to the array, the array is put in a wrapper class. The wrapper class then exposes the minimum necessary amount of operations that can be performed on the array.

If the use is simple and the array is used synchronously, then it doesn't matter as long as the code has a good balance in terms of performance and being readable. Where that balance lies depends on the requirements, but it's usually "As readable as possible while being fast enough".

Answer 2

There are multiple ways to deal with this and each has benefits and drawbacks. You need to pick the right approach depending on how the data structure should work.

1. Use single-threaded access. This removes a large class of problems but is not always feasible. Specifically, if you save array offsets, iterators, etc. they can be invalidated even by a single thread. E.g. save off index 7, then delete index 4, now the element that was at index 7 is now at 6. This can be fixed by refactoring the code to work better and more consistently, such as by not searching for the element until you need it.

2. Control access to the array using a locking mechanism. Want to access or modify the array? Use a semaphore or other mechanism to ensure only one thread can access it. This goes a long way toward ensuring safety, but not entirely. It has the same potential single-threaded bugs as the previous point.

3. Wrap the array in a thread-safe data structure. One example is a copy-on-write list. This ensures that writes by one thread (or reference) are only seen by that same object reference. The benefit is two processes modifying the same structure do not step on each others' toes, with the obvious drawback that different threads cannot truly share data because once a thread modifies the list, it receives its own copy that is now out of sync with other threads.

4. Use a different data structure. For example, a hash table that happens to use integers as keys operates similar to an array, but does not have the "I deleted or inserted and shifted everything" problem. This may or may not be appropriate for a given task, but may be worth considering. This is also a good alternative if you need a sparse array.

Answer 3

Only convention I know for situations where you have a lot of inserting and deleting in a list is to not use an array.

Use a linked list or a binary tree instead. These data-structures are made for inserting and deleting.