Доступ к элементам связного списка

@metrolog · Регистрация: 18.11.2012

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

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

@yoghurt92 · 06.04.2013, 00:09

metrolog, смотрите в сторону индексированных списков.

Добавлено через 12 минут
metrolog, а что ты хочешь там сделать?

@metrolog · 06.04.2013, 00:24 **[ТС]**

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

@yoghurt92 · 06.04.2013, 00:28

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

@metrolog · 06.04.2013, 00:37 **[ТС]**

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

все, вопросов нет, разобрался.)) добавляем и элемент вектора в середину списка.

@yoghurt92 · 06.04.2013, 00:44

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

@metrolog · 06.04.2013, 00:48 **[ТС]**

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

@yoghurt92 · 06.04.2013, 00:53

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

@metrolog · 06.04.2013, 01:05 **[ТС]**

а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ?

Добавлено через 8 минут
то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так?

@OhMyGodSoLong · 06.04.2013, 01:58

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

а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ?

Обновить связи его соседей, прибить сам элемент.

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

то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так?

Не с каждым добавлением, но да. И ещё часть элементов надо сдвигать (всегда), если вставка производится не в конец вектора.

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

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

Именно таким, каким вы подумали: тупо проходим по всему списку до нужного элемента. Можно навернуть сверху различных кеширований, разреженных и развёрнутых списков и т. п., но суть остаётся та же.

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

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

Когда надо делать много вставок и удалений элементов не только по краям. Когда надо вставлять/удалять сразу целые подсписки.

@metrolog · 06.04.2013, 11:56 **[ТС]**

Каким образом прибить сам элемент? Delete?

@OhMyGodSoLong · 06.04.2013, 13:28

Естессно. Если создавали с помощью new.

@metrolog · 06.04.2013, 23:33 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct node{
 
int number;
node *next;
};
 
...
 
node* pOne;
node* pEnd;
 
// создаем node temp каким либо образом.
 
if( pOne==NULL)  // добавляем temp в список.
pOne = temp;
pEnd = temp;
 
else
{ pEnd->next = temp;
pEnd = temp;
}

если хочу удалить этот элемент из списка что делать?
то что у соседних элементов поменять указатели на следующие элементы это понятно.
а как именно из памяти его удалить?

Добавлено через 9 часов 53 минуты
то есть node temp нужно создавать через new чтобы потом удалить его?
если не через new его создал то уже не освободить эту ячейку памяти? или когда ссылок на нее не будет сборщик мусора сам заберет ее?

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101

	Доступ к элементам связного списка 05.04.2013, 23:51. Показов 4735. Ответов 12 Метки нет (Все метки) как организовать самый простой для реализации способ чтобы получить доступ к i-му элементу в односвязном списке? придумал только создать вектор в который помещать адрес элемента из списка, получая доступ к i-му элементу вектора, получаем доступ к нужному элементу связного списка. но тогда сама суть пропадает связного списка, раз вектор используем в придачу к нему. 0

@yoghurt92 381 / 352 / 113 Регистрация: 17.05.2012 Сообщений: 1,049
	06.04.2013, 00:09
	metrolog, смотрите в сторону индексированных списков. Добавлено через 12 минут metrolog, а что ты хочешь там сделать? 0

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101
	06.04.2013, 00:24 [ТС]
	да просто интересно как к элементам по индексам доступ осуществлять. хотел бы узнать именно в связных списках как простым способом это делается 0

@yoghurt92 381 / 352 / 113 Регистрация: 17.05.2012 Сообщений: 1,049
	06.04.2013, 00:28
	metrolog, я как-то писал программу для индексированных списков, там принцип тот что и вы предложили, только я хранил указатели в массиве, там было задание для адресной книжки, чтобы ускорить поиск я хранил указатели на первые записи каждой буквы алфавита. 1

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101
	06.04.2013, 00:37 [ТС]
	к примеру я хочу вставить элемент не в конец списка я между какими нибудь элементами. не проблема, вставил) но как быть с порядковыми номерами тогда, все элементы списка привязаны к элементам вектора ведь ? все элементы списка сдвигать в векторе? все, вопросов нет, разобрался.)) добавляем и элемент вектора в середину списка. 0

@yoghurt92 381 / 352 / 113 Регистрация: 17.05.2012 Сообщений: 1,049
	06.04.2013, 00:44
	так а зачем тебе вообще индексированный список, что ты хранишь в списке? в векторе храни только на указатели на некоторые элементы списка, иначе в этих индексах не будет толку. 0

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101
	06.04.2013, 00:48 [ТС]
	да ничего не храню)) просто разбираюсь))) в каком случае связный список использовать выгоднее чем вектор? 0

@yoghurt92 381 / 352 / 113 Регистрация: 17.05.2012 Сообщений: 1,049
	06.04.2013, 00:53
	если тебе нужен быстрый доступ, то однозначно вектор, так как он обеспечивает произвольный доступ с постоянной скоростью, чего не скажешь о списках, зато в списках быстро происходит вставка и удаление, причем не только с концов. и если не ошибаюсь, то в списках нельзя наткнуться на перераспределение памяти в отличие от вектора. 1

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101
	06.04.2013, 01:05 [ТС]
	а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ? Добавлено через 8 минут то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так? 0

@metrolog 4 / 4 / 0 Регистрация: 18.11.2012 Сообщений: 101
	06.04.2013, 11:56 [ТС]
	Каким образом прибить сам элемент? Delete? 0

@OhMyGodSoLong ~ Эврика! ~ 1258 / 1007 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	06.04.2013, 13:28
	Естессно. Если создавали с помощью new. 0