«Я знаю парня, который знает парня, который знает другого парня». Возможно, вы слышали эту фразу Сола Гудмана из популярного телешоу «Во все тяжкие». Неудивительно, что связанные списки на самом деле работают так же, как известная фраза Гудмана. В этой статье я расскажу, что такое связанные списки, их достоинства и недостатки, их операции и способы их реализации в программе. В моем случае я буду использовать Java для реализации.

Что такое связанные списки?

В качестве метафоры представьте, что у вас есть 10 ящиков, и вы хотите соединить их друг с другом с помощью цепочки, где каждый ящик соединяется с соседним. Вы можете пометить эти поля как узлы с 1 по 10 и решить пометить строки как указатели.

Связанные списки — это линейные структуры данных, состоящие из узлов (блоков) и указателей (строк), где каждый узел указывает на следующий узел. Из фразы Гудмана мы можем сказать, что парень 1 (узел 1) знает (указывает на) парня 2 (узел 2), который знает (указывает на) другого парня 3 (узел 3), и так продолжается до последнего парня в списке, который является последним парнем. Мы можем назвать парня1 (узел1) головой, а последнего парня (парень n) — хвостом. Итак, связанный список имеет начало, которое является первым узлом, и хвост, который является последним узлом в списке.

Типы связанных списков

Связанные списки бывают нескольких типов: Связанные списки включают;

Односвязные списки, поддерживающие движение в одном направлении. в качестве метафоры мы можем думать о течении реки, которая течет только в одном направлении либо к озеру, либо к океану.

двусвязные списки, которые поддерживают движение или обход в двух направлениях. Мы можем вспомнить фразу Гудмана, где парень 1 может указывать на парня 2, а парень 2 может указывать на парня 1, что означает, что эти два парня знают друг друга, поэтому они могут «указывать» друг на друга.

Круговые связанные списки, в которых хвостовой узел указывает на головной узел.

Двойные круглые связанные списки, которые поддерживают двустороннее направление, а также указывание хвоста к голове. В качестве метафоры мы можем использовать музыкальный проигрыватель, который воспроизводит список воспроизведения песен. Последняя песня указывает на первую песню, и мы можем перейти к следующей или предыдущей песне.

Достоинства и недостатки связанных списков перед массивами

В этой статье я не буду рассказывать, что такое массивы, но по определению массив — это линейная структура данных, элементы которой хранятся последовательно, где каждый элемент имеет индекс. Мы можем думать о массиве как о лестнице или лестнице. Хотя массивы проще реализовать по сравнению со связанными списками, они могут хранить только элементы одного и того же типа данных. если вы не знакомы с этими терминами, вам не о чем беспокоиться, потому что есть много ресурсов, из которых вы можете извлечь уроки. некоторые из ресурсов, которые вы можете проверить; Программирование с Mosh, freeCodeCamp.org, Codecademy.com

Основное преимущество связанных списков по сравнению с массивами заключается в том, что они являются динамическими, поэтому могут увеличиваться и уменьшаться во время выполнения. Этот атрибут позволяет связным спискам не тратить память впустую, поскольку выделяется только необходимая память. Таким образом, мы можем резюмировать преимущества следующим образом.

Они динамичны.

У них нет потери памяти.

Хотя у связанных списков есть ряд преимуществ, они могут потреблять много памяти и не допускают обратного обхода в односвязных списках.

Операции со связанными списками

Связанные списки поддерживают четыре вида операций

Обход — переход к узлам списка.
Вставка — вставка нового узла в уже существующий связанный список.
Удаление — удаление узла из уже существующего связанного списка.

Поиск — находит определенный элемент в связанном списке.

Базовая реализация связанного списка в Java

В этой реализации мы будем использовать фразу Сола Гудмана. Предположим, что узел — это парень, который указывает на другого парня. Эта реализация предполагает, что связанный список является односвязным списком, поэтому мы будем двигаться только в одном направлении.

public class Guy{
  int data; // this guy has some information
  Guy next; // this guy knows a guy who has information
  public Guy(int data){
    this.data = data;
  }
public class Main{
  public static void main (String [] args){
    var guy1 = new Guy(1);
    var guy2 = new Guy(2);
    var guy3 = new Guy(3);
    var guy4 = new Guy(4);
    
    guy1.next = guy2;
    guy2.next = guy3;
    guy3.next = guy4;
    guy4.next = null;

Заключение

Связанный список представляет собой линейную структуру данных и может использоваться вместо массивов, когда размер данных не является фиксированным или когда данные необходимо динамически распределять или освобождать во время выполнения.

Связанные списки состоят из узлов, связанных друг с другом с помощью указателей. Каждый узел содержит данные и указатель на следующий узел в списке. Благодаря этой динамической структуре связанные списки можно легко модифицировать во время выполнения, например вставлять или удалять узлы, без необходимости перемещать большие объемы данных. Это делает их особенно полезными, когда размер данных заранее неизвестен или когда данные необходимо часто добавлять или удалять.

связанные списки могут перемещаться медленнее, чем массивы, поскольку к каждому узлу необходимо обращаться индивидуально. Они также требуют больше памяти из-за дополнительных указателей, необходимых для связи узлов.