Логика работы со списками

Софронов П.Н.

Этот текст предназначен для ознакомления со списками в общем плане. Понятие логики работы со списками.
Прежде чем продолжать нужно уяснить себе, что такое указатель и структура иногда еще называемое объединением. Начнем с указателей.
Все данные хранятся в памяти и характеризуются значением и адресом в памяти. Значение - совокупность данных различных размерностей. (Вполне возможна ситуация когда будет только единичный кусок данных одного типа) Адрес - число которое показывает где конкретно расположены данные. Немного отвлечемся от компьютерных терминов и попробуем провести аналогию с жизненным вариантом. К примеру у нас есть город Харьков. За центр отсчета возьмем Москву. Так сам город Харьков - это само значение. А расстояние от Москвы до Харькова - это и будет адрес.
Что такое структура или объединение. В дальнейшем будем говорить объединение, так как это более правильное определение.
Во всех языках программирования высокого уровня есть несколько основных типов данных. В каждый язык высокого уровня введена возможность объединения этих типов. Это создание нового типа на основе первых элементарных типов. По другому это можно представить опять жизненным случаем. К примеру у нас есть некоторое количество типов к примеру книга по программированию, фантастика, детективы и вестерны. Взяв эти книги (Объявить переменны представленных типов). И поставив их на полку. Мы получаем новый тип "Полка" которая включает в себя другие элементарные типы данных "книг". Доступ к книгам можно получить только через полку. Возвращаясь к баранам мы получаем объединение типов к которым можно получить доступ только через этот новый тип. В разных языках программирования - это реализуется по разному. Но принцип везде один и тот же. Разберемся в терминологии для дальнейшего более удобного изложения материала. Новый тип который мы получили после объединения называет структурой или объединением (Теперь надеюсь понятно почему последние определение я считаю более правильным). Элементарные типы данных из которых состоит структура - это поля (Или поля данных) в которых содержатся данные.
Теперь уже переходим ближе к делу.
Адрес это какое-то число которое хранится в памяти компьютера. А это означает, что адрес на самом деле - это тоже данные вполне определенного типа. А это значит, что адрес - это вполне конкретное значение но только понимается она как адрес. Отсюда можно сделать вывод: В структуре данных вполне может быть указатель на что либо.
Указатель так же может указывать не только на элементарные типы данных но и на структуру. (Ярким примером служат массивы) Указатель на структуру указывает на начало структуры. Это значит, что он указывает на первый элемент структуры. (Как указатель на массив указывает на первый элемент массива)
Однако ни кто не мешает сделать так, чтобы одно из полей было указателем. Тем более, что ни кто не мешает сделать это указателем на другую структуру. (Вместо структуры может быть любой тип данных как простой так и составной). Следую логики можно предположить, что структура (на которую указывает указатель) может в свою очередь указывать на другую структуру (нормальная ситуация когда это совершенно другая структура) и так до бесконечности, точнее пока не закончится память. Однако нам это не подходит. Но из почти любого исключения есть выход. Так для работы с указателями введен так называемый адрес в никуда. А это значит, что последнее поле структуры должно указывать в никуда. Однако есть еще способ. Можно сделать так, чтобы последний элемент структуры указывал на первый элемент. В этом случае мы получим так называемый закольцованный список.
Ну вот если вы все поняли - что я там выше написал, то вы должны получить поверхностное представление о списках. Дальше мы разберемся как с ними работать удалять, создавать и т.д. Но прежде чем работать дальше перечислим ОСНОВНЫЕ варианты организации списка. Я выделил основные, так как этих вариантов бесконечное множество. Варианты ограничиваются только воображением программиста.
Не закольцованный список - это список у которого последний элемент указывает в никуда. К примеру поезд. Каждый вагон подсоединяется к следующему (указывает на следующий), а вот электровоз не подсоединяется ни к кому (указывает в никуда).
Закольцованный список - это когда последний элемент указывает на первый. Он становится как то и не последним и не первым. Да и вообще в этой ситуации понятие первый и последний является довольно туманным. Хотя, что бы было удобней с ними работать можно, для себя выделить первый, последний (третий, пятый) элемент. Примером такого списка может служит. Женские бусы. Все они нанизаны один за одним, и составляют кольцо из элементов.
Одно направленный список - это список в котором только один элемент указывает на последующий. Как стрелочки на карте которые указывают где зарыт клад. Надеюсь Вы уловили схожесть определения с определением не закольцованного список. Однако разница есть эти стрелочки могут указывать и на начало откуда мы выходим. J
Двунаправленный список - это список в котором элемент указывает не только на последующий элемент но и на предыдущий. В случае закольцованного списка; первый элемент указывает на второй и последний, а последний на предпоследний и первый элемент списка. Жизненным примером может служить метрополитен.
Это и есть виды основных списков, однако не вздумайте ограничиваться
Только ими. Во-первых их можно как то комбинировать (К примеру двунаправленный закольцованный список), а во-вторых есть еще бесконечное количество вариантов которые удобней будет использовать для конкретных задач.
Для более наглядного понимания структуры списков - их можно рисовать в виде квадратиков, прямоугольников кружочков и т.д. и т.п. Я вам только предлагаю вариант которым пользуюсь я и который представляется мне более удобным. Поэтому вы можете изобретать велосипед и пользоваться им. Так вот рисую я сами структуры в виде прямоугольников в которых схематически отображены поля данных в виде палочки отсекающей кусок прямоугольника из которой выходит стрелка указывающая на другой прямоугольник - это указатель на другой список. Так мне более понятно, что нужно делать при работе со списками.
Теперь более конкретные примеры работы со списками. Так принципы создания, работы и удаления списков. Начнем с создания. Но прежде чем мы пойдем дальше я хочу, что бы вы уяснили себе, что это совершенно не единственный способ работы со списками. Есть еще миллион вариантов решения задач, Представленные варианты даже не претендуют на самые оптимальные алгоритмы работы.
Создание списка: Почти во всех случаях со списками работают как с динамическими элементами структур. В этом случае получается, что списки динамические. В случае если мы сразу знаем количество элементов то кто мне мешает создать массив структур с которым намного удобней работать. Правда мне некто не мешает создать динамический массив элементами которого являются структуры. Но в этом случае это уже извращение. Если вы еще этого не поняли то советую вам поработать с тем и другим и решить, что лучше.
И так мы уже третий раз переходим к созданию списка но это уже окончательно.
И так во время работы программы создаем первую структуру и настраиваем все указатели на ноль (в никуда). Однако это динамическая структура и нам надо переменную указатель которая указывала бы на эту структуру. Иначе мы не сможем к ней обращаться ведь структура динамическая. И располагается где - то в памяти. Дальше создаем второй элемент и настраиваем указатели первого элемента (последнего созданного элемента) на второй элемент (новый элемент) и т.д. и т.п. В процессе работы нам придется переходить по мере создания на последующие элементы. Для этого нужно использовать другой указатель (уже второй). Действия повторяются до логического завершения. Поля-указатели последнего элемента настраиваем на ноль (в никуда)
Работа со списками. Если у нас есть указатель который указывает на первый элемент не закольцованного однонаправленного списка. То нам необходима создать дополнительный указатель что бы не потерять начало списка. Для закольцованных и двунаправленным спискам создавать дополнительный элемент необязательно. Так как начал списка не теряется на него указывает последний элемент. Как передвигаться по списку с помощью одного указателя: Указателя присваивается значение поля-указателя которое указывает на другую структуру. Таким образом указатель настроен на другой элемент списка. Обращение к полю элемента списка аналогично обращение к полю структуры. Только надо учитывать, что вся работа идет через адреса.
Удаление списка. Если список создан не динамически то удалять его не надо. Освобождение памяти произойдет при завершении работы программы. Однако чаше работают с динамическими списками. А это означает, что при завершении работы программы, или где то в программе, нужно освободить память занятую элементами списков. Иначе данная память в дальнейшем будет потеряна для работы. Как понятно удаление указателей на список нечего не даст. Так как это только указатели или числа удаление их за собой повлечет невозможность доступа к памяти. При удалении элементов важно не потерять указатель на список. Поэтому проще для понимания на данном этапе будет использования двух указателей. Первый указывает на первые элемент второй на второй. После настройки удаляем первый элемент настраиваем указатель на уже второй элемент (бывший третий) второй указатель указывает уже на первый элемент. И так пока мы не присвоим указателю на удаленный первый элемент значение ноль.
Это все, что можно сказать по теории работы со списками не касаясь языков программирования.
Совет: Для работы со списками нужно логическое мышление и воображение. И никогда не бойтесь создавать самые дикие списки.