Динамические структуры данных. Алексеев А.Ю - 4 стр.

                                 1. СПИСКИ

                1.1. Линейный однонаправленный список

   Линейный список представляет собой способ организации последователь-
ности однотипных элементов, при котором, каждый элемент, кроме первого,
имеет одного предшественника (предыдущий элемент) и каждый элемент,
кроме последнего, имеет одного преемника (следующий элемент). Доступ
к каждому элементу списка можно получить, последовательно продвигаясь по
списку от элемента к элементу. Если это продвижение осуществляется только
в одном направлении, то говорят о линейном однонаправленном списке
(Л1–списке). Если можно перемещаться по списку, как в направлении его
конца, так и к его началу, то говорят о линейном двунаправленном списке
(Л2–списке). Схематично линейный список можно представлять, например,
так, как это изображено на рис. 1.1.

            Начало списка                                Конец списка




               Первый элемент                    Последний элемент
              Рис. 1.1. Схематичное (модельное) представление списка

   Операции добавления, удаления или замены элементов списка могут про-
изводиться в любом месте списка по мере продвижения по нему.
   Простейший способ реализации линейного списка основан на его пред-
ставлении одномерным массивом так, что соседние элементы списка записаны
в соседние элементы массива (так называемая непрерывная реализация на базе
вектора). Очевидным недостатком такой реализации является необходимость
сдвига элементов массива при выполнении операций вставки и удаления эле-
мента списка. Иначе говоря, операции удаления и вставки при такой реализа-
ции являются массовыми, т.е. требующими выполнения элементарных опера-
ций в количестве, в среднем пропорциональном числу элементов списка.
   От этого недостатка свободно так называемое цепное (или ссылочное) пред-
ставление Л1–списка. Здесь каждый элемент списка представляется звеном в це-
пи, состоящим из информационного поля Info, содержащего собственно эле-
мент списка, и поля Next, куда записывается ссылка на следующий элемент.
   Схематично отдельное звено списка изображено на рис. 1.2,а. Пустую
ссылку обычно обозначают символом nil и изображают, например, как на
рис. 1.2,б. Тогда последний элемент списка будет изображен так, как показано
на рис. 1.2,в. В качестве примера на рис. 1.3 изображен в этих обозначениях
список из элементов a,b,c,d.
                                        4