Типы связанного списка - односвязные, двусвязные и круговой

Content

Существует три распространенных типа связанного списка.

  • Единственный связанный список
  • Двусвязный список
  • Круговой связанный список
Единственный связанный список

Это самый распространенный. Каждый узел имеет данные и указатель на следующий узел.

Где адрес первого узла специальное имя, называемое HEAD.
На последний узел в связанном списке указывает NULL.

Узел представлен как:

struct node {
    int data;
    struct node *next;
}

Трехэлементный односвязный список может быть создан как:

/* Инициализируем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Назначаем значения данных */
one->data = 1;
two->data = 2;
three->data = 3;

/* Соединяем узлы */
one->next = two;
two->next = three;
three->next = NULL;

/* Сохраняем адрес первого узла в голове */
head = one;
Двусвязный список

Мы добавляем указатель на предыдущий узел в двусвязном списке. Таким образом, мы можем идти в любом направлении: вперед (next) или назад (prev).

Узел представлен как:

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

Двусвязный список из трех участников может быть создан как:

/* Инициализируем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Назначаем значения данных */
one->data = 1;
two->data = 2;
three->data = 3;

/* Соединяем узлы */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Сохраняем адрес первого узла в голове */
head = one;
Круговой связанный список

Круговой связанный список - это вариант связанного списка, в котором последний элемент связан с первым элементом. Это образует круговую петлю.

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

  • Для односвязного списка указатель next последнего элемента указывает на первый элемент;
  • В двусвязном списке указатель prev первого элемента также указывает на последний элемент.

Круговой односвязный список из трех членов может быть создан как:

/* Инициализируем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Назначаем значения данных */
one->data = 1;
two->data = 2;
three->data = 3;

/* Соединяем узлы */
one->next = two;
two->next = three;
three->next = one;

/* Сохраняем адрес первого узла в голове */
head = one;
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
June 6, 2020, 12:20 a.m.
Aleksej

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:60points,
  • Rating points-1
June 6, 2020, 12:15 a.m.
Aleksej

C++ - Test 001. The first program and data types

  • Result:53points,
  • Rating points-4
V
June 5, 2020, 5:47 p.m.
Vladzo

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
June 5, 2020, 11:52 a.m.
progammist

Распознавание изображений на Python с помощью TensorFlow и Keras

Огромное спасибо за метериал, по-больше бы подобных статей (с подробным описанием работы и примерами применения) на тему современных технологий. Вопрос поразмышлять. На текущий момент реал…
June 5, 2020, 2:39 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

По-моему, смысла в этом нет особого. Если делегат будет игнорировать настройки таблицы, то это приведёт ещё к большему непониманию, что вообще происходит, для программиста, который после вас буд…
June 5, 2020, 2:34 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Сижу, размышляю: можно ли переписать делегата так, чтобы независимо от настроек строк выделялись строки?
June 5, 2020, 2:31 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Понятно. Я не обратил внимания на то, что там было в старом коде по настройкам строк :)
Now discuss on the forum
s
June 6, 2020, 2:54 a.m.
shuric

Qt/C++ Определение положения курсора над действие(кнопкой) в QToolBar

Доброго дня. Возник вопрос - как можно определить что курсор находится над определенным действием(кнопкой) в qtoolbar ? mainwindow.cpp MainWindow::MainWi…
s
June 6, 2020, 1:45 a.m.
shuric

Qt/C++ особенности QProxyStyle

Да, Вы правы. Код был скопирован с сайта (уже не помню с какого), но решил пойти по пути более легком. Пришлось переписать - кому интересно: использовал stackedWidget для пе…
June 6, 2020, 12:08 a.m.
Aleksej

Посоветуйте новичку (базы данных и Qt, что учить)

Блин, а я недавно купил Шлее Qt 5.10 :( С детства хотел стать программистом, баловался Паскалем, писал простенькие программки на Delphi, создавал движок на php, изучал C (забросил и перешел на п…
June 5, 2020, 2:09 p.m.
IscanderChe

QPlainTextEdit настройка цвета фона

Вечер добрый. Пытаюсь настроить цвет фона QPlainTextEdit следующим образом: CodeEditor::CodeEditor(QWidget *parent) : QPlainTextEdit(parent){ ... QPalette::ColorRole role = bac…
June 5, 2020, 7:13 a.m.
IscanderChe

Фильтр для QtableView sql

Добрый день. Для такой фильтрации необходимо использовать QSortFilterProxyModel. В оффдоках есть хороший пример.
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB