Двобічно зв'язаний список
Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.
Вузол двобічно зв'язаного списку складається з трьох полів: вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент.
Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.
Переваги двобічно зв'язаного списку над однобічно зв'язаним списком
- додавання нового вузла в певну позицію;
- видалення i-того елемента з послідовності;
- перегляд списку в обох напрямках.
Крім переваг існують і недоліки: з'являється додаткова змінна — вказівник на попередній елемент (prev). У даній статті описаний принцип роботи двобічно зв'язного циклічного списку. Єдина відмінність двобічно зв'язного циклічного списку від двобічно зв'язного списку в тому, що останній елемент указує на перший, а перший — на останній. Дана відмінність дозволяє виключати перевірки на «перший» і «останній» елемент. Двобічно зв'язаний циклічний список (далі просто Двобічно зв'язаний список) візуально можна представити в наступному вигляді(рис.1):
Стандартні функції для двобічно зв'язного списку
Функція push (додати новий елемент у i-ту позицію списку). Вона виконує наступні дії:
- створює новий елемент;
- копіює значення інформаційного поля;
- якщо даний елемент є єдиним:
- обидва покажчика (next і prev) посилаються на цей елемент (рис. 2),
- покажчик first вказує на єдиний елемент у списку.
- інакше зсувається покажчик на i-ий елемент і додається новий елемент перед i-им.
Додати нове значення у двобічно зв'язний список (push 4), новий елемент буде додаватися після першого. Після операції push список містититиме один елемент (рис. 2).
Додавши ще кілька значень (push 6 і push 7), кожен новий елемент буде додаватися після першого. Список міститиме три елементи (рис. 3) у такій послідовності:
Функція pop виштовхує i-ий елемент зі списку. Вона виконує наступні дії:
- якщо список порожній, вихід з функції;
- якщо в список містить єдиний елемент;
- копіюється значення інформаційного поля;
- видаляється елемент зі списку;
- присвоюється заголовку пусто.
- інакше - зсувається покажчик на i-ий елемент;
- якщо заголовок вказує на i-ий елемент (first == t), тоді переміщається заголовок на наступний елемент (First = t-> next)
- копіюється значення інформаційного поля;
- видаляється i-ий елемент зі списку.
- повертається значення інформаційного поля.
Виконавши функцію pop над лінійним списком (виштовхується 3-ій елемент). Отримується наступний стан зв'язного списку (рис. 4).
Функція print_all пробігає по всіх елементах і виводить в консоль значення інформаційного поля. Перегляд елементів здійснюється зліва направо, але легко можна переписати функцію і змінити перегляд елементів справа наліво (замінити a = a-> next на a = a-> prev). Функція clean видаляє всі елементи в списку і привласнює заголовку пусто (first = null). Після цієї операції список повертається в початковий стан.
Приклад реалізації двобічно зв'язаного списку на С++
struct List{
char name[30];
List *next;
List *prev;
};
//
List *head; // голова списку
//
void CreateList(){ // створення списку
head = NULL;
}
//
void add_from_the_head(char newname[30]){ // додати з голови
List * n = new List;
strcpy_s(n->name,newname);
if(head == NULL){
head = n;
head->next = NULL;
}
else{
n->next = head;
head->prev = n;
head = n;
}
}
//
void add_from_the_tail(char newname[30]){ // добавити з хвоста
List *n = new List;
strcpy_s(n->name,newname);
if(head == NULL){
head = n;
head->next = NULL;
}
else{
n->next = head;
while(n->next != NULL)
n = n->next;
List * nova = new List;
strcpy_s(nova->name,newname);
n->next = nova;
nova->prev = n;
nova->next = NULL;
}
}
//
bool add_after(char after[30]){ // добавити після якогось елемента
char newname[30];
List *n = head;
while(n != NULL){
if(strcmp(n->name,after) == 0){
cout << after << " Знайдено!" << endl;
cout <<"Введіть ім'я, що потрібно додати: "<<endl;
cin >> newname;
List * list = new List;
list->next = n->next;
n->next = list;
list->prev = n;
strcpy_s(list->name,newname);
return true;
}
n = n->next;
}
cout<<"Не знайдено нікого!"<<endl;
return false;
}
//
void Udalit(char smbdy[30]){ // видалення елемента
if(head == NULL){
perror("Список порожній!");
}
else{
List * n = head;
while(strcmp(head->name,smbdy)==0){ head = head->next;
}
List * pr;
n = head;
if(n!=NULL){
while(n->next!=NULL){
if(strcmp(n->next->name,smbdy)==0){
pr = n->next->next;
delete n->next;
n->next = pr;
pr->prev = n;
}
if((n->next!=NULL) && (strcmp(n->next->name,smbdy)!=0))
n = n->next;
}
}
}
}
//
void print_all(){ // друкування елемента
int counter = 1;
List * n = head;
if(n==NULL)
perror("Список порожній!");
while(n!=NULL){
cout << counter <<". "<<n->name << endl;
n = n->next;
counter++;
}
}
//
void search(char * name){ // пошук по категорії «ім'я» елемента
int counter = 1;
List * n = head;
while(n!=NULL){
if(strcmp(n->name,name)==0){
cout << counter <<". "<<n->name << endl;
counter++;
}
n = n->next;
}
if(counter == 1)
cout << "Не знайдено нікого!" <<endl;
}
//