Массивы и связные списки

	Tsubasa VA: Yumi Kakazu Stage Manager & Producer. She's in the position of giving orders to both the AKB0048 Succesors and the Understudies. She's calm, cool, collected, and a reliable commander. She's also a mysterious woman with a past she doesn't speak of.
	Ushiyama VA: Daisuke Ono He's AKB0048's dance instructor. He's both nice and strict at times. There's a strong bond of trust between him and Tsubasa, and the two of them are both friends who often consult each other for advice.
	Megumi Wanibuchi VA: Momoka Kinoshita She's one of the 76th generation understudies. She was close friends with her peer, Youko, who succeeded the name of Sae Miyazawa, becoming the 10th Sae Miyazawa.
	Hazuki Yanagawa VA: Miyu Takeuchi She's one of the 76th generation understudies. She's strong willed, but also very caring.
	Mamoru VA: Haruka Ishida He's one of Yuka's male friends. At first he was against idols, but now he's a WOTA who follows Suzuko.
	Aoi VA: Airi Furukawa She's one of the WOTA living in Lancaster. She's always together with Mamoru.
	Mikako Minamino VA: Sachiko Kojima She's a camerawoman who works at the Atami Star, the holy ground for gravure shoots. She was originally the 5th Successor to Minami Minegishi, and one of the Center Nova members, whose truth Tsubasa seeks?!

 

Массивы и связные списки

 

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

В листинге 1 представлен массив из 100 элементов и инициализируются его первые 3 значения.

Листинг 1. Инициализация массива

int my_array[100]; my_array[0]=1; my_array[1]=20; my_array[2]=100;

 

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

Для выделения памяти для связного списка используется иной механизм, когда память выделяется динамически, во время работы программы. Данный тип памяти называется «куча» (heap) и добавляемые элементы физически могут располагаться в такой куче безвсякого упорядочивания.

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

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

Списки бывают линейными и кольцевыми, односвязными и двусвязными.

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

1. динамически выделить под него память и

2. присвоить соответствующие значения указателям соседних элементов,

3. а также указателям самого созданного элемента.