Список

Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

Содержание

Односвязный список [ править ]

Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

Двусвязный список [ править ]

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

XOR-связный список [ править ]

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

Циклический список [ править ]

Первый элемент является следующим для последнего элемента списка.

Операции на списке [ править ]

Рассмотрим базовые операции на примере односвязного списка.

Вставка [ править ]

Очевиден случай, когда необходимо добавить элемент ( [math]newHead[/math] ) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

Поиск [ править ]

Удаление [ править ]

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

Удаление элемента после заданного ( [math]thisElement[/math] ) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.

Поиск цикла в списке [ править ]

Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда «Черепаха и заяц». Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.

Поиск длины хвоста в списке с циклом [ править ]

Наивные реализации [ править ]

Реализация за [math]O(n^2)[/math] [ править ]

Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от [math]pointMeeting[/math] вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит [math]pointMeeting[/math] снова, то точку окончания (начала) хвоста нашли.

Реализация за [math]O(n \log n)[/math] [ править ]

Эффективная реализация [ править ]

Доказательство корректности алгоритма [ править ]

[math]f_1(n) = L + (n-L) \bmod N[/math]

[math]f_2(n) = L + (2n-L) \bmod N[/math]

[math]Q = L + (1-k) N[/math]

Пусть [math]L = p N + M, 0 \leqslant M \lt N[/math]

[math]L \lt k N \leqslant L + N[/math]

[math]pN + M \lt kN \leqslant (p+1)N + M[/math] откуда [math]k = p + 1[/math]

Задача про обращение списка [ править ]

Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий. Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать [math]NULL[/math] ), а возвращает указатель на новую голову списка.

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели [math]next[/math] изменят свое направление, не нарушив связности самого списка.

Источник

Односвязные списки

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

Рис. 22.2 Односвязный список

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

Несмотря на то, что созданный с помощью функции slstore() список можно отсортировать отдельной операцией уже после его создания, легче сразу создавать упорядоченный список, вставляя каждый новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.

При вставке элемента в односвязный список может возникнуть одна из трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним. На рис. 22.3 показана схема изменения ссылок в каждом случае.

Последовательный перебор элементов связанного списка осуществляется очень просто: начать с начала и следовать указателям. Обычно фрагмент кода перебора настолько мал, что его вставляют в другую процедуру — например, функцию поиска, удаления или отображения содержимого. Так, приведенная ниже функция выводит на экран все имена из списка рассылки:

Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля name :

Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента. На рис. 22.4 показаны все три операции.

Рис. 22.4. Удаление элемента из односвязного списка

У односвязных списков есть один большой недостаток: односвязный список невозможно прочитать в обратном направлении. По этой причине обычно применяются двусвязные списки.

[1] Не забывайте, что у односвязного списка, как и у веревки, два конца: начало и конец.

Источник

Односвязный линейный список

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры

Основные действия, производимые над элементами ОЛС:

Инициализация ОЛС

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

Добавление узла в ОЛС

Функция добавления узла в список принимает два аргумента:

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛС включает в себя следующие этапы:

Таким образом, функция добавления узла в ОЛС имеет вид:

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЛС

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

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЛС включает в себя следующие этапы:

Удаление корня списка

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

Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

При замене соседних узлов переустановка указателей выглядит следующим образом:

При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:

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

Функция взаимообмена узлов списка выглядит следующим образом:

Комментариев к записи: 77

using namespace std;
struct NODE <
char value;
struct NODE* next;
>;

struct DbCircleList <
size_t size;
struct NODE* head;
>;

void addNode(DbCircleList* list, char elem)
<
NODE* newElem = new NODE;
newElem->value = elem;
if (list->size == 0)
<
list->head = newElem;
list->head->next = list->head;
>
else
<
struct NODE* temp;
temp = list->head;
list->head = newElem;
newElem->next = temp;
>
++list->size;
>

void printList(DbCircleList* list)
<
NODE* tmp = list->head;
cout «List values: » endl;
for ( int i = 0; i size; ++i)
<
cout «Value: » tmp->value endl;
tmp = tmp->next;
>
>

int main()
<
DbCircleList* list = new DbCircleList;
list->size = 0;
list->head = NULL ;
DbCircleList* list1 = new DbCircleList;
list1->size = 0;
list1->head = NULL ;
DbCircleList* list2 = new DbCircleList;
list2->size = 0;
list2->head = NULL ;

addNode(list, ‘b’);
addNode(list, ‘b’);
addNode(list, ‘3’);
addNode(list, ‘c’);
addNode(list, ‘3’);
addNode(list, ‘7’);

delete list;
delete list1;
delete list2;
return 0;
>

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include

struct book
<
char name[30];
char author[30];
int num_page;
int year;
char style[30];
struct book* next;
>;
struct book* poperedbook, * element, * pershiy, * novii, * ostan;

void Stvorutu( void )
<
element = ( struct book*)malloc( sizeof ( struct book));
pershiy = element;

do
<
poperedbook = element;

ostan = poperedbook;
poperedbook->next = NULL ;
>

void hood( void )
<
element = pershiy;

int main()
<
SetConsoleCP(1251);
SetConsoleOutputCP(1251);

struct list <
int ptr;
list *next;
>;

void input_list(list *&first, int n) <
first = new list;
cinn >> first->ptr;
list *q = first;
for ( int i = 0; i next = new list;
q = q->next;
cin >> q->ptr;
>
q->next = 0;
>
void print_list(list *q) <
while (q) <
cout q->ptr » » ;
q = q->next;
>
cout endl;
>

void razbienie_list(list *&first) <
list *q = first;
list *chet = new list;
list *nechet = new list;
list *q1 = chet;
list *q2 = nechet;
list *w1 = q1;
list *w2 = q2;
while (p) <
if (q->ptr % 2) <
q2->ptr = p->ptr;
q2->next = new list;
w2 = q2;
q2 = q2->next;
>
else <
q1->ptr = p->ptr;
q1->next = new list;
q1 = q1;
q1 = q1->next;
>;
q = q->next;
>
w1->next = 0;
w2->next = 0;
>

int main() <
list *first = 0;
int n = 5;
input_list(first, n);
print_list(first);
razbienie_list(first);
print_list(first);
return 0;
>

int main()
<
char name[maxSize] = <'\0'>;
char type[maxSize] = <'\0'>;
double MaximumHeight;
double lifespan;

Wood* Head = nullptr;
int n;

//Вводим число деревьев, которые будем хранить в массиве
cout «Number of Wood = » ;
cin >> n;
//Вводим информацию о всех деревьях с помощью реализованной функции
for ( int i = 0; i // удаление элемента
cout » deleted Woods = » ;
cin >> lifespan;
DeleteWood(Head, WoodSearch(Head, lifespan)); // ЗДЕСЬ ОШИБКА
PrintWood(Head);

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
struct list
<
int field;
struct list* ptr;
>;
// Инициализация списка (ОЛС)

struct list* init( int a)
<
struct list* head = ( struct list*)malloc( sizeof ( struct list));
head->field = a;
head->ptr = NULL ;
return (head);
>
// Добавление элемента (возвращает добавленный элемент) (ОЛС)
struct list* addelem( struct list* lst, int number)
<

struct list* temp, * p;
temp = ( struct list*)malloc( sizeof ( struct list)); // выделение памяти под узел списка
p = lst->ptr; // временное сохранение указателя
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return (temp);
>

// Удаление корня списка (возвращает новый корень) (ОЛС)
struct list* deletehead( struct list* root)
<
struct list* temp;
temp = root->ptr;
free(root);
return (temp); // новый корень списка
>

struct list* add( struct list* head, int data)
<
struct list* temp, * p;
p = head->ptr;
temp = ( struct list*)malloc( sizeof ( struct list));
head->ptr = temp;
temp->field = data;
temp->ptr = p;
return (temp);
>

struct list* t1 = t->ptr;
while (t1)
<
if (t1->field == v)
<
t->ptr = t1->ptr;
free(t1);
return ;
>
t = t1;
t1 = t1->ptr;
>
>

void sub( struct list* a, struct list* b)
<
struct list* p2;
for ( struct list* p2 = b; p2; p2 = p2->ptr)
del(a, p2->field);
/* struct list* p2;
p2 = b;
while (p2)
<
del(a, p2->field);
p2 = p2->ptr;
>*/
/* struct list* p1, * p2;
p1 = a;
p2 = b;
while (p1)
<
while (p2)
<
if (p1->field == p2->field)
deletelem(p1, p1->field);
p2 = p2->ptr;
>
p1 = p1->ptr;
>*/
>
int main()
<
setlocale(LC_ALL, «Russian» );

/* struct list* p1 = ( struct list*)malloc( sizeof ( struct list));
struct list* p2 = ( struct list*)malloc( sizeof ( struct list));

p1 = init(5);
add(p1, 6);
add(p1, 9);
p2 = init(6);
add(p2, 7);

Источник

Односвязный список

В информатике, cвя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Содержание

Виды связных списков

Линейный связный список

Односвязный список

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.

Двусвязный список

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

XOR-связный список

Кольцевой связный список

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

Список с пропусками

Развёрнутый связный список

Достоинства

Недостатки

См. также

Полезное

Смотреть что такое «Односвязный список» в других словарях:

Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия

Двусвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия

Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия

Линейный список — У этого термина существуют и другие значения, см. Список. Разновидность связного списка односвязный список, содержащий 3 элемента Линейный однонаправленный список это структура данных, состоящая из элементов одног … Википедия

Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия

Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с… … Википедия

Развернутый связанный список — Развёрнутый связанный список список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить… … Википедия

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

Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто … Википедия

Коллекция данных — Коллекция в программировании программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям. Коллекция позволяет записывать в себя значения и извлекать их.… … Википедия

Источник

Введение в связанные списки

Авторизуйтесь

Введение в связанные списки

Знакомимся со структурой связных списков вместе с Арианой на примере её песни «‎Thank U, Next». Если вы её ещё не слышали, то посмотрите клип, прежде, чем читать дальше.

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

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

В статье мы будем использовать следующий список:

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

Thought I’d end up with Sean
But he wasn’t a match
Wrote some songs about Ricky
Now I listen and laugh
Even almost got married
And for Pete, I’m so thankful
Wish I could say, «Thank you» to Malcolm
‘Cause he was an angel

Последний узел — сама Ариана:

Plus, I met someone else
We havin’ better discussions
I know they say I move on too fast
But this one gon’ last
‘Cause her name is Ari
And I’m so good with that (so good with that)

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

25–26 ноября, Москва и онлайн, От 24 000 до 52 000 ₽

Простейший способ создать односвязный список — поочерёдно создать и связать узлы:

Пример аналогичного кода на Python.

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

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

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

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

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

Вот как будет выглядеть удаление Ricky из нашего связного списка, если Ариана перестанет быть ему так чертовски благодарна:

Все объекты красного цвета удаляются.

Два других полезных метода — search и iterate :

Итак, мы знаем, что хранение перечня бывших Арианы в связном списке — хорошее применение этой структуры данных. Ведь мы всегда перечисляем их в одном порядке, напевая «‎thank u, next»! Ещё они хорошо подходят, например, для формирования очереди задач. Так, принтеры печатают по одной странице, но мы хотим добавлять дополнительные задачи и не отправлять документы на печать по одной странице. Когда мы создаём список задач, мы всегда будем добавлять новые объекты в конец очереди и потом печатать первый объект в списке. Похожим образом работает кнопка браузера «‎Назад» или функция «‎Undo» редактора. Для реализации этих возможностей ПО обычно используют структуры данных стек или очередь, основанные на связанных списках.

Источник