Связанный список — это трудная тема для многих из нас, начинающих мир программирования. Это данные линейной структуры, но вы можете думать о коллекции объектов, и каждый объект указывает на следующий объект.
Пример: у нас есть объект A, объект B и объект C, они используют место в памяти, но они не связаны. Теперь мы можем понять, почему я сказал, что у нас есть объект, потому что этот объект должен сохранять некоторые атрибуты.
Каждый объект будет сохранять данные, а следующий объект, давайте посмотрим:
Объект A [100, Объект B] теперь, если мы обращаемся к объекту A, мы можем получить значение. Поскольку объект B уже сохранен, мы также можем получить следующее значение и объект.
Объект B [200, Объект C] отсюда мы получаем следующий Объект C.
Объект C [300, null] отсюда мы знаем значение последнего объекта.
Как мы узнаем, что мы обогащаем последний объект?
Если следующий объект текущего объекта имеет значение null, это означает, что мы обогащаем последний объект в нашем списке. Существует множество реализаций со связанным списком. Вы можете обнаружить, что первый объект указывает на null или первый и последний объекты указывают друг на друга.
Давайте сделаем пример:
У вас есть простая очередь в супермаркете. Вы знаете, что первый человек в очереди — это тот, кто первым получает помощь. Второй человек будет позади первого человека и так далее.
Как реализовать последний сценарий с помощью связанного списка?
Я собираюсь использовать Ruby для работы над примером:
Мы собираемся создать класс с именем Person (обычно имя класса — Node, чтобы использовать его в любом объекте. Но для этого примера я решил назвать его Person). Давайте рассмотрим код построчно:
attr_accesor :имя, :следующий_человек. Здесь мы устанавливаем геттеры и сеттеры для name и next_person.
инициализировать (имя, next_person = nil). Здесь мы инициализируем наш класс Person двумя переменными. Мы также говорим, что next_person может начинаться как nil. Наконец, мы устанавливаем переменные экземпляра, используя @. Теперь мы можем быть уверены, что сможем получить доступ к этим переменным из любого метода в классе.
Следующий класс, который нам нужен, — это класс, который управляет нашей очередью людей. Мы создаем класс и инициализируем две переменные, которые будут доступны в любом методе.
@first — первый человек в очереди.
@last — последний человек в очереди.
Сейчас я объясню, как шаг за шагом добавлять человека в очередь.
Первый сценарий — это когда у нас нет ни одного человека в очереди, и мы получаем первого. В этом конкретном случае нам нужно установить имя первого человека, поэтому я перехожу к @first.name = name. Я также установил @last.name = name, потому что в очереди, если у вас есть один человек, последний и первый человек совпадают.
Но как насчет следующего человека; потому что у нас есть один человек в очереди @first.next_person остается нулевым.
Посмотрим, что получилось у второго человека:
Второй сценарий — когда у нас в очереди 2 человека, откуда мы можем это знать? Нам нужно проверить, равен ли @first.next_person ноль. Если он равен нулю, это означает, что мы пытаемся добавить в очередь второго человека.
@last.name = имя. Мы установили это так, потому что знаем, что у нас два человека. Первый будет иметь имя первого человека, а последний будет иметь имя второго человека.
@first.next_person = @last, здесь мы соединяем двух наших людей. Мы говорим, что первое лицо имеет связь со вторым лицом, которое в данном случае является последним.
Наш последний сценарий — это когда у нас в очереди более 2 человек.
Человек встает в очередь, а там больше 2 человек. Во-первых, нам нужно сохранить информацию о последнем человеке в очереди. Затем мы можем добавить нового человека в очередь как последнего человека в очереди. Давайте посмотрим это шаг за шагом с кодом:
person = @last здесь мы сохраняем информацию о последнем человеке лично. Я использую «человек», потому что это любой человек между первым и последним человеком в очереди. Я сохраняю его, потому что мне нужно сохранить связь между людьми в очереди.
@last = Person.new(имя), потому что мы уже сохранили информацию о последнем человеке. Теперь мы можем установить нового последнего человека в очереди.
person.next_person = @последний. Здесь мы восстанавливаем связь. Человек, который был предыдущим последним человеком, теперь указывает на нового последнего человека.
Я собираюсь создать еще один метод для удаления человека из очереди. Так как мы работаем с очередью в супермаркете. Мы знаем, что первый человек в очереди получит помощь. И он будет первым, кто закончит процесс.
Для нашей поп-функции у нас есть 3 сценария:
Первый сценарий @first.name равен нулю. Это означает, что у нас нет никого в очереди, поэтому мы печатаем «Пустая очередь».
Второй сценарий @first.next_person равен нулю. Это означает, что у нас есть один человек в очереди. Мы также знаем, что если в очереди есть один человек, то последний человек является первым человеком. Вот почему мы устанавливаем @first.name и @last.name равными нулю.
Последний сценарий прост. Нам нужно установить фактическое первое лицо в качестве следующего человека, потому что первое лицо уже подключено к нему. Делаем @first = @first.next_person.
Переменная name предназначена для того, чтобы знать имя человека, которого мы удаляем из очереди.
Вы можете использовать больше методов, например, удалить элемент по определенному индексу и многое другое. С приведенными выше реализациями легко реализовать другие реализации.
