Указатель на следующий элемент. Последний элемент списка указывает на null. Для начала определим несколько терминов, чтобы в дальнейшем не возникло недопонимания

Развёрнутый связный список

• Развёрнутый связный список
• Основная статья: Развёрнутый связный список
• Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических элементов (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).

Позволяет значительно уменьшить расход памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при малом размере логических элементов и большом их количестве — так, односвязный список из 10 тысяч четырёхбайтных целых чисел при четырёхбайтной же адресации памяти займет 40 тысяч байт под собственно значения, плюс 40 тысяч байт под адреса, итого 80 тысяч байт; если же объединить числа в 100 массивов по 100 элементов, расход памяти на адреса упадёт до 400 байт, и суммарный расход составит 40400 байт.

• Позволяет значительно уменьшить расход памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при малом размере логических элементов и большом их количестве — так, односвязный список из 10 тысяч четырёхбайтных целых чисел при четырёхбайтной же адресации памяти займет 40 тысяч байт под собственно значения, плюс 40 тысяч байт под адреса, итого 80 тысяч байт; если же объединить числа в 100 массивов по 100 элементов, расход памяти на адреса упадёт до 400 байт, и суммарный расход составит 40400 байт.

Преимущества

• Преимущества

эффективное (за константное время) добавление и удаление элементов

размер ограничен только объёмом памяти компьютера и разрядностью указателей

динамическое добавление и удаление элементов

Недостатки

• Недостатки
• Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:
• сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке
• на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
• некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы