На этом шаге мы приведем общую информацию о линейных двунаправленных списках.

Мы будем рассматривать лишь двунаправленные списки с заглавным звеном, которые имеют следующую структуру:

Рис.1. Общий вид двунаправленного списка с заглавным звеном

Здесь nsp - указатель на заглавное звено двунаправленного списка, ksp - указатель на последнее звено двунаправленного списка.

Тип каждого звена списка можно описать так:

struct node
{
  int elem;//Информационное поле.
  node *sled; // Указатель на следующее звено.
  node *pred; // Указатель на предыдущее звено.
};

Рис.2. Структура звена списка

На следующем шаге мы разберем формирование списка.