Линейный связный список - последовательность ячеек, связанных в некотором порядке. Каждая ячейка имеет два поля: в одном из них находится элемент списка, в другом – указатель, сообщающий положение следующей ячейки.

Пример 1

позиция = 1 2 3 4 5 6 7 8 9  [i]
A[i]    = x b x d a x c x x
Next[i] = x 7 x 0 2 x 4 x x
IP = 5
признак конца = 0

A[3] <- e
Next[3] <- Next[2]
Next[2] <- 3

Если хотим удалить символ 7, то
Next[2] <- Next[7]
Двусвязные списки

Двусвязные (двунаправленные) линейные списки - линейные списки, записи которых связаны посредством пары указателей, хранимых в адресных полях записей списка. Логическую структуру двусвязного списка иллюстрирует следующая диаграмма
Рис. 1.  
В каждой записи поле prev содержит адрес предыдущей записи, поле - next - адрес последующей записи, а data обозначает информационные поля. Для доступа к списку могут быть использованы адреса начальной (start), конечной (end) и текущей (this) записей списка. Индикатором начальной и конечной записей являются нулевые (NULL) значения адресных полей Start и end, соответственно.

Любая функциональная обработка списка строится на основе процедур модификации и просмотра. Процедуры модификации списка должны обеспечивать вставки и исключение записей списка. Частным случаем процедур вставки и исключения являются процедуры добавить и удалить начальную или конечную запись списка. Следующая диаграмма иллюстрирует процедуру вставки новой записи Z после записи Y (или перед записью X)
Рис. 2.  
Следующая диаграмма иллюстрирует процедуру исключения текущей записи this.
Рис. 3.  
Процедуры просмотра списка должны обеспечивать смещение указателя текущей записи (this) на требуемое число позиций в направлении начала или конца списка, как показано на следующей диаграмме.
Рис. 4.  
Частным случаем смещения указателя текущей записи является переход к соседней предыдущей или последующей записи (смещение на 1 позицию), а также нефиксированный переход к начальной или конечной записям списка, который позволяет принудительно инициализировать указатели start и end после модификаций в начале и конце списка.