Удаление последнего элемента списка

Удаление последнего элемента списка

Введение. Основные операции

О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.

Для нас односвязный список полезен тем, что

  • 1) Он очень просто устроен и все алгоритмы интуитивно понятны
  • 2) Односвязный список – хорошее упражнение для работы с указателями
  • 3) Его очень просто визаулизировать, это позволяет "в картинках" объяснить алгоритм
  • 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
  • 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.

Для простоты рассмотрим односвязный список, который хранит целочисленное значение.

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

Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.

Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо

  • 1) Выделить под него память.
  • 2) Задать ему значение
  • 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
  • 4) Перекинуть указатель head на новый узел.

1) Создаём новый узел

2) Присваиваем ему значение

3) Присваиваем указателю tmp адрес предыдущего узла

4) Присваиваем указателю head адрес нового узла

5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.

Так как указатель head изменяется, то необходимо передавать указатель на указатель.

Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.

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

Читайте также:  Вертикальная направляющая для дрели

Уже после этого можно удалить первый элемент и вернуть его значение

Не забываем, что необходимо проверить на NULL голову.

Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.

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

Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.

Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL

Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый

Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.

Читайте также:  Где найти trade url в стиме

Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.

Удаление последнего элемента и вставка в конец имеют сложность O(n).

Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:

Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент

Покажем на рисунке последовательность действий

После этого делаем так, чтобы новый элемент ссылался на следующий после n-го

Определение

Удаляет первое вхождение указанного объекта из коллекции List . Removes the first occurrence of a specific object from the List .

Параметры

Объект, который необходимо удалить из коллекции List . The object to remove from the List . Для ссылочных типов допускается значение null . The value can be null for reference types.

Возвращаемое значение

Значение true , если элемент item успешно удален, в противном случае — значение false . true if item is successfully removed; otherwise, false . Этот метод также возвращает false , если элемент item не найден в коллекции List . This method also returns false if item was not found in the List .

Реализации

Примеры

В следующем примере показано, как добавить, удалить и вставить простой бизнес-объект в List . The following example demonstrates how to add, remove, and insert a simple business object in a List .

В следующем примере демонстрируется Remove метод. The following example demonstrates Remove method. Для добавления, вставки и поиска в списке используются несколько свойств и методов универсального класса List . Several properties and methods of the List generic class are used to add, insert, and search the list. После выполнения этих операций список будет содержать дубликат. After these operations, the list contains a duplicate. Метод Remove используется для удаления первого экземпляра повторяющегося элемента и отображения содержимого. The Remove method is used to remove the first instance of the duplicate item, and the contents are displayed. Метод Remove всегда удаляет первый обнаруженный экземпляр. The Remove method always removes the first instance it encounters.

Читайте также:  Как убрать автозапуск яндекс браузера

Комментарии

Если тип T реализует IEquatable универсальный интерфейс, то функция сравнения на равенство является методом Equals этого интерфейса. в противном случае компаратор проверки на равенство по умолчанию Object.Equals. If type T implements the IEquatable generic interface, the equality comparer is the Equals method of that interface; otherwise, the default equality comparer is Object.Equals.

Этот метод выполняет линейный поиск. Таким образом, этот метод является операцией O (n), где n — Count. This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

Есть ли лучший способ удалить последние N элементов списка.

если вы хотите удалить последние n элементов, другими словами, сохраните первые len-n элементы:

Примечание. Это не операция с памятью. Это создаст копию.

Работает для n >= 1

Как правильно говорит Vincenzooo, pythonic lst[:-n] не работает, когда n==0 .

Для всех n>=0 выполняется следующее:

Мне нравится это решение, потому что оно также читается на английском языке: "возвратите срез, опуская последние n элементов или ни один (если ни один не должен быть опущен)".

Это решение работает из-за следующего:

  • x or y оценивается как x , когда x логически истинно (например, если это не 0 , "" , False , None . ) и y в противном случае. Итак, -n or None -n , когда n!=0 и None , когда n==0 .
  • При нарезке None эквивалентно опусканию значения, поэтому lst[:None] совпадает с lst[:] (см. здесь).

Я вижу, что это было задано давно, но ни один из ответов не сделал это для меня; что, если мы хотим получить список без последних элементов N, но сохраним исходный: вы просто делаете list[:-n] . Если вам нужно обрабатывать случаи, когда n может равняться 0 , вы делаете list[:-n or None] .

Ссылка на основную публикацию
Телефон самсунг с хорошей камерой недорогой
Если вы ищете лучший телефон Samsung, тогда рейтинг поможет разобраться в их различиях. Посмотрите какой смартфон лучшие купить из всех...
Стилус для графического планшета своими руками
Если кто-то желает сделать стилус для планшета в домашних условиях, это вовсе не означает, что человеку нечем заняться, или у...
Стили линий в автокаде
Типы линий для AutoCAD можно создавать самостоятельно и для этого не надо быть гением или программистом. Как создать линию в...
Телефон перестал заряжаться быстрой зарядкой
Наверняка многие сталкивались с тем, что смартфон ни с того ни с сего перестаёт заряжаться. Другая распространённая беда — слишком...
Adblock detector