Идеология односвязного списка

@Zigfrid · Регистрация: 24.11.2015

Студворк — интернет-сервис помощи студентам

Здарова!

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

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

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

@zss · 03.11.2016, 18:21

Почитайте вот это:
http://ci-plus-plus-snachala.ru/?p=57

@Zigfrid · 03.11.2016, 18:24 **[ТС]**

zss, я читал, отсюда и вынес все эти сентенции)

ValeryS · 03.11.2016, 18:30

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

это как надпись на стенках туалета, где на каждой стенке написано "Посмотри налево"

Maxim Prishchepa · 03.11.2016, 18:31

Почитайте про списки и про массивы

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

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

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

ну это вкратце, более подробно читайте мануалы

IGPIGP · 03.11.2016, 19:09

Zigfrid, массив и список это структуры данных произвольного и последовательного доступа. Об этом хорошо сказал Maxim Prishchepa. В обработке информации одним из базовых вопросов является поиск. Ясно, что искать легче всего в сортированной (упорядоченной) последовательности. Упорядоченный массив позволяет реализовать бинарный поиск, время которого пропорционально логарифму ln₂N, а список нет. В списке надо пройти от начала и ... пока не найдёшь последовательно перебирая элементы. А это в среднем N/2, а в худшем случае N. То есть в списке поиск пропорционален N по времени. Зато в списке можно быстро вставлять и удалять элементы. Тут затраты на поиск элементов, с лихвой компенсируются отсутствием необходимости перевыделения памяти и переписывания в неё старого содержимого. Существуют гибридные структуры сочетающие массивы и списки. Деревья используются тоже. В целом, выбор структуры зависит от той технологии которую предполагается к ней применять.

@castaway · 03.11.2016, 19:51

Сообщение от Zigfrid

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

Нет. Массив так же может хранить объекты разнообразных типов.

ValeryS · 03.11.2016, 22:52

Сообщение от castaway

Массив так же может хранить объекты разнообразных типов.

покажь

IGPIGP · 04.11.2016, 02:06

Сообщение от ValeryS

покажь

Это ответ на тираду сравнивающую массив и список по возможности размещать типы. Массив может хранить разные типы, так же как и список, но не вперемешку, конечно.

Там есть, на что ответить. Например:

Сообщение от Zigfrid

Насколько я понял, односвязный список - это аналог простого массива

А двусвязный? Причём тут количество связей? Двусвязный позволяет двигаться в двух направлениях и он ближе к массиву, чем односвязный.

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

ValeryS · 04.11.2016, 02:21

Сообщение от IGPIGP

Массив может хранить разные типы, так же как и список

теперь ты покажь
как будет выглядеть массив хранящий 3 инта 1 чар и 2 флоата?

@dailydose · 04.11.2016, 05:45

ValeryS,

Сообщение от IGPIGP

Массив может хранить разные типы, так же как и список

Сообщение от ValeryS

теперь ты покажь
как будет выглядеть массив хранящий 3 инта 1 чар и 2 флоата?

Сообщение от IGPIGP

но не вперемешку, конечно.

)

@castaway · 04.11.2016, 07:17

ValeryS, может быть я не совсем правильно выразился, а может быть вы нас просто не поняли, но речь не о том что в массив можно запихать объекты разных типов.

ValeryS · 04.11.2016, 08:24

Сообщение от castaway

а может быть вы нас просто не поняли, но речь не о том что в массив можно запихать объекты разных типов.

а как же вас понять?

Сообщение от castaway

может хранить объекты разнообразных типов.

Сообщение от IGPIGP

Массив может хранить разные типы,

или это следует читать так
один массив int, другой char, третий еще какой-то ?

@castaway · 04.11.2016, 08:54

Да, следует читать так. Ведь ТС ничего не говорил про хранение разных объектов в одном массиве, к чему бы нам переключаться на эту тему?

ValeryS · 04.11.2016, 09:08

castaway, ну тогда прошу пардону

но я бы сказал так
Массив предназначен для хранения любых, но однотипных данных.
или как К. Касперски: "Массив по определению гомогенен и данные разных типов хранить не может."

@Zigfrid · 04.11.2016, 09:10 **[ТС]**

Сообщение от ValeryS

любых, но однотипных данных

Вот в чем дело! Теперь вроде стало понятнее

ValeryS · 04.11.2016, 09:20

Zigfrid, так все предназначены для однотипных данных
и массив, и список, и стек, и очередь, и дерево

@Zigfrid · 04.11.2016, 09:21 **[ТС]**

Сообщение от ValeryS

как будет выглядеть массив хранящий 3 инта 1 чар и 2 флоата?

Я думал, что в массиве это сделать нельзя, а в списке можно, нет?

ValeryS · 04.11.2016, 09:29

Сообщение от Zigfrid

а в списке можно, нет?

тоже нельзя, однотипные данные
для хранения нужно разные массивы и списки тоже разные

Сообщение от ValeryS

3 инта 1 чар и 2 флоата?

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

IGPIGP · 04.11.2016, 09:31

Сообщение от Zigfrid

Я думал, что в массиве это сделать нельзя, а в списке можно, нет?

Зато теперь правильно думаете, а это главное.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Zigfrid 11 / 11 / 1 Регистрация: 24.11.2015 Сообщений: 359

	Идеология односвязного списка 03.11.2016, 18:17. Показов 4469. Ответов 41 Метки нет (Все метки) Здарова! Посмотрел, что такое односвязный список и возникли естественно кое-какие чисто идеологические вопросы. Насколько я понял, односвязный список - это аналог простого массива, только память выделяется динамически, но в отличае от дин. массива не поддерживается функция вставки и удаления постфактум (то есть: мы задали размер дин. массива вначале и больше менять его размер не можем, а размер односвязного списка - можем) Еще отличае в том, что в простом массиве, элемент - просто число, а в односвязном - это может быть все, что угодно, например, объект класса или структуры. Вопрос в том, правильно ли я понял эти моменты и если да, то зачем нам нужен односвязный список, можно ведь просто воспользоваться массивом типа Vector, он точно также динамически меняет свой размер и его элементами могут быть любые типы данных. 0

@zss Модератор 13769 / 10962 / 6491 Регистрация: 18.12.2011 Сообщений: 29,236
	03.11.2016, 18:21
	Почитайте вот это: http://ci-plus-plus-snachala.ru/?p=57 0

@Zigfrid 11 / 11 / 1 Регистрация: 24.11.2015 Сообщений: 359
	03.11.2016, 18:24 [ТС]
	zss, я читал, отсюда и вынес все эти сентенции) 0

ValeryS Модератор 8978 / 6744 / 921 Регистрация: 14.02.2011 Сообщений: 23,852
	03.11.2016, 18:30
	в массиве элементы лежат строго друг за другом в списке где угодно, главное что элемент знает где лежит другой в односвязном следующий, в двусвязном и предыдущий и следующий это как надпись на стенках туалета, где на каждой стенке написано "Посмотри налево" 1

Maxim Prishchepa 1936 / 1048 / 109 Регистрация: 29.03.2010 Сообщений: 3,167
	03.11.2016, 18:31
	Сообщение было отмечено Zigfrid как решение Решение Почитайте про списки и про массивы Если вкратце: то массив - это непрерывная последовательность данных, а список это кусочки данных, которые знают о следующем (возможно еще и о предыдущем) своем элементе. Отсюдова и все плюсы и минусы: В массив тяжело добавить/удалить элемент, т.к. получите повторное выделение памяти и копирование всех данных. в списке же вы просто выкидываете одно из звеньев и изменяете ссылки на след./пред. элемент - и все... то же самое и с добавлением. В массиве вы можете перейти к любому элементу практически моментально (просто задав смещение от начала массива), а в списке вам нужно бежать по всему списку, что бы дойти до нужного элемента. ну это вкратце, более подробно читайте мануалы 2

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4706 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	03.11.2016, 19:09
	Zigfrid, массив и список это структуры данных произвольного и последовательного доступа. Об этом хорошо сказал Maxim Prishchepa. В обработке информации одним из базовых вопросов является поиск. Ясно, что искать легче всего в сортированной (упорядоченной) последовательности. Упорядоченный массив позволяет реализовать бинарный поиск, время которого пропорционально логарифму ln₂N, а список нет. В списке надо пройти от начала и ... пока не найдёшь последовательно перебирая элементы. А это в среднем N/2, а в худшем случае N. То есть в списке поиск пропорционален N по времени. Зато в списке можно быстро вставлять и удалять элементы. Тут затраты на поиск элементов, с лихвой компенсируются отсутствием необходимости перевыделения памяти и переписывания в неё старого содержимого. Существуют гибридные структуры сочетающие массивы и списки. Деревья используются тоже. В целом, выбор структуры зависит от той технологии которую предполагается к ней применять. 1

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	04.11.2016, 07:17
	ValeryS, может быть я не совсем правильно выразился, а может быть вы нас просто не поняли, но речь не о том что в массив можно запихать объекты разных типов. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	04.11.2016, 08:54
	Да, следует читать так. Ведь ТС ничего не говорил про хранение разных объектов в одном массиве, к чему бы нам переключаться на эту тему? 1

ValeryS Модератор 8978 / 6744 / 921 Регистрация: 14.02.2011 Сообщений: 23,852
	04.11.2016, 09:08
	castaway, ну тогда прошу пардону но я бы сказал так Массив предназначен для хранения любых, но однотипных данных. или как К. Касперски: "Массив по определению гомогенен и данные разных типов хранить не может." 1

ValeryS Модератор 8978 / 6744 / 921 Регистрация: 14.02.2011 Сообщений: 23,852
	04.11.2016, 09:20
	Zigfrid, так все предназначены для однотипных данных и массив, и список, и стек, и очередь, и дерево 0

Идеология односвязного списка

Решение