Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).
В программе двусвязный список можно реализовать с помощью описаний:
typedef struct ndd
  { float val;      /* значение элемента                */
    struct ndd * n; /* указатель на следующий элемент   */
    struct ndd * m; /* указатель на предыдующий элемент */
  } NDD;
NDD * dl, * p, * r;

Графическая интерпретация метода связанного хранения списка F=< 2,5,7,1 > как списка с двумя связями приведена на рис.1.
Рис. 1.  Схема хранения двусвязного списка.
Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:
r=malloc(NDD);
r->val=new;
r->n=p->n;
(p->n)->m=r;
p->=r;
Удаление элемента, следующего за узлом, на который указывает p
p->n=r;
p->n=(p->n)->n;
( (p->n)->n )->m=p;
free(r);
Связанное хранение линейного списка называется циклическим списком, если его последний указывает на первый элемент, а указатель dl — на последний элемент списка.
Схема циклического хранение списка F=< 2,5,7,1 > приведена на рис.2.
Рис. 2.  Схема циклического хранения списка.
При решении конкретных задач могут возникать разные виды связанного хранения. Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1 по возрастанию. Составить процедуру для формирования Fn в связанном хранении и возвращения указателя на его начало.
При решении задачи в каждый момент времени имеем упорядоченный список Fi и при вводе элемента Bi+1 вставляем его в нужное место списка Fi, получая упорядоченный список Fi+1. Здесь возможны три варианта: в списке нет элементов; число вставляется в начало списка; число вставляется в конец списка. Чтобы унифицировать все возможные варианты, начальный список организуем как связанный список из двух элементов <0,1000>. Рассмотрим программу решения поставленной задачи, в которой указатели dl, r, p, v имеют следующее значение: dl указывает начало списка; p, v — два соседних узла; r фиксирует узел, содержащий очередное введенное значение in.
#include
#include
typedef struct str1
  { float val;
    struct str1 *n; }  ND;
main()
  { ND *arrange(void);
    ND *p;
    p=arrange();
    while(p!=NULL)
      {
        printf("\n %f ",p->val);
        p=p->n;
      }
  }
ND *arrange() /*   формирование упорядоченного списка */
  {  ND *dl, *r, *p, *v;
     float in=1;
     char *is;
     dl=malloc(sizeof(ND));
     dl->val=0;                  /*  первый элемент     */
     dl->n=r=malloc(sizeof(ND));
     r->val=10000; r->n=NULL;    /*  последний элемент  */
     while(1)
       {
         scanf(" %s",is);
         if(* is=='q') break;
         in=atof(is);
         r=malloc(sizeof(ND));
         r->val=in;
         p=dl;
         v=p->n;
         while(v->valn);
          {
            r->n=v;
            p->n=r;
          }
        }
    return(dl);
  }