Різниця між спільно пов'язаним списком і списком, що зв'язаний удвічі

Спільно пов'язаний список проти подвійно пов'язаний список

Пов'язаний список - це лінійна структура даних, яка використовується для зберігання колекції даних. Зв'язаний список виділяє пам'ять своїм елементам окремо у своєму власному блоці пам'яті, і загальна структура отримується шляхом з'єднання цих елементів як ланок у ланцюжку. Окремо пов'язаний список складається з послідовності вузлів, і кожен вузол має посилання на наступний вузол у послідовності. Подвійно пов'язаний список містить послідовність вузлів, у яких кожен вузол містить посилання на наступний вузол, а також на попередній вузол.

Окремо пов'язаний список

Кожен елемент спільно пов'язаного списку має два поля, як показано на малюнку 1. Поле даних містить фактично збережені дані, а наступне поле містить посилання на наступний елемент ланцюга. Перший елемент пов'язаного списку зберігається як голова пов'язаного списку.

На малюнку 2 зображено окремо пов'язаний список з трьома елементами. Кожен елемент зберігає свої дані та всі елементи, крім останнього, зберігає посилання на наступний елемент. Останній елемент містить нульове значення у наступному полі. Будь-який елемент у списку можна отримати, починаючи з заголовка та слідуючи наступному вказівнику, поки ви не зустрінете потрібний елемент.

Двозначно пов'язаний список

Кожен елемент подвійно зв'язаного списку має три поля, як показано на малюнку 3. Як і в окремо зв'язаному списку, у полі даних зберігаються фактичні дані, що зберігаються, і наступне поле містить посилання на наступний елемент ланцюга. Крім того, попереднє поле містить посилання на попередній елемент ланцюга. Перший елемент пов'язаного списку зберігається як голова пов'язаного списку.

На малюнку 4 зображено подвійно пов'язаний список з трьома елементами. Всі проміжні елементи зберігають посилання на перший та попередні елементи. Останній елемент у списку містить нульове значення у наступному полі, а перший елемент у списку містить нульове значення у попередньому полі. Подвійно пов'язаний список можна просувати вперед, слідуючи наступним посиланням у кожному елементі, і аналогічно можна просувати назад, використовуючи попередні посилання на кожен елемент.

Яка різниця між спільно пов’язаним списком та списком, що зв'язаний подвійно?

Кожен елемент у спільно пов'язаному списку містить посилання на наступний елемент у списку, тоді як кожен елемент у подвійному зв’язку списку містить посилання на наступний елемент, а також на попередній елемент у списку. Подвійно пов'язані списки потребують більше місця для кожного елемента у списку, а елементарні операції, такі як вставка та видалення, є складнішими, оскільки вони мають мати справу з двома посиланнями. Але подвійні списки посилань дозволяють простіше маніпулювати, оскільки це дозволяє пересувати список у напрямку вперед та назад.