Why can't asynchronous threads modify an ArrayList simultaneously?

I am studying threads and came across this snippet here:

We create and start two identical java.lang.Threads and have them modify an ArrayList continuously without doing anything about this being non-thread-safe because we're just making a research.

Both threads are just instances of the same class NoteThread. In the run() method there are two operations:

1. add(item) to the list
2. remove(0) from the list.

These two operations execute in 1000 iterations.

public class Solution {
    public static void main(String[] args) {
        new NoteThread().start();
        new NoteThread().start();
    }

    public static class Note {

        public static final List<String> notes = new ArrayList<String>();

        public static void addNote(String note) {
            notes.add(0, note);
        }

        public static void removeNote(String threadName) {
            String note = notes.remove(0);
            if (note == null) {
                System.out.println("Another thread has already deleted the note");
            } else if (!note.startsWith(threadName)) {
                System.out.println("Thread [" + threadName + "] has deleted [" + note + "]");
            }
        }
    }

    public static class NoteThread extends Thread{
        @Override
        public void run() {
            for (int i = 0; i < 1000; i++) {
                Note.addNote(getName() + "-Note" + i);
                Note.removeNote(getName());
            }
        }
    }
}

Sometimes, it can throw IndexOutOfBoundsException: Index: 0, Size: -1 when the list is empty and I fail to understand how that can be possible.

An example of output:

Thread [Thread-1] has deleted [Thread-0-Note597]         
Another thread has already deleted the note         
Thread [Thread-0] has deleted [Thread-1-Note558]         
Another thread has already deleted the note         
Thread [Thread-1] has deleted [Thread-0-Note635]         
Another thread has already deleted the note         
Thread [Thread-0] has deleted [Thread-1-Note580]

We can be 100% sure, that creation of an item always takes place before it's deletion in one same thread, so I assume that it is not possible to encounter a situation when a thread wants to delete an item but fails to find one.

UPDATE: Sergey Rybalkin has very clearly explained the concept of a programmatic execution order (which I originally did not mention in the question but meant it anyway) and most importantly, he has answered the question:

If Thread 1 adds something, Thread 2 will not see the changes in some situations.

In Java, internally, each object, that we modify actually has a cached copy of it in each thread that works with it. Because the example does not do anything about thread-safety, the array, that we modify, is also cached to each of the thread. Now, that being the case, there is the possibility:

Note, this is just how I understand it, I am not an expert

1. Thread 1 copies the array into its cache.
2. Thread 2 copies the array into its cache.
3. Thread 1 adds an item to its cached array.
4. Thread 2 adds an item to its cached array.
5. Thread 1 deletes an item from its cached array.
6. Thread 1 flushes its cached array into the actual array.
7. JVM propagates the change and uploads the actual array to all of the users of that object -- to the Thread 2. So, the second thread now has the updated version of the array which is currently empty.
8. Thread 2 deletes an item from its cached array.
9. Exception: the list already empty: IndexOutOfBoundsException: Index: 0,Size: -1