Предположим, что нам понадобилось записать последовательность чисел неопределенной длины в массив. Недолго думая мы воспользуемся массивом. В процессе работы нам вдруг понадобилось увеличить максимальное кол-во чисел в нашей последовательности. И что же мы делаем? Залазим в код проги и меняем константу отвечающую за максимальное число элементов в массиве. Логично предположение сразу поставить значение константы равное большому числу например 1000 или 10000... Но как же экономия памяти и нет гарантий, что нам когда-нибудь не понадобиться 10001 элемент. В том случае, если вы используете свое приложение то конечно можно каждый раз менять код программы, хотя это и не удобно, но если вашим приложением пользуется другой человек далекий от программирования. Что тогда?
Появляется мысль создать такой структурированный тип данных в котором можно максимальное число элементов представлять переменной и соответственно изменять в процессе работы самой программы, не меняя при этом ее кода. А что если увеличивать максимальное число элементов массива непосредственно перед добавлением элемента и уменьшать его при удалении? Хорошо звучит верно? В такой ситуации на ум приходит идея создать свой тип данных удовлетворяющий нашим требованиям.
Для того, что бы выделять дополнительную память для нового элемента и освобождать ее после удаления логично было бы воспользоваться динамической памятью. Если вы не знаете, что это такое и как ей пользоваться обратитесь к содержанию предыдущий статьи из данного раздела.
Что должен содержать каждый элемент данного списка?
1)Информационная часть.(хранящую в себе вводимую вами информацию)
2)Адресную часть.(для связи между элементами)
Можно создать список с одной адресной частью, тогда придется для обращения к нужному элементу списка, пробегать его от первого. Такой список называется однонаправленным или односвязным. Так же можно воспользоваться списком с двумя адресами, он имеет ряд приемуществ перед односвязным, например для обращения к нужному элементу списка не нужно пробегать все элементы перед ним начиная с первого. Такой список называется двунаправленным или двусвязным.
Идея реализации списков очень проста. У списка существует, как мы сказали ранее, информационная часть. И два адреса. Первый адрес назовем его previus ссылается на предыдущий элемент, второй адрес назовем его next ссылается на следующий элемент. У только что созданного списка адреса никуда не ведут. Если мы добавляем элемент после выделенного элемента, то адресная часть previus у вновь созданного элемента ссылается на уже созданный (выделенный элемент), а адресная часть next указывает на элемент следующий за выделенным.Если выделенный элемент первый, то адресная часть у вновь созданного элемента никуда не будет вести. Графическую схему списка можно увидеть на схеме.
___________________________________________________________________
Авторские права © 2000, Hunter'у Переработано 08.01.05 Ваши отклики и пожелания пишите мне
