Melaksanakan Senarai Berpaut Tunggal

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

Memahami Senarai Berpaut Tunggal

senarai terpaut ialah struktur data yang mewakili jujukan nod. Dalam senarai terpaut tunggal, setiap nod menghala ke nod seterusnya.

Dalam ingatan, nod ini tidak perlu diisih secara bersebelahan (bersebelahan antara satu sama lain) kerana kami tidak bergantung pada pengindeksan. Apabila kita melelar melalui senarai terpaut, kita melalui setiap rujukan nod sehingga kami menekan penuding null.

Struktur Nod

Dalam senarai pautan tunggal, setiap nod biasanya mengandungi dua medan:

• data: nilai atau maklumat yang terkandung dalam nod
• seterusnya: rujukan (penunjuk) ke nod seterusnya dalam senarai

Penunjuk Kepala dan Ekor

kepala ialah rujukan kepada nod pertama dalam senarai. Ia penting kerana ia membenarkan akses kepada permulaan senarai terpaut. Ia kadangkala bertindak sebagai nod sentinel (diletakkan sebelum nod kepala sebenar) untuk operasi yang lebih mudah seperti memasukkan di kepala. Ekor adalah rujukan kepada nod terakhir dalam senarai. Penunjuk seterusnya adalah batal yang menunjukkan penghujung senarai.

Kecekapan Memori Sisipan/Pemadaman

Berbanding dengan tatasusunan, senarai terpaut adalah lebih cekap memori dari segi sisipan/pemadaman kerana operasi ini tidak memerlukan "perubahan" elemen. Operasi menambah atau mengalih keluar elemen dari mana-mana sahaja dalam senarai terpaut mengambil masa $O(1)$O(1) masa. Walau bagaimanapun, ia memerlukan $O(n)$O(n) masa dalam kes terburuk untuk melintasi senarai terpaut untuk kemudian menambah/mengalih keluar elemen (tidak terpakai untuk menambah/mengalih keluar elemen pertama).

Perlu diingatkan bahawa senarai terpaut mempunyai overhed memori tambahan kerana penyimpanan penunjuk bersama-sama dengan data dalam setiap nod.

Analisis Kerumitan Masa

Sisipan:

• pada permulaan atau akhir (dengan penunjuk kepala/ekor) → $O(1)$O(1)
• pada kedudukan tertentu (kerana traversal) → $O(n)$O(n)

Pemadaman:

• pada permulaan → $O(1)$O(1)
• pada akhir → $O(n)$O(n)
• pada kedudukan tertentu → $O(n)$O(n)

Perjalanan/Cari: $O(n)$O(n)

Pelaksanaan JavaScript

OOP klasik

class ListNode {
    constructor(val, nextNode = null) {
        this.val = val;
        this.next = nextNode;
    }
}

class LinkedList {
    constructor() {
        // sentinel node for easy operations on head
        this.head = new ListNode(-1);
        this.tail = this.head;
    }

    // get the value at the specified index.
    get(index) {
        let curr = this.head.next;
        let i = 0;
        while (curr !== null) {
            if (i === index) return curr.val;
            curr = curr.next;
            i++;
        }
        return -1;
    }

    // insert a new value at the head of the list.
    insertHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (newNode.next === null) {
            this.tail = newNode;
        }
    }

    // insert a new value at the tail of the list.
    insertTail(val) {
        const newNode = new ListNode(val);
        this.tail.next = newNode;
        this.tail = newNode;
    }

    // remove the node at the specified index.
    remove(index) {
        let curr = this.head;
        let i = 0;
        while (i < index && curr.next !== null) {
            i++;
            curr = curr.next;
        }

        if (curr !== null && curr.next !== null) {
            if (curr.next === this.tail) this.tail = curr;
            curr.next = curr.next.next;
            return true;
        }
        return false;
    }

    // get all values in the list as an array.
    getValues() {
        const values = [];
        let curr = this.head.next;
        while (curr !== null) {
            values.push(curr.val);
            curr = curr.next;
        }
        return values;
    }

    // get the length of the list.
    length() {
        let length = 0;
        let curr = this.head.next;
        while (curr !== null) {
            length++;
            curr = curr.next;
        }
        return length;
    }
}

OOP berfungsi

function ListNode(val, nextNode = null) {
    this.val = val;
    this.next = nextNode;
}

function LinkedList() {
    this.head = new ListNode(-1); // Sentinel node
    this.tail = this.head;
}

// get the value at the specified index
LinkedList.prototype.get = function(index) {
    let curr = this.head.next;
    let i = 0;
    while (curr !== null) {
        if (i === index) return curr.val;
        curr = curr.next;
        i++;
    }
    return -1;
};

// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head.next;
    this.head.next = newNode;
    if (newNode.next === null) {
        this.tail = newNode;
    }
};

// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
    const newNode = new ListNode(val);
    this.tail.next = newNode;
    this.tail = newNode;
};

// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
    let curr = this.head;
    let i = 0;
    while (i < index && curr.next !== null) {
        i++;
        curr = curr.next;
    }

    if (curr !== null && curr.next !== null) {
        if (curr.next === this.tail) this.tail = curr;
        curr.next = curr.next.next;
        return true;
    }
    return false;
};

// get all values in the list as an array
LinkedList.prototype.getValues = function() {
    const values = [];
    let curr = this.head.next;
    while (curr !== null) {
        values.push(curr.val);
        curr = curr.next;
    }
    return values;
};

// get the length of the list
LinkedList.prototype.length = function() {
    let length = 0;
    let curr = this.head.next;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }
    return length;
};

Atas ialah kandungan terperinci Melaksanakan Senarai Berpaut Tunggal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!