Singly Linked List məlumat strukturu

codex

Tək istiqamətli əlaqəli listlər (Singly Linked List), hər elementi iki hissədən ibarət olan düyünlərdən (node) ibarət olan məlumat strukturudur: dəyər (data) və növbəti düyünə keçid (next pointer). Siyahının sonuncu düyünü null-a bərabər olur ki, bu da siyahının sonlandığını bildirir.

Bu məlumat strukturunun əsas məqsədi dinamik element kolleksiyasını səmərəli şəkildə saxlamaq və idarə etməkdir. Tək istiqamətli listlərin ən böyük üstünlüyü başlanğıc və ortada yerləşdirmə və silmə əməliyyatlarını effektiv şəkildə yerinə yetirməkdir. Bunun səbəbi odur ki, bu əməliyyatlar sadece bir neçə göstəricinin (pointer) dəyişdirilməsi ilə həyata keçirilir, bu da massivlərə (arrays) nisbətən daha səmərəli bir həll təqdim edir.

Linked Listlərin Üstünlükləri və Çatışmazlıqları

ÜSTÜNLÜKLƏR	ÇATIŞMAZLIQLAR
Dinamik Ölçü - Bağlı siyahılar yaddaşda bitişik (contiguous) şəkildə saxlanılmadığı üçün dinamik ölçüyə malikdirlər. Bu, verilənlərin ölçüsünün əvvəlcədən bilinmədiyi və ya tez-tez dəyişdiyi hallarda faydalıdır.	Təsadüfi (random) giriş yoxdur - Massivlərdən fərqli olaraq, bağlı siyahılar elementlərə birbaşa indekslə giriş imkanı vermir. Elementə çatmaq üçün siyahının başından keçmək lazımdır, bu isə ən pis halda O(n) zaman mürəkkəbliyinə malikdir.
Səmərəli Əlavə və Silmə Əməliyyatları - Siyahının başlanğıcında və ortasında elementlərin əlavə edilməsi və silinməsi O(1) mürəkkəbliyinə malikdir.	Yaddaş sərfiyyatı - Hər bir düyün data və növbəti düyünə keçid (next pointer) üçün əlavə yaddaş tələb edir.
Əvvəlcədən Yaddaş Ayrılmasına Ehtiyac Yoxdur - Bağlı siyahılar üçün yaddaşı əvvəlcədən ayırmağa ehtiyac yoxdur. Lazım olan düyünlər real vaxtda yaradılır.	Geriyə keçid (backward traversal) məhdudiyyətləri - Tək istiqamətli bağlı siyahılar yalnız irəli hərəkət etmək üçün nəzərdə tutulub. Geriyə keçid üçün siyahını tərsinə çevirmək və ya ikili bağlı siyahılardan (Doubly Linked List) istifadə etmək lazımdır.
Keş Performansı (Cache Locality) Problemi - Bağlı siyahılar yaddaşda dağınıq saxlanıldığı üçün keş performansı aşağı ola bilər.	-

Linked Listdən real həyatda istifadə halları

Musiqi Pleylistləri - Hər bir mahnı bir düyün kimi saxlanılır və növbəti mahnıya keçid mövcuddur.
Brauzer Tarixi - Brauzerlər istifadəçilərin gəzdiyi səhifələri bağlı siyahı şəklində saxlayır.
Tapşırıq Siyahıları (Task List) - Tapşırıqlar asanlıqla əlavə və silinə bilir.
Undo/Redo Funksionallığı - Bağlı siyahılar istifadəçilərin etdiyi dəyişiklikləri geri qaytarmaq üçün istifadə olunur.
Fayl Sistemləri - Faylların və qovluqların idarə olunmasında tək istiqamətli bağlı siyahılardan istifadə edilə bilər.
Simvol Cədvəlləri (Symbol Tables) - Proqramlaşdırma dillərinin kompilyatorlarında istifadə olunur.
Növbə Strukturları (Queue Data Structures) - İşlənəcək elementlərin idarə edilməsi üçün sıralama strukturu olaraq tətbiq edilir.
GPS Naviqasiya Sistemləri - İstiqamət və marşrutların saxlanması üçün bağlı siyahılardan istifadə olunur.
Log Faylları - Sistem hadisələri bağlı siyahılar şəklində saxlanıla bilər.
Sosial Media Lentləri - Postlar tək istiqamətli bağlı siyahı şəklində saxlanılır.
Şəbəkə Paket Növbələri - Şəbəkə protokolları paketin ötürülməsini bağlı siyahı kimi idarə edə bilər.
Versiya Nəzarət Sistemləri (Git) - Hər bir commit bir düyün kimi saxlanılır.

JavaScript-də tək istiqamətli əlaqəli listlərin implementasiyası

Əsas classlar (Base Classes)

Node classı hər bir düyünün dəyərini və növbəti düyünə keçidi saxlayır.
LinkedList classı isə siyahını idarə etmək üçün istifadə olunur.

class Node {
    constructor(value) {
        this.val = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

Siyahıya əlavə (Push) - O(1)

push(value) {
    const newNode = new Node(value);

    if (!this.head) {
        this.head = newNode;
    } else {
        this.tail.next = newNode;
    }

    this.tail = newNode;
    this.length++;
    return this;
}

Sonuncu düyünü silmə (Pop) - O(n)

pop() {
    if (!this.length) return undefined;

    let current = this.head;
    let newTail = current;

    while (current.next) {
        newTail = current;
        current = current.next;
    }

    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    return current;
}

Başlanğıcdan silmə (Shift) - O(1)

shift() {
    if (!this.length) return undefined;

    let current = this.head;
    this.head = current.next;
    this.length--;

    return current;
}

Başlanğıca əlavə (Unshift) - O(1)

unshift(value) {
    const newNode = new Node(value);

    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head = newNode;
    }

    this.length++;
    return this;
}

Verilən düyünü tapmaq (Get) - O(n)

get(index) {
    if (index < 0 || index >= this.length) return null;

    let current = this.head;
    let counter = 0;

    while (counter !== index) {
        current = current.next;
        counter++;
    }

    return current;
}

Düyünün dəyərini dəyişmək (Set) - O(n)

set(value, index) {
    const foundNode = this.get(index);
    if (!foundNode) return false;

    foundNode.val = value;
    return true;
}

Siyahını tərsinə çevirmək (Reverse) - O(n)

reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let prev = null;
    let next;

    while (node) {
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
    }

    return this;
}

Bu yazıda Tək istiqamətli əlaqəli listlərin (Singly Linked List) əsaslarını, üstünlüklərini, istifadələrini və JavaScript-də implementasiyasını öyrəndik. Bu mövzunu daha dərindən başa düşmək üçün fərqli alqoritmlərlə test etmək və real layihələrdə tətbiq etmək tövsiyə olunur.

codex

AzePUG-dan möhtəşəm izahı. Düşünürəm bundan daha geniş izahını tapmaq çətin olar.

Data_Structures_Algo_Python/book/3.Birtərəfli_Əlaqəli_listlər_singly_linked_lists.md at master · AzePUG/Data_Structures_Algo_Python

Azərbaycan dilində "Data strukturları və Alqoritmlər" mövzusunda Open Source kitab. - Data_Structures_Algo_Python/book/3.Birtərəfli_Əlaqəli_listlər_singly_linked_lists.md at master · AzePUG/Data_Structures_Algo_Python

GitHub (github.com)