Каковы преимущества и недостатки связных списков по сравнению с массивами в C++

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

недостатки списков:
элемент списка требует большее количество памяти чем элемент массива (помимо значения там как минимум хранится хоть один указатель на соседний элемент) . Операция добавления элемента в коне списка выполняется дольше, т. к. для массива достаточно выполнить что-то вроде a[n++] = new_value; но при добавлении узла в список необходимо задавать значения указателей.
Но и самый большой недостаток списков - трудоемкость произвольного доступа. Элементы массива расположены последовательно, поэтому адрес элемента массива А с номером i вычисляется как А+i*size, где size - количество памяти, занимаемое одним элементом. Со списками так не выходит, чтобы обратиться к элементу списка с номером 100 надо пройти от начала списка до 100 элемента последовательно перемещаясь по ссылкам.

Достоинства:
*вставка элемента в середину списка может выполняться быстрее ( достаточно лишь изменить значение ссылок соседних элементов) , в массиве придется выполнять сдвиг (это очень трудоемко) . Вставка элемента в начало - это вообще крайний случай.
*список может хранить любое количество элементов, это количество не требуется где-либо фиксировать. Количество ограничено лишь объемом памяти компьютера и объемом памяти. которое система позволит захватить процессу. Размер массива фиксирован, хотя гляньте на std ::vector или std ::valarray - они работают примерно так - выделяется память под N элементов, и при выполнии операции над таким массивом мы получаем все преимущества массивов, до тех пор, пока размер массива не превысит N, когда размер превышен N увеличивается в несколько раз (обычно в 2), элементы из старого массива копируются в новый (при этом одна операция вставки элемента будет выполняться очень долго) а дальше опять получаем преимущества от массива пока размер не превысит N...
*операция удаления элемента из списка выполняется быстрее чем над массивом, но для этого нужно иметь указатель на элемент, если же мы имеем индекс - то элемент в списке придется сначала искать, а тут сложность N (как и сложность удаления элемента массива, впрочем) - это такой же спорный момент как и со вставкой.

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

Добавил: "Павел" очень прав про большой кусок, действительно, я забыл указать. Т. к. под каждый элемент списка память выделяется отдельно - то и не требуется наличие в памяти куска заданного размера (а элементы массива хранятся последовательно - им требуется) . Но это было актуально лет 15 назад, когда с памятью реально были проблемы, сейчас в 4Гб для пользовательских задач такие проблемы не возникают, если программист не накосячит.