Реалізація однозв'язного списку в Java

Доброго вечора шановні читачі! Існує безліч структур даних. Найпопулярніші з них - масиви та зв’язні списки. Хотілося нагадати вам декілька вад масивів:

• В неупорядкованому масиві пошук виконується повільно
• В упорядкованому масиві повільно виконується вставка
• Видалення виконується повільно, як в упорядкованому так і в неупорядкованому масиві
• Неможливо змінити розмір масиву після його створення

В нашій статті ми розглянемо зв’язні списки – структури даних, які вирішують вищезгадані проблеми. Крім того, зв’язаний список може бути основою для створення інших структур даних (таких як стеки та черги). Зв’язані списки можна використовувати замість масивів (окрім ситуацій з частим випадковим доступом до окремих елементів по індексу).

Зв’язані списки не вирішують усіх проблем збереження даних, але вони універсальні та прості на концептуальному рівні.
Почнемо з найпростішого – однозв’язного списку. В цій структурі даних кожен елемент даних, міститься у спеціальному об’єкті – елементі списку (класу, на основі якого створюються ці об’єкти, часто надається ім’я Link). Кожен об`єкт цього класу містить посилання на наступний елемент списку(поле next).

Розглянемо початок реалізації класу Link:

class Link {
    public  int iData; // інформація
    public double dData; // інформація
    public Link next; // посилання на наступний елемент списку
    public Link(int iData, double dData) {
        this.iData = iData;
        this.dData = dData;
    }
    public void displayLink() {
        System.out.print(" {" + iData + ", " + dData + "}");
    }
}

Створимо поля, які буду нести певну інформацію (iData, dData) та поле (next), яке має посилання на об’єкт того ж типу (такі поля також називають самовідносними (self-referential)).

З першого погляду, включення такого поля у клас Link виглядає незрозумілим та заплутаним (як компілятор зрозуміє скільки пам’яті виділити під об’єкт next?). Справа в тому, що клас Link зберігає не об’єкт, а лише посилання на нього. Посилання - це число, яке асоціюється з об’єктом. Іншими словами, посилання – адреса об’єкту в пам’яті. На відміну від масиву, де потрібний елемент можна знайти за індексом, знайти елемент у списку можна лише одним способом – відслідкувати його по ланцюжку елементів від початку списку.

Клас Link буде містити лише один метод, відображення даних конкретного вузла.

public void displayLink() {
        System.out.print(" {" + iData + ", " + dData + "}");    
    }

Настав час реалізувати новий клас, який буде «об’єднанням» наших елементів і безпосередньо буде реалізацією зв'язаного списку. Назвемо цей клас LinkedList. Він буде містити наступні методи:

1) insertFirst - метод, який вставляє новий елемент списку на першу позицію

Реалізація методу:

public void insertFirst(int iD, double dD) {
        Link newLink = new Link(iD, dD); //створюємо новий елемент списку
        newLink.next = first; //вказали на старий "перший" елемент і таким чином зробили його другим
        first = newLink; // позначили створений елемент, як перший
    }

Графічне зображення цього процесу:

2) find – метод, який забезпечує пошук інформації у нашому списку

public Link find(int key) { // пошук елемента с заданим ключем
        Link current = first; // починаємо пошук з першого елемента
        while (current.iData != key) { // якщо, ключ не знайдено,то..
         if (current.next == null) { //якщо ключа немає в списку взагалі, повертаємо null
             return null; 
         } else {
             current = current.next; //то переходимо до наступного елемента і шукаємо ключ
         }
        }
        return current;
    }

3) delete – метод, який забезпечує видалення певного елемента списку

Пошук елементу аналогічний розглянутому вище. Під час видалення елемента, потрібно розглянути декілька ситуацій. По перше, якщо елемент який видаляється займає першу позицію, то ми просто зміщуємо посилання First, на другий елемент в списку, а про перший «забуваємо».
По друге – якщо елемент який видаляється знаходиться всередині списку, то його потрібно обійти.

Реалізація:

public Link delete(int key) { //видалення елементу по заданому ключу
        Link current = first; 
        Link previous = first;
        while (current.next != null) { // пошук елемента
            if (current.next == null) {
                return null;    // елемент не знайдено
            } else {
                previous = current; // перейти до наступного елементу
                current = current.next;
            }
            // ключ знайдено
            if (current == first) {
                first = first.next; // якщо шуканий елемент - перший
            } else {
                previous.next = current.next; // якщо шуканий елемент лежить всередині списку, обійдемо його
            }
        }
        return current;
    }

4) displayList метод відображення даних у нашому списку

public void displayList() {
        Link current = first;
        System.out.print("List (first --> last): ");
        while(current != null) { //доки список не закінчився, відображаємо дані
            current.displayLink(); // відображаємо дані елементу, на якому знаходимося
            current = current.next; // переходимо до наступного елементу
        }
        System.out.println("");
    }
}

Основні методи нашого списку готові. Давайте поглянемо що вийшло!

На сьогодні це все. Але, для вас невелике домашнє завдання:

1) реалізуйте обробку помилки пошуку неіснуючого елементу

2) реалізуйте метод видалення останнього елементу списку

Якщо будуть питання, звертайтеся! Успіху!

Лістинг:

class Link {
    public  int iData; // інформація
    public double dData; // інформація
    public Link next; // посилання на наступний елемент списку
    public Link(int iData, double dData) {
        this.iData = iData;
        this.dData = dData;
    }
    public void displayLink() {
        System.out.print(" {" + iData + ", " + dData + "}");
    }
}
class LinkList {
    Link first;
    public LinkList() {
        first = null;
    }
    public void insertFirst(int iD, double dD) {
        Link newLink = new Link(iD, dD); //створюємо новий елемент списку
        newLink.next = first; //вказали на старий "перший" елемент і таким чином зробили його другим
        first = newLink; // позначили створений елемент, як перший
    }
    public Link find(int key) { // пошук елемента с заданим ключем
        Link current = first; // починаємо пошук з першого елемента
        while (current.iData != key) { // якщо, ключ не знайдено,то..
         if (current.next == null) { //якщо ключа немає в списку взагалі, повертаємо null
             return null; 
         } else {
             current = current.next; //то переходимо до наступного елемента і шукаємо ключ
         }
        }
        return current;
    }
    public Link delete(int key) { //видалення елементу по заданому ключу
        Link current = first; 
        Link previous = first;
        while (current.next != null) { // пошук елемента
            if (current.next == null) {
                return null;    // елемент не знайдено
            } else {
                previous = current; // перейти до наступного елементу
                current = current.next;
            }
            // ключ знайдено
            if (current == first) {
                first = first.next; // якщо шуканий елемент - перший
            } else {
                previous.next = current.next; // якщо шуканий елемент лежить всередині списку, обійдемо його
            }
        }
        return current;
    }
    public void displayList() {
        Link current = first;
        System.out.print("List (first --> last): ");
        while(current != null) { //доки список не закінчився, відображаємо дані
            current.displayLink(); // відображаємо дані елементу, на якому знаходимося
            current = current.next; // переходимо до наступного елементу
        }
        System.out.println("");
    }
}
public class LinkedList {
    public static void main(String[] args) {
        LinkList newList = new LinkList();
        newList.insertFirst(12, 30.99);
        newList.insertFirst(10, 30.99);
        newList.insertFirst(45, 345.34);
        newList.insertFirst(14, 23.78);
        newList.insertFirst(54, 12.59);
        newList.displayList();
        Link f = newList.find(10);
        System.out.println("Ми знайшли: " +f.iData);
    }
}