M3 | WebDev

68 views18:29

Пост про связанные списки 📚

Связанный список — это абстрактная структура данных, позволяющая вставлять элементы в любую точку памяти за O(1) (константное время). Чтение элементов занимает O(n), где *n* — количество элементов в списке.

🧩 Основные компоненты связанного списка:

1. Узел (Node): Содержит значение и ссылку на следующий узел.
2. Заголовок (Head): Указывает на начало списка.
3. Хвост (Tail): Ссылка на последний узел, который ссылается на null.

✨ Двухнаправленный связанный список:

Имеет ссылки как на следующий, так и на предыдущий узлы, что облегчает навигацию в обе стороны.

📊 Сравнение массивов и связанных списков:

1. Хранение данных:

- Массив: Элементы массива хранятся в памяти последовательно, непрерывно. Это означает, что доступ к элементам массива по индексу осуществляется за константное время.

- Связанный список: Элементы связанного списка хранятся в разных участках памяти, связанных указателями. Для доступа к элементам требуется последовательно пройти по указателям от начала списка до нужного элемента, что делает доступ по индексу менее эффективным.

2. Размер и изменяемость:

- Массив: Размер массива фиксирован и определяется при создании. Изменение размера массива может потребовать перевыделения памяти и копирования элементов.

- Связанный список: Размер связанного списка может динамически меняться, поскольку элементы не обязательно должны быть хранены последовательно в памяти.

3. Вставка и удаление элементов:

- Массив: Вставка и удаление элементов из середины массива требует перемещения всех элементов после изменяемого, что может быть затратно по времени.

- Связанный список: Вставка и удаление элементов из середины списка требует только перенаправления указателей, что делает эти операции более эффективными.

4. Память:

- Массив: Массивы могут потреблять больше памяти, чем реально требуется, особенно если размер массива больше, чем количество используемых элементов.

- Связанный список: Связанные списки могут быть более эффективны в использовании памяти, поскольку они выделяют память только для фактически используемых элементов.

5. Сложность операций:

- Массив: В среднем доступ к элементу массива по индексу имеет сложность O(1), а вставка и удаление элементов в середине массива имеют сложность O(n), где n - размер массива.

- Связанный список: Доступ к элементу по индексу имеет сложность O(n), а вставка и удаление элементов в середине списка имеют сложность O(1).

Пример реализации на JavaScript:

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

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

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

        if (!this.head || !this.tail) {
            this.head = newNode;
            this.tail = newNode;
            return this;
        }

        this.tail.next = newNode;
        this.tail = newNode;
        return this;
    }

    prepend(value) {
        const newNode = new Node(value, this.head);
        this.head = newNode;

        if (!this.tail) {
            this.tail = newNode;
        }
        return this;
    }

    find(value) {
        if (!this.head) return null;
        let current = this.head;
        
        while (current) {
            if (current.value === value) return current;
            current = current.next;
        }
        return null;
    }

    insertAfter(value, prevNode) {
        if (prevNode === null) return this;
        const newNode = new Node(value);
        newNode.next = prevNode.next;
        prevNode.next = newNode;

        if (newNode.next === null) this.tail = newNode;
        return this;
    }
}

🎯 Где используются связанные списки?

- Связанные списки используются в реализациях различных алгоритмов и структур данных , когда важно избежать перевыделения памяти.

Тэги : #javascript #структурыданных

75 views19:01