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

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

Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 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.

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

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

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

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

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

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

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


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

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

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


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

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

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


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

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

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


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

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

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


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

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

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


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

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

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 в противном случае.


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

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

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


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

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

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


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

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

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


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

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

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


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

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

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