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

@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++

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 его создал то уже не освободить эту ячейку памяти? или когда ссылок на нее не будет сборщик мусора сам заберет ее?

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	06.04.2013, 01:58	10
	Сообщение от metrolog а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ? Обновить связи его соседей, прибить сам элемент. Сообщение от metrolog то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так? Не с каждым добавлением, но да. И ещё часть элементов надо сдвигать (всегда), если вставка производится не в конец вектора. Сообщение от metrolog да просто интересно как к элементам по индексам доступ осуществлять. хотел бы узнать именно в связных списках как простым способом это делается Именно таким, каким вы подумали: тупо проходим по всему списку до нужного элемента. Можно навернуть сверху различных кеширований, разреженных и развёрнутых списков и т. п., но суть остаётся та же. Сообщение от metrolog да ничего не храню)) просто разбираюсь))) в каком случае связный список использовать выгоднее чем вектор? Когда надо делать много вставок и удалений элементов не только по краям. Когда надо вставлять/удалять сразу целые подсписки. 1

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

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

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

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

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

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

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

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

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

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

Опции темы

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