Структура элемента списка

Структура элемента списка

Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 2.1 была предложена единая реализация связанных списков в ядре. Сегодня во всех подсистемах ядра используется официальная реализация. Для новых разработок необходимо использовать только существующий интерфейс и не нужно изобретать велосипед.

Код работы со связанными списками определен в файле <linux/list.h>, a основная структура данных имеет очень простой вид.

struct list_head {

 struct list_head *next, *prev;

};

Обратите внимание на характерное имя структуры list_head. Такое название выбрано, чтобы подчеркнуть, что списку не нужно головного элемента. Наоборот, обход списка можно начинать с любого элемента, и каждый элемент может быть головным. В связи с этим все элементы списка называются головными (list head). Указатель next указывает на следующий элемент списка, а указатель prev — на предыдущий элемент списка. Если текущий элемент списка является последним, то его указатель next указывает на первый узел. Если же текущим элементом является первый, то его указатель prev указывает на последний узел списка. Благодаря элегантной реализации связанных списков без концепции головного элемента, можно вообще не вводить понятия первого и последнего элементов.

Структура list_head сама по себе бесполезна. Ее необходимо включать в другие структуры данных.

struct my_struct {

 struct list_head list;

 unsigned long dog;

 void *cat;

};

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

struct my_struct *p;

/* выделить память для структуры my_struct ... */

p->dog = 0;

p->cat = NULL;

INIT_LIST_HEAD(&p->list);

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

struct my_struct mine = {

 .list = LIST_HEAD_INIT(mine.list),

 .dog = 0,

 .cat = NULL

};

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

static LIST_HEAD(fox);

Эта команда позволяет статически создать связанный список с именем fox.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Удаление элемента из указателя

Из книги Word 2007.Популярный самоучитель автора Краинский И

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


Трансформации элемента

Из книги Photoshop CS3: Обучающий курс автора Тимофеев Сергей Михайлович

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


Понятие опорного элемента

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Понятие опорного элемента В отличие от других проблем, решение которых предложено в этой лекции, такое тиражирование кода не связано с тем, что система типов препятствует нам в выполнении задуманного. Повторное объявление ковариантных типов разрешает их


Выбор потомков элемента

Из книги XSLT автора Хольцнер Стивен

Выбор потомков элемента В предыдущем разделе при помощи выражения "PLANET/NAME" я выбирал все элементы <NAME>, являющиеся прямыми потомками элементов <PLANET>, а при помощи выражения "PLANET/*/NAME" — все элементы <NAME>, являющиеся внуками элементов <PLANET>. Есть, однако, более


Создание меток элемента списка:

Из книги Технология XSLT автора Валиков Алексей Николаевич

Создание меток элемента списка: <fo:list-item-label> Метка для элемента списка создается элементом <fo:list-item-label>, при помощи которого можно перенумеровать или пометить дело элемента списка.К элементу <fo:list-item-label> можно применять следующие свойства:• общие свойства


Определение элемента

Из книги Программирование на языке Пролог для искусственного интеллекта автора Братко Иван


3.2.3. Добавление элемента

Из книги VBA для чайников автора Каммингс Стив

3.2.3. Добавление элемента Наиболее простой способ добавить элемент в список — это вставить его в самое начало так, чтобы он стал его новой головой. Если X — это новый элемент, а список, в который X добавляется — L, тогда результирующий список — это просто[X | L]Таким


3.2.4. Удаление элемента

Из книги Язык программирования Си для персонального компьютера автора Бочков C. О.

3.2.4. Удаление элемента Удаление элемента X из списка L можно запрограммировать в виде отношенияудалить( X, L, L1)где L1 совпадает со списком L, у которого удален элемент X. Отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:(1) Если X


Регистрация элемента управления

Из книги Программирование КПК и смартфонов на .NET Compact Framework автора Климов Александр П.

Регистрация элемента управления Чтобы зарегистрировать новый элемент управления, выясните имя файла, содержащего элемент управления, и место, где размещается этот файл на диске. После этого выполните следующее.1. Выберите Tools=References, чтобы открыть диалоговое окно со


Выбор элемента

Из книги Fiction Book Designer 3.2. Руководство по созданию книг автора

Выбор элемента Синтаксис:<выражение>.<идентификатор><выражение> -> <идентификатор>Выражение выбора элемента позволяет получить доступ к элементу структуры или объединения. Выражение имеет значение и тип выбранного элемента.В первой синтаксической форме


Использование элемента DateTimePicker

Из книги Язык Си - руководство для начинающих автора Прата Стивен

Использование элемента DateTimePicker Элемент управления DateTimePicker появился только в последней версии .NET Compact Framework 2.0. В документации MSDN есть ряд замечательных статей о том, как создать собственный элемент DateTimePicker для программ, работающих на платформе .NET Compact Framework 1.0. Стоит


Уничтожение одного элемента.

Из книги C++ для начинающих автора Липпман Стенли

Уничтожение одного элемента. 1. Кликните дважды на элемент (заголовок, параграф, стихи и т. д.).2. Нажмите иконку BookCorrector "delete" или кликните правой кнопкой мышки внутри основного окна BookDesigner и затем нажмите "delete" в появившемся


II. ОПЕРАЦИЯ КОСВЕННОГО ПОЛУЧЕНИЯ ЭЛЕМЕНТА: ->

Из книги HTML, XHTML и CSS на 100% автора Квинт Игорь

II. ОПЕРАЦИЯ КОСВЕННОГО ПОЛУЧЕНИЯ ЭЛЕМЕНТА: ->      Эта операция используется с указателем на структуру или объединение для определения элемента структуры или объединения. Предположим, что ptrstr является указателем на структуру и что member элемент, определенный


6.12.2. Поиск и извлечение элемента отображения

Из книги автора

6.12.2. Поиск и извлечение элемента отображения Оператор взятия индекса является простейшим способом извлечения элемента. Например:// mapstring,int word_count;int count = word_count[ "wrinkles" ];Однако этот способ работает так, как надо, только при условии, что запрашиваемый ключ действительно


6.13.2. Поиск элемента

Из книги автора

6.13.2. Поиск элемента Две операции, позволяющие отыскать в наборе определенное значение, – это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае.


Атрибуты элемента OBJECT

Из книги автора

Атрибуты элемента OBJECT Этот элемент позволяет встроить на сайт любой мультимедиа-объект вместе с программой обработки данного объекта. В этом разделе мы рассмотрим вопросы встраивания музыки, видео и Flash-анимации. Однако возможности элемента OBJECT намного шире: в принципе,