однонаправленный список это список в котором получив доступ к элементу списка можно
Односвязный линейный список
Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на 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);
Реализация односвязного линейного списка в СИ
Односвязный список – это динамическая структура данных, элементы которой содержат ссылку на следующий элемент. Последний элемент имеет в качестве ссылки NULL. Для доступа к списку используется указатель на первый элемент.
Односвязный список состоит из узлов. Каждый узел содержит в себе указатель на следующий узел (элемент списка) и хранимое значение. Узлы представляются в качестве структуры:
Инициализируем список
Мы инициализируем список отдельной функцией для того, чтобы облегчить процесс добавления звеньев в список. Другими словами, мы создаем заглавное звено списка.
Добавим узел в начало списка
Добавим узел в конец списка
Добавим узел в определенное место списка
Удалим весь список
Данная функция полностью «уничтожает» список, рассмотрим случай когда нужно удалить только определенный элемент из списка.
Удалим определенный узел списка
В данной функции используется принцип функции удаления всего списка и добавления нового элемента в n-ую позицию (конечно, никакого добавления нового узла нет, но здесь мы связываем элемент до удаляемого узла с элементом, расположенным после удаляемого узла).
Вывод элементов списка
Рассмотрим простейший способ вывода элементов списка:
В данной статье мы рассмотрели основные функции, которые предназначены для работы с односвязными списками. Если у Вас остались вопросы, то просьба писать их в комментариях.
Подписывайтесь на T4S.TECH в Telegram, Twitter и во «ВКонтакте», чтобы оставаться в курсе самых интересных новостей из мира технологий и не только.
Razer представила водонепроницаемую игровую клавиатуру
Геймерские клавиатуры прошли большое количество испытаний и к ним предъявляют высокие требования. Они должны быть прочными, удобными и функциональными. Также будет хорошо, если клавиатура будет
Google выпустил YouTube VR для Steam
Виртуальная реальность набирает все большую популярность и становится следующей крупной технологией в сфере мультимедиа и развлечений. В настоящее время на рынке продаются различные очки VR,
Односвязный список
В информатике, cвя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Содержание
Виды связных списков
Линейный связный список
Односвязный список
В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.
Двусвязный список
По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, т.к. всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список
Кольцевой связный список
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Список с пропусками
Развёрнутый связный список
Достоинства
Недостатки
См. также
Полезное
Смотреть что такое «Односвязный список» в других словарях:
Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия
Двусвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
Линейный список — У этого термина существуют и другие значения, см. Список. Разновидность связного списка односвязный список, содержащий 3 элемента Линейный однонаправленный список это структура данных, состоящая из элементов одног … Википедия
Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия
Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с… … Википедия
Развернутый связанный список — Развёрнутый связанный список список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить… … Википедия
Сортировка связного списка — Сортировка связного списка. Подавляющее большинство алгоритмов сортировки требует для своей работы возможности обращения к элементам сортируемого списка по их порядковым номерам (индексам). В связных списках, где элементы хранятся неупорядоченно … Википедия
Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто … Википедия
Коллекция данных — Коллекция в программировании программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям. Коллекция позволяет записывать в себя значения и извлекать их.… … Википедия
Односвязный список
Введение. Основные операции
О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.
Для нас односвязный список полезен тем, что
Для простоты рассмотрим односвязный список, который хранит целочисленное значение.
Односвязный список состоит из узлов. Каждый узел содержит значение и указатель на следующий узел, поэтому представим его в качестве структуры
Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.
Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо
1) Создаём новый узел
2) Присваиваем ему значение
3) Присваиваем указателю tmp адрес предыдущего узла
4) Присваиваем указателю head адрес нового узла
5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.
Так как указатель head изменяется, то необходимо передавать указатель на указатель.
Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.
Если мы перекинем указатель head на следующий элемент, то мы потеряем адрес первого и не сможем его удалить и тем более вернуть его значения. Для этого необходимо сначала создать локальную переменную, которая будет хранить адрес первого элемента
Уже после этого можно удалить первый элемент и вернуть его значение
Не забываем, что необходимо проверить на NULL голову.
Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.
Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла
Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.
Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL
Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый
Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.
Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.
Удаление последнего элемента и вставка в конец имеют сложность O(n).
Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:
Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент
Покажем на рисунке последовательность действий
После этого делаем так, чтобы новый элемент ссылался на следующий после n-го
Список
Связный список (англ. 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] изменят свое направление, не нарушив связности самого списка.