Линейный список — это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически :
D1 D2 D3 ... Dn
Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0. При работе со списками на практике чаще всего приходится выполнять следующие операции:
В реальных языках программирования нет какой-либо структуры данных для представления линейного списка так, чтобы все указанные операции над ним выполнялись в одинаковой степени эффективно. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти.
Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. Рассмотрим простейшие варианты этих методов для списка с целыми значениями F=<7,10>. При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида
float d[100];   int l;
Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:
d[0]=7; d[1]=10; l=2;
Полученный список хранится в памяти согласно схеме:
l: 2
d: 7 10 .............
. [0] [1] [2] [3] ....... [98] [99]
При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель dl. Структура образующая элемент хранения, должна кроме соответствующего элемента списка содержать и указатель на соседний элемент хранения.
Описание структуры и указателя в этом случае может имееть вид:
typedef struct snd   /* структура элемента хранения   */
 { float  val;        /* элемент списка                */
   struct snd *n ;     /* указатель на элемент хранения */
 } DL;
DL *p;               /* указатель текущего элемента   */
DL *dl;              /* указатель на начало списка    */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:
p=malloc(sizeof(DL));
p->val=10;   p->n=NULL;
dl=malloc(sizeof(DL));
dl->val=7;   dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рис.1
Рис. 1.  Связное хранение линейного списка