Зв'язний список

В інформатиці, зв'язний список - базова динамічна структура даних, що складається з вузлів, кожен з яких містить як власне дані, так і одну або дві посилання ("зв'язування") на наступний та / або попередній вузол списку. [1] Принциповим перевагою перед масивом є структурна гнучкість: порядок елементів зв'язкового списку може не збігатися з порядком розташування елементів даних в пам'яті комп'ютера, а порядок обходу списку завжди явно задається його внутрішніми зв'язками.


1. Види зв'язкових списків

1.1. Лінійний зв'язний список

1.1.1. Односвязного список (Однонаправлений зв'язний список)

Single linked list.png

Тут посилання в кожному вузлі вказує на наступний вузол в списку. У односвязного списку можна пересуватися тільки в бік кінця списку. Дізнатися адресу попереднього елемента, спираючись на вміст поточного вузла, неможливо.


1.1.2. Двусвязний список (Двонаправлений зв'язний список)

Doubly linked list.png

Тут посилання в кожному вузлі вказують на попередній і на наступний вузол в списку. За двозв'язним списку можна пересуватися в будь-якому напрямку - як до початку, так і до кінця. У цьому списку простіше проводити видалення і перестановку елементів, так як завжди відомі адреси тих елементів списку, покажчики яких спрямовані на змінюваний елемент.


1.1.3. XOR-зв'язний список

1.2. Кільцевій зв'язний список

Різновидом зв'язкових списків є кільцевий (циклічний, замкнутий) список. Він теж може бути односвязного або двозв'язним. Останній елемент кільцевого списку містить покажчик на перший, а перший (у разі двозв'язним списку) - на останній.

Односвязного кільцевої список

Реалізація такої структури відбувається на базі лінійного списку. У кожному кільцевому списку є вказівник на перший елемент. У цьому списку константи NULL не існує.

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


1.3. Список з пропусками

1.4. Розгорнутий зв'язний список

2. Приклад реалізації на Java

 public  class  Node  {  private  int  element  ;  private  Node next  ;  public  int  getElement  (  )  {  return  element  ;  }  public  void  setElement  (  int  e  )  {  element  =  e  ;  }  public  Node getNext  (  )  {  return  next  ;  }  public  void  setNext  (  Node n  )  {  next  =  n  ;  }  } 

3. Переваги

  • легкість додавання і видалення елементів
  • розмір обмежений тільки об'ємом пам'яті комп'ютера і розрядністю покажчиків
  • динамічне додавання і видалення елементів

4. Недоліки

  • складність визначення адреси елемента за його індексу (номера) в списку
  • на поля-покажчики (покажчики на наступний і попередній елемент) витрачається додаткова пам'ять (в масивах, наприклад, покажчики не потрібні)
  • робота зі списком повільніше, ніж з масивами, так як до будь-якого елементу списку можна звернутися, тільки пройшовши всі попередні йому елементи
  • елементи списку можуть бути розташовані в пам'яті розріджено, що надасть негативний ефект на кешування процесора
  • над зв'язними списками набагато важче (хоча і в принципі можливо) проводити паралельні векторні операції, такі як обчислення суми
  • кеш -промахи при обході списку

Примітки

  1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7
Перегляд цього шаблону Структури даних ( список)
Типи
Масиви
Списки
Дерева
Графи