Как сделать список c
Обновлено: 07.07.2024
Связанные списки являются второй по частоте использования структурой данных после массивов.
Они являются достаточно простой реализацией динамических структур данных, использующие указатели (pointers) для реализации.
Понимание работы указателей является необходимым условием для того, что бы понять связанные списки. Кроме того – требуется понимание динамического выделения памяти и знать, что такое структуры и как ими пользоваться.
Ниже рассмотрены примеры работы с односвязными (или однонаправленными) списками.
Описание
Кратко – связанный список работает как массив, который может расти и уменьшаться при необходимости из любой точки массива.
Связаные списки имеют несколько основных преимущств:
- элементы могут быть добавлены или удалены из середины списка
- нет необходимости объявления размера при инициализации
Но имеют и недостатки:
- связанные списки не имеют возможности рандомного доступа к элементам – т.е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него
- для работы списков требуется динамическое выделение памяти и указатели, что усложняет код и может привести к утечкам памяти
- связанные списки требуют больше ресурсов операционной системы, т.к. их элементы выделяются динимачески и каждый элемент должен хранить дополнительный указатель
Реализация
Связанный список – это коллекция динамически выделяемых нод (элементов списка), организованных таким образом, что каждая нода содержит одно значение и один указатель. Указатель в ноде всегда указывает на следующий член списка. Если указатель == NULL – это последняя нода в списке.
Определение ноды
Давайте создадим ноду связанного списка:
Обратите внимание, что структура тут создаётся в виде рекурсивного дерева.
Теперь – используем ноды.
Создаём локальную переменную с именем head , которая указывает на первый элемент списка:
Полностью код сейчас будет выглядеть следующим образом:
Тут мы создали первую переменную в нашем списке, со значением 1 и значением NULL для поля next , что бы закончить наполнение списка.
Аналогично – мы можем добавить ещё один элемент списка, и ещё один, и ещё – пока не закончим список с NULL в next , например:
Получение элементов списка
Давайте добавим функцию, которая будет выводить на экран все элементы спсика.
Для этого мы используем текущий указатель, который будет отслеживать текущую ноду, а после того как её значение напечатано – указатель перемещается на следующую ноду, печатает её значение, и так по всему списку, пока не получим NULL для адреса следующей ноды:
Списки похожи на массивы, только с более широким спектром управления. В отличие от массивов в список легко добавить новый элемент в конец или вставить элемент в любое место, удалить элемент, сократив список, сортировать простым методом Sort, инвертировать последовательность элементов, добавить к списку другой список.
Метод Add
С помощью метода Add можно добавить элементы в список.
[code] List x = new List (); //Создали пустой список для хранения целых чисел x.Add(5); x.Add(27); x.Add(-6); x.Add(14); x.Add(70); x.Add(14); x.Add(178); [/code]
Таким образом в список были добавлены числа. Каждое из них теперь имеет свой индекс, начиная с 0.
| Индекс: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Значение: | 5 | 27 | -6 | 14 | 70 | 14 | 178 |
[code] List x = new List () < 5, 27, -6, 14, 70, 14, 178 >; [/code]
Чтобы получить первое число, используется индекс со значением 0 (счёт начинается с нуля)
[code] int m = x[0]; //Значение равно 5 int n = x[1]; //Значение равно 27 [/code]
А чтобы изменить значение 3-го элемента (индекс 2) на значение 100, используется такая запись:
[code] x[2] = 100; [/code]
Метод Remove
Метод RemoveAt
Свойство Count
Считает количество элементов в списке
[code] List x = new List () < 5, 27, -6, 14, 70, 14, 178 >; int n = x.Count; //7 элементов
int m = x.Count - 1; //Получить индекс последнего элемента
[/code]
Обратите внимание, что если в списке 4 элемента (0,1,2,3), то последний - это индекс №3.
Для 20 элементов последним будет 19-ый
Для 100 элементов последний - 99-ый и т.д.
Метод Insert
Метод IndexOf
Данное свойство позволяет определить, есть ли в списке элемент с этим значением.
[code] List x = new List () < 5, 27, -6, 14, 70, 14, 178 >; int a = x.IndexOf(5); //Получим 0-ую позицию
int b = x.IndexOf(-6); //Получим 2-ую позицию
int k = x.IndexOf(70); //Получим 4-ую позицию
int q = x.IndexOf(166); //Получим -1
[/code]
Метод IndexOf находит позицию элемента в списке. Если найти не удалось, будет возвращено значение -1.
Другие методы коротко в примерах
[code] List x = new List () < 5, 27, -6, 14, 70, 14, 178 >; x.Reverse(); //Получить обратный порядок элементов, т.е. 178, 14, 70, 14, -6, 27, 51
x.Sort(); //Сортировать элементы по порядку с увеличением
int a = x.Min(); //Найти наименьшее значение в списке. Получим -6
int b = x.Max(); //Найти наибольшее значение в списке. Получим 178
int c = x.Sum(); //Найти сумму элементов. Получим 302
int d = x.Average(); //Найти среднее значение чисел. Получим примерно 43,14
[/code]
Простой способ сортировать числа в порядке убывания, это сперва отсортировать из в порядке увеличения методом Sort, а потом методом Reverse перевернуть список в обратную строну.
[code] List x = new List () < 5, 27, -6, 14, 70, 14, 178 >; x.Sort(); //Сортировать элементы по порядку с увеличением
x.Reverse(); //Получить обратный порядок элементов, т.е. 178, 70, 27, 14, 14, 5, -6
[/code]
Списки содержат огромное количество методов и свойств. Их можно увидеть в IntelliSense.
Дополнительная информация о том, как вывести результат в консоли или WinForm
Первая структура данных, которую мы рассмотрим — связный список. На то есть две причины: первое — связный список используется практически везде — от ОС до игр, и второе — на его основе строится множество других структур данных.
Связный список
Основное назначение связного списка — предоставление механизма для хранения и доступа к произвольному количеству данных. Как следует из названия, это достигается связыванием данных вместе в список.
Прежде чем мы перейдем к рассмотрению связного списка, давайте вспомним, как хранятся данные в массиве.
Как показано на рисунке, данные в массиве хранятся в непрерывном участке памяти, разделенном на ячейки определенного размера. Доступ к данным в ячейках осуществляется по ссылке на их расположение — индексу.
Это отличный способ хранить данные. Большинство языков программирования позволяют так или иначе выделить память в виде массива и оперировать его содержимым. Последовательное хранение данных увеличивает производительность (data locality), позволяет легко итерироваться по содержимому и получать доступ к произвольному элементу по индексу.
Тем не менее, иногда массив — не самая подходящая структура.
Предположим, что у нашей программы следующие требования:
- Прочесть некоторое количество целых чисел из источника (метод NextValue ), пока не встретится число 0xFFFF .
- Передать считанные числа в метод ProcessItems
Поскольку в требованиях указано, что считанные числа передаются в метод ProcessItems за один раз, очевидным решение будет массив целых чисел:
У этого решения есть ряд проблем, но самая очевидная из них — что случится, если будет необходимо прочесть больше 20 значений? В данной реализации значения с 21 и далее просто проигнорируются. Можно выделить больше памяти — 200 или 2000 элементов. Можно дать пользователю возможность выбрать размер массива. Или выделить память под новый массив большего размера при заполнении старого и скопировать элементы. Но все эти решения усложняют код и бесполезно тратят память.
Нам нужна коллекция, которая позволяет добавить произвольное число элементов и перебрать их в порядке добавления. Размер коллекции должен быть неограничен, а произвольный доступ нам не нужен. Нам нужен связный список.
Прежде чем перейти к его реализации, давайте посмотрим на то, как могло бы выглядеть решение нашей задачи.
Обратите внимание: проблем, присущих первому варианту решения больше нет — мы не можем выделить недостаточно или, наоборот, слишком много памяти под массив.
Кроме того, из этого кода можно увидеть, что наш список будет принимать параметр типа и реализовывать интерфейс IEnumerable
Реализация класса LinkedList
Класс Node
В основе связного списка лежит понятие узла, или элемента (Node). Узел — это контейнер, который позволяет хранить данные и получать следующий узел.
В самом простом случае класс Node можно реализовать так:
Теперь мы можем создать примитивный связный список. Выделим память под три узла ( first , middle , last ) и соединим их последовательно:
Теперь у нас есть список из трех элементов, начиная с first и заканчивая last . Поле Next последнего узла имеет значение null , что показывает, что это последний элемент. С этим списком уже можно производить различные операции. Например, напечатать данные из каждого элемента:
Метод PrintList итерируется по элементам списка: печатает значение поля Value и переходит к следующему узлу по ссылке в поле Next .
Теперь, когда мы знаем, как должен выглядеть узел связанного списка, давайте посмотрим на пример реализации класса LinkedListNode .
Класс LinkedList
Прежде чем реализовывать наш связный список, нужно понять, как мы будем с ним работать.
Ранее мы увидели, что коллекция должна поддерживать любой тип данных, а значит, нам нужно реализовать обобщенный интерфейс.
Учитывая все вышесказанное, давайте набросаем примерный план класса, а затем заполним недостающие методы.
Метод Add
- Поведение: Добавляет элемент в конец списка.
- Сложность: O(1)
Добавление элемента в связный список производится в три этапа:
- Создать экземпляр класса LinkedListNode .
- Найти последний узел списка.
- Установить значение поля Next последнего узла списка так, чтобы оно указывало на созданный узел.
Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.
Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.
Первое, что нам необходимо сделать — добавить два приватных поля в класс LinkedList : ссылки на первый (head) и последний (tail) узлы.
Теперь мы можем добавить метод, который выполняет три необходимых шага.
Сначала мы создаем экземпляр класса LinkedListNode . Затем проверяем, является ли список пустым. Если список пуст, мы просто устанавливаем значения полей _head и _tail так, чтобы они указывали на новый узел. Этот узел в данном случае будет являться одновременно и первым, и последним в списке. Если список не пуст, узел добавляется в конец списка, а поле _tail теперь указывает на новый конец списка.
Поле Count инкрементируется при добавлении узла для того, чтобы сохранялся контракт интерфейса ICollection . Поле Count возвращает точное количество элементов списка.
Метод Remove
- Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true , если элемент был удален и false в противном случае.
- Сложность: O(n)
Основной алгоритм удаления элемента такой:
- Найти узел, который необходимо удалить.
- Изменить значение поля Next предыдущего узла так, чтобы оно указывало на узел, следующий за удаляемым.
Как всегда, основная проблема кроется в мелочах. Вот некоторые из случаев, которые необходимо предусмотреть:
- Список может быть пустым, или значение, которое мы передаем в метод может не присутствовать в списке. В этом случает список останется без изменений.
- Удаляемый узел может быть единственным в списке. В этом случае мы установим значения полей _head и _tail равными null .
- Удаляемый узел будет в начале списка. В этом случае мы записываем в _head ссылку на следующий узел.
- Удаляемый узел будет в середине списка.
- Удаляемый узел будет в конце списка. В этом случае мы записываем в _tail ссылку на предпоследний узел, а в его поле Next записываем null .
Поле Count декрементируется при удалении узла.
Метод Contains
- Поведение: Возвращает true или false в зависимости от того, присутствует ли искомый элемент в списке.
- Сложность: O(n)
Метод Contains достаточно простой. Он просматривает каждый элемент списка, от первого до последнего, и возвращает true как только найдет узел, чье значение равно переданному параметру. Если такой узел не найден, и метод дошел до конца списка, то возвращается false .
Метод GetEnumerator
- Поведение: Возвращает экземпляр IEnumerator , который позволяет итерироваться по элементам списка.
- Сложность: Получение итератора — O(1). Проход по всем элементам — O(n).
Возвращаемый итератор проходит по всему списку от первого до последнего узла и возвращает значение каждого элемента с помощью ключевого слова yield .
Метод Clear
- Поведение: Удаляет все элементы из списка.
- Сложность: O(1)
Метод CopyTo
- Поведение: Копирует содержимое списка в указанный массив, начиная с указанного индекса.
- Сложность: O(n)
Метод CopyTo проходит по списку и копирует элементы в массив с помощью присваивания. Клиент, вызывающий метод должен убедиться, что массив имеет достаточный размер для того, чтобы вместить все элементы списка.
Метод Count
- Поведение: Возвращает количество элементов списка. Возвращает 0, если список пустой.
- Сложность: O(1)
Count — поле с публичным геттером и приватным сеттером. Изменение его значения осуществляется в методах Add , Remove и Clear .
Метод IsReadOnly
- Поведение: Возвращает true , если список только для чтения.
- Сложность: O(1)
Двусвязный список
Для того, чтобы создать двусвязный список, мы должны добавить в класс LinkedListNode поле Previous , которое будет содержать ссылку на предыдущий элемент списка.
Далее мы рассмотрим только отличия в реализации односвязного и двусвязного списка.
Класс Node
Единственное изменение, которое надо внести в класс LinkedListNode — добавить поле со ссылкой на предыдущий узел.
Метод AddFirst
В то время, как односвязный список позволяет добавлять элементы только в конец, используя двусвязный список мы можем добавлять элементы как в начало, так и в конец, с помощью методов AddFirst и AddLast соответственно. Метод ICollection .Add будет вызывать AddLast для совместимости с односвязным списком.
- Поведение: Добавляет переданный элемент в начало списка.
- Сложность: O(1)
При добавлении элемента в начало списка последовательность действий примерно такая же, как и при добавлении элемента в односвязный список.
- Установить значение поля Next в новом узле так, чтобы оно указывало на бывший первый узел.
- Установить значение поля Previous в бывшем первом узле так, чтобы оно указывало на новый узел.
- Обновить поле _tail при необходимости и инкрементировать поле Count
Метод AddLast
- Поведение: Добавляет переданный элемент в конец списка.
- Сложность: O(1)
Добавление узла в конец списка легче, чем в начало. Мы просто создаем новый узел и обновляем поля _head и _tail , а затем инкрементируем поле Count .
Как было сказано ранее, ICollection .Add просто зовет AddLast .
Метод RemoveFirst
Как и метод Add , Remove будет разделен на два метода, позволяющих удалять элементы из начала и из конца списка. Метод ICollection .Remove будет также удалять элементы из начала, но теперь будет еще обновлять поля Previous в тех узлах, где это необходимо.
- Поведение: Удаляет первый элемент списка. Если список пуст, не делает ничего. Возвращает true , если элемент был удален и false в противном случае.
- Сложность: O(1)
RemoveFirst устанавливает ссылку head на второй узел списка и обнуляет поле Previous этого узла, удаляя таким образом все ссылки на предыдущий первый узел. Если список был пуст или содержал только один элемент, то поля _head и _tail становятся равны null .
Метод RemoveLast
- Поведение: Удаляет последний элемент списка. Если список пуст, не делает ничего. Возвращает true , если элемент был удален и false в противном случае.
- Сложность: O(1)
RemoveLast устанавливает значение поля _tail так, чтобы оно указывало на предпоследний элемент списка и, таким образом, удаляет последний элемент. Если список был пустым, или содержал только один элемент, то поля _head и _tail становятся равны null .
Метод Remove
- Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true , если элемент был удален и false в противном случае.
- Сложность: O(n)
Метод ICollection .Remove() почти такой же, как и в односвязном списке. Единственное отличие — теперь нам необходимо поменять значение поля Previous при удалении узла. Для того, чтобы не повторять код, этот метод зовет RemoveFirst при удалении первого узла.
Зачем нужен двусвязный список?
Итак, мы можем добавлять элементы в начало списка и в его конец. Что нам это дает? В том виде, в котором он реализован сейчас, нет особых преимуществ перед обычным односвязным списком. Но если добавить геттеры для полей head и tail , пользователь нашего списка сможет реализовать множество различных алгоритмов.
Так мы сможем итерироваться по списку вручную, в том числе от последнего элемента к первому.
В этом примере мы используем поля Tail и Previous для того, чтобы обойти список задом наперед.
Кроме того, двусвязный список позволяет легко реализовать двусвязную очередь, которая, в свою очередь, является строительным блоком для других структур данных. Мы вернемся к ней позже, в соответствующей части.
Продолжение следует
На этом мы заканчиваем разбор связных списков. В следующий раз мы подробно разберем массивы.
Односвязный список – это динамическая структура данных, элементы которой содержат ссылку на следующий элемент. Последний элемент имеет в качестве ссылки NULL. Для доступа к списку используется указатель на первый элемент.
- Работа со списком занимает гораздо меньше времени, чем с массивом
- Списки можно нарисовать на бумаге, тем самым наглядно понять механизм работы
- Списки можно определить рекурсивно
Односвязный список состоит из узлов. Каждый узел содержит в себе указатель на следующий узел (элемент списка) и хранимое значение. Узлы представляются в качестве структуры:
- Используем typedef для создания нового типа, чтобы в дальнейшем не писать слово struct.
- int value — хранимое значение, может быть любого типа.
- struct Node *next — указатель на следующий узел списка.
- Spisok — название структуры.
Инициализируем список
Мы инициализируем список отдельной функцией для того, чтобы облегчить процесс добавления звеньев в список. Другими словами, мы создаем заглавное звено списка.
Добавим узел в начало списка
Добавим узел в конец списка
- p -> next имеет значение NULL, так как указатель p расположен в конце списка. Указатель tmp ссылается на только что созданный узел, который мы хотим добавить в конец списка. Следовательно, нужно сделать так, чтобы последний элемент текущего списка ссылался на добавляемый узел (а не на NULL). Именно для этого используется строчка p -> next = tmp.
- Мы не проверяем список на пустоту, так как ранее список был инициализирован (имеется заглавное звено).
Добавим узел в определенное место списка
Удалим весь список
Удалим определенный узел списка
В данной функции используется принцип функции удаления всего списка и добавления нового элемента в n-ую позицию (конечно, никакого добавления нового узла нет, но здесь мы связываем элемент до удаляемого узла с элементом, расположенным после удаляемого узла).
Вывод элементов списка
Рассмотрим простейший способ вывода элементов списка:
В данной статье мы рассмотрели основные функции, которые предназначены для работы с односвязными списками. Если у Вас остались вопросы, то просьба писать их в комментариях.
Razer представила водонепроницаемую игровую клавиатуру
Геймерские клавиатуры прошли большое количество испытаний и к ним предъявляют высокие требования. Они должны быть прочными, удобными и функциональными. Также будет хорошо, если клавиатура будет
Google выпустил YouTube VR для Steam
Виртуальная реальность набирает все большую популярность и становится следующей крупной технологией в сфере мультимедиа и развлечений. В настоящее время на рынке продаются различные очки VR,
Читайте также: