Database Design - 'Lists' storage
User has >1 playlist

The Answer by Vérace is correct except that it skipped the fact that each user may have more than one playlist.

So here is a diagram of my table design. I changed one column name to "sort_order" as the name “index” in a database and in programming will cause all kinds of confusion.

Basically I suspect you are failing to notice the 'list' in 'playlist', conflating each person's list of their favoritesfrom the full list of possible choices. Each playlist is a collection of references to the desired items (songs, books, or whatever your matter is  — not clear in the Question). 



Performance

As for your performance issue when inserting a new/changed row amongst the existing rows’ sort-order  numbers, you can dramatically reduce the frequency of this chore.

Increment your sort-order value by a hundred or by a thousand or by a million rather than by one. You can insert a new row by assigning a sort-order number in between the numbers of existing rows without any shifting. You only need to do a full shift when 99 or 999 or 999,999 rows happen to have already been inserted between the incremented rows. Until then you may need to do mini-shifts when clumps appear with the in-between numbers, but on small subset of rows, &lt;100 or &lt;1,000 or &lt;1,000,000. 

If you need to show sequential 1, 2, 3… numbers to user, let the database create these numbers dynamically as part of your SELECT statement.