В этом уроке вы узнаете о связанном списке и его приложениях. Вы также узнаете, как создавать и выполнять различные операции со связанным списком.
В игре «Охота за сокровищами» вы начинаете с поиска первой подсказки. Когда вы найдете его, вместо того, чтобы найти сокровище, вы найдете местоположение следующей подсказки, а затем следующей и так далее. Вы продолжаете следовать за подсказками, пока не доберетесь до сокровища.
Связанный список похож на пример с игрой. Это серия связанных «узлов», которая содержит «адрес» следующего узла. Каждый узел может хранить точку данных, которая может быть числом, строкой или любым другим типом данных.
Представление связанного списка
Нужно начать с чего-нибудь, поэтому мы даем адресу первого узла специальное имя, называемое HEAD. Кроме того, последний узел в связанном списке может быть идентифицирован, потому что его следующая часть указывает на NULL.
Как ссылаются на другой узел?
Давайте подумаем о том, что содержит каждый узел:
- Элемент данных;
- Адрес другого узла.
Мы объединяем элемент данных и ссылку на следующий узел в структуру как:
- struct node
- {
- int data;
- struct node *next;
- };
Понимание структуры связанного узла списка является ключом к пониманию.
Каждый структурный узел имеет элемент данных и указатель на другой структурный узел. Давайте создадим простой связанный список с тремя элементами, чтобы понять, как это работает.
- /* Инициализируем узлы */
- struct node *head;
- struct node *one = NULL;
- struct node *two = NULL;
- struct node *three = NULL;
- /* Выделяем память */
- one = malloc(sizeof(struct node));
- two = malloc(sizeof(struct node));
- three = malloc(sizeof(struct node));
- /* Назначаем значения данных */
- one->data = 1;
- two->data = 2;
- three->data=3;
- /* Соединяем узлы */
- one->next = two;
- two->next = three;
- three->next = NULL;
- /* Сохраняем адрес первого узла в голове */
- head = one;
Если вы не поняли ни одной из вышеперечисленных строк, все, что вам нужно, это обновить указатели и структуры.
Всего за несколько шагов мы создали простой связанный список с тремя узлами.
Приемущество связного списка происходит от способности разорвать цепь и присоединить к ней. Например, если вы хотите поместить элемент 4 между 1 и 2, выполните следующие шаги:
- Создайте новый узел структуры и выделите для него память.
- Добавьте его значение данных как 4
- Направьте следующий указатель на узел структуры, содержащий 2 в качестве значения данных
- Измените следующий указатель «1» на узел, который мы только что создали.
Чтобы сделать что-то похожее в массиве, потребовалось бы сместить позиции всех последующих элементов.
Утилита связанного списка
Списки являются одной из самых популярных и эффективных структур данных, которые реализуются на всех языках программирования, таких как C, C ++, Python, Java и C #.
Кроме того, связанные списки - отличный способ узнать, как работают указатели. Практикуя работу со связанными списками, вы можете подготовиться к изучению более сложных структур данных, таких как графики и деревья.
