Линейный список представляет собой последовательность n≥0 узлов Х [1], X[2], … , X[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если n>0 и X[1] является первым узлом, а X[n] – последним, то k –й узел следует за X[k-1] и предшествует узлу X[k+1] для всех 1< k
• Линейные односвязные списки – единственное адресное поле содержит адрес следующего элемента. Если следующий элемент отсутствует, то в адресное поле заносят константу nil;
• Линейные двусвязные списки – каждый элемент содержит адреса предыдущего и по-следующих элементов, соответственно, первый элемент в качестве адреса предыдущего, а последний – в качестве адреса следующего элемента содержит nil.
Связный граф, в котором каждый узел имеет не более двух рёбер.