res2001

Алгоритмы это классно, книга Кормена закроет большую часть вопросов по ним.
По ассемблеру (в т.ч. и для АРМ) есть несколько толстых красивых книг у издательства ДМК пресс, можешь поискать у них на сайте. Не читал. Думаю, что не стоит пока туда лезть, разве что очень-очень руки чешутся.

Из того, что реально необходимо в большинстве проектов:
1. параллельное программирование: Энтони Уильмс C++. Практика многопоточного программирования
2. сетевое программирование: Уильям Стивенс UNIX: Разработка сетевых приложений
3. Разработка под линукс: Керриск Майкл Linux API. Исчерпывающее руководство
4. базы данных. Тут очень много книг и много вариантов так что советовать ничего не буду, но стоит освоить работу хотя бы с одной реляционной базой данных и знать SQL. Рекомендую смотреть в сторону Postgres.

Видимо планируется хранить список на медленном устройстве хранения (на диске). Тогда такое построение связного списка вполне оправдано - за одно чтение можно прочитать несколько блоков данных.
Возможно примерно таким же способом хранятся таблицы в СУБД. Называться это может по разному.
Так же в СУБД часто применяют b-tree для хранения индексов, в этом дереве то же хранится несколько элементов данных в одном узле.

Потому что, чтоб вставить элемент в массив в произвольное место, надо все остальные элементы сдвинуть на одну позицию.
Для вставки в список вы должны передать операции ссылку на элемент перед которым (или после которого) должен быть вставлен новый элемент. Имея такую ссылку операция происходит за константное количество шагов.
Такая же ситуация и с операцией удаления произвольного элемента.

Просто размышление.
Логика подсказывает, что такой подход применяется, когда нужно не просто обойти все дерево как-нибудь, а обойти в порядке сортировки дерева (или в обратном порядке).

Конечно вы можете применять такое и с деревьями с большим количеством узлов. Но это будет уже, скорее всего, не симметричный обход, потому что симметрей чисто визуально тут уже и не пахнет, но алгоритмическе все то же самое. В некоторых конфигурациях деревьев с количеством дочерних узлов больше 2, обход вполне может остаться симметричным (когда дочерних узлов четное количество и родителя проверяете по середине).

На каком именно этапе проверять родителя в таком случае зависит от того как сортируются потомки относительно родителя в данном конкретном случае. Т.е. в бинарном дереве левый потомок меньше родителя, а правый больше - это правило и создает упорядоченность при обходе. Если узлов больше 2, то нужно определить аналогичное правило упорядоченности для потомков относительно родителя. в соответствии с этим правилом и совершать обход.

Вы описываете типичную ситуацию при работе с базами данных.
Обычно применяются 2 стратегии:
1. ничего не делаем, побеждает последний записавший данные. Запись, конечно, должна быть атомарной, т.е. если 2 пользователя одновременно пишут, то в итоге должны быть записанны данные либо первого пользователя либо второго, но не нечто среднее.
2. блокировка доступа на изменение, в этом случае описанная ситуация просто не возникнет.
Эти же подходы вполне применимы и в вашем случае.
Оба подхода имеют свои достоинства и недостатки, нужно оценить вашу конкретную ситуацию и выбрать более подходящий подход.

Виноваты накладные расходы.
В traditional_way они минимальны.
Замените лямбды вычислением промежуточного массива содержащего abs(a-x) в остальных случаях и получите дополнительный прирост производительности.

По моему речь о характеристиках ЦП, влияющих на производительность, например, тактовая частота, размер кэша и проч.
Игнорировать их можно потому, что алгоритм с логарифмической сложностью будет выполняться быстрее на более медленном устройстве - как раз описанный случай. Для каждых двух разных аппаратных конфигураций и алгоритмов размер входных данных, при котором алгоритм с логарифмической сложностью будет выигрывать у линейного, будет разным и его нужно подбирать опытным путем.
Просто примите к сведению и продолжайте изучение, это не то на чем требуется заострять внимание.

В практических задачах часто оптимизируют алгоритмы для того что бы можно было выполнять задачу на более слабом устройстве, при этом имеют конечную цель снизить энергопотребление устройства. Актуально для разного рода встроенных решений.