В этом уроке вы узнаете о связанном списке и его приложениях. Вы также узнаете, как создавать и выполнять различные операции со связанным списком.
В игре «Охота за сокровищами» вы начинаете с поиска первой подсказки. Когда вы найдете его, вместо того, чтобы найти сокровище, вы найдете местоположение следующей подсказки, а затем следующей и так далее. Вы продолжаете следовать за подсказками, пока не доберетесь до сокровища.
Связанный список похож на пример с игрой. Это серия связанных «узлов», которая содержит «адрес» следующего узла. Каждый узел может хранить точку данных, которая может быть числом, строкой или любым другим типом данных.
Представление связанного списка
Нужно начать с чего-нибудь, поэтому мы даем адресу первого узла специальное имя, называемое 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 #.
Кроме того, связанные списки - отличный способ узнать, как работают указатели. Практикуя работу со связанными списками, вы можете подготовиться к изучению более сложных структур данных, таких как графики и деревья.
