Doubly Linked List məlumat strukturu

[codex]

İki istiqamətli bağlı siyahı (DLL) — hər bir elementi həm özündən əvvəlki, həm də özündən sonrakı elementə işarə edən iki göstərici ilə saxlayan xüsusi bir bağlı siyahı növüdür. Bu struktur elementlər arasında irəli və geri hərəkət etməyə imkan verir.

DLL, verilənlərin həm irəli, həm də geri istiqamətdə rahat idarə olunması üçün istifadə olunur.

DLL İstifadə Sahələri:

1. Mətn redaktorları – hər bir sətri node kimi saxlamaq və kursorla irəli-geri hərəkət etmək.
2. Undo/Redo funksionallığı – dizayn proqramlarında istifadə olunur.
3. Musiqi siyahıları – musiqilər arasında irəli və geri keçid.
4. Brauzer tarixi – əvvəlki və növbəti səhifələrə keçid.
5. Cache idarəsi – yaddaşda tez-tez istifadə olunan elementləri önə çəkmək.
6. Tapşırıq idarəetməsi – tapşırıqları asanlıqla əlavə/çıxarmaq və dəyişdirmək.
7. Verilənlər bazası idarəçiliyi – tranzaksiyaları izləmək və idarə etmək.
8. Real-time sistemlər – sabit və səmərəli yaddaş ayırması üçün.
9. Dinamik məlumat strukturları – deque, queue və s. üçün əsas struktur.

---

Tətbiq – JavaScript ilə DLL qurulması

Node və DoublyLinkedList classları

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

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

---

push(value) – Siyahının sonuna əlavə etmə (O(1))

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

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

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

  return this;
}

---

pop() – Siyahının sonundan element silmək (O(1))

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

  const current = this.tail;

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.tail = current.prev;
    this.tail.next = null;
    current.prev = null;
  }

  this.length--;
  return current;
}

---

shift() – Siyahının əvvəlindən element silmək (O(1))

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

  const current = this.head;

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = current.next;
    this.head.prev = null;
    current.next = null;
  }

  this.length--;
  return current;
}

---

unshift(value) – Siyahının əvvəlinə element əlavə etmək (O(1))

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

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

  this.length++;
  return this;
}

---

get(index) – İndeksə görə elementi əldə etmək (O(n))

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

  let count, current;

  if (index <= this.length / 2) {
    count = 0;
    current = this.head;
    while (count !== index) {
      current = current.next;
      count++;
    }
  } else {
    count = this.length - 1;
    current = this.tail;
    while (count !== index) {
      current = current.prev;
      count--;
    }
  }

  return current;
}

---

set(value, index) – İndeksə uyğun elementin dəyərini dəyişmək (O(n))

set(value, index) {
  const currentNode = this.get(index);
  if (currentNode) {
    currentNode.value = value;
    return true;
  }
  return false;
}

---

insert(value, index) – Müəyyən mövqeyə element əlavə etmək (O(n))

insert(value, index) {
  if (index < 0 || index > this.length) return false;
  if (index === 0) return this.unshift(value);
  if (index === this.length) return this.push(value);

  const newNode = new Node(value);
  const beforeNode = this.get(index - 1);
  const afterNode = beforeNode.next;

  beforeNode.next = newNode;
  newNode.prev = beforeNode;
  newNode.next = afterNode;
  afterNode.prev = newNode;

  this.length++;
  return true;
}

---

remove(index) – Müəyyən mövqedən elementi silmək (O(n))

remove(index) {
  if (index < 0 || index >= this.length) return false;
  if (index === 0) return this.shift();
  if (index === this.length - 1) return this.pop();

  const removedNode = this.get(index);
  removedNode.prev.next = removedNode.next;
  removedNode.next.prev = removedNode.prev;
  removedNode.next = null;
  removedNode.prev = null;

  this.length--;
  return removedNode;
}

---

🧠 Nəticə

Doubly Linked List – məlumatların idarəsini rahatlaşdıran və performans baxımından bir çox üstünlüyə sahib olan vacib məlumat strukturlarındandır. JavaScript-də bu strukturu sıfırdan qurmaq, həm nəzəri bilikləri praktikləşdirmək, həm də data strukturları sahəsində biliklərinizi möhkəmləndirmək üçün əla təcrübədir.

[codex]

Doubly Linked List-in Typescript-də full implementasiyası

// Node classı
class Node<T> {
  value: T; // Dəyər
  next: Node<T> | null; // Növbəti qovşağa işarə
  prev: Node<T> | null; // Əvvəlki qovşağa işarə

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// DLL classı
class DoublyLinkedList<T> {
  head: Node<T> | null; // Baş qovşaq
  tail: Node<T> | null; // Sonuncu qovşaq
  length: number; // Siyahının uzunluğu

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

  // Siyahının sonuna element əlavə etmək
  push(value: T): this {
    const newNode = new Node(value);
    if (!this.head) {
      // Siyahı boşdursa, həm head, həm tail eyni node olur
      this.head = newNode;
    } else {
      if (this.tail) {
        this.tail.next = newNode;
        newNode.prev = this.tail;
      }
    }
    this.tail = newNode;
    this.length++;
    return this;
  }

  // Siyahının sonundan element silmək
  pop(): Node<T> | undefined {
    if (!this.head) return undefined;

    const removed = this.tail!;
    if (this.length === 1) {
      // Siyahıda tək element varsa, hər ikisi də `null` olur
      this.head = null;
      this.tail = null;
    } else {
      this.tail = removed.prev;
      if (this.tail) this.tail.next = null;
      removed.prev = null;
    }
    this.length--;
    return removed;
  }

  // Siyahının əvvəlindən element silmək
  shift(): Node<T> | undefined {
    if (!this.head) return undefined;

    const removed = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = removed.next;
      if (this.head) this.head.prev = null;
      removed.next = null;
    }
    this.length--;
    return removed;
  }

  // Siyahının əvvəlinə element əlavə etmək
  unshift(value: T): this {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  // Verilmiş indeksə əsasən qovşağı əldə etmək
  get(index: number): Node<T> | null {
    if (index < 0 || index >= this.length) return null;

    let current: Node<T>;
    let count: number;

    // İndeks siyahının ortasından əvvəldirsə, başdan axtar
    if (index <= this.length / 2) {
      current = this.head!;
      count = 0;
      while (count !== index) {
        current = current.next!;
        count++;
      }
    } else {
      // Ortanı keçibsə, sondan axtar
      current = this.tail!;
      count = this.length - 1;
      while (count !== index) {
        current = current.prev!;
        count--;
      }
    }

    return current;
  }

  // Verilmiş indeksdəki qovşağın dəyərini dəyişmək
  set(index: number, value: T): boolean {
    const node = this.get(index);
    if (node) {
      node.value = value;
      return true;
    }
    return false;
  }

  // Verilmiş indeksə yeni qovşaq əlavə etmək
  insert(index: number, value: T): boolean {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return !!this.unshift(value);
    if (index === this.length) return !!this.push(value);

    const newNode = new Node(value);
    const before = this.get(index - 1);
    const after = before!.next;

    before!.next = newNode;
    newNode.prev = before;
    newNode.next = after;
    if (after) after.prev = newNode;

    this.length++;
    return true;
  }

  // Verilmiş indeksdəki qovşağı silmək
  remove(index: number): Node<T> | undefined {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const removed = this.get(index)!;
    const before = removed.prev!;
    const after = removed.next!;

    before.next = after;
    after.prev = before;

    removed.next = null;
    removed.prev = null;

    this.length--;
    return removed;
  }

  // Siyahını array kimi qaytarmaq (debug üçün)
  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

---

Jenny “bajı” qəşşəng başa salır. Baxmağa dəyər