単一リンクリストの実装

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

単一リンクリストについて

リンク リストは、ノードのシーケンスを表すデータ構造です。単一リンク リストでは、各ノードは次のノードを指します。

インデックス付けに依存していないため、メモリ内でこれらのノードを連続して (互いに隣接して) 並べ替える必要はありません。リンクされたリストを反復処理する場合、null ポインターに到達するまで、ノードの各 参照 を通過します。

ノードの構造

単一リンクリストでは、通常、各ノードには 2 つのフィールドが含まれます。

• data: ノード
に含まれる値または情報
• next: リスト内の次のノードへの参照 (ポインタ)

ヘッドポインタとテールポインタ

ヘッドは、リストの最初のノードへの参照です。これは、リンクされたリストの先頭にアクセスできるようにするために不可欠です。先頭への挿入などの操作を簡単にするために、センチネル ノード (実際のヘッド ノードの前に配置) として機能することがあります。末尾はリストの最後のノードへの参照です。次のポインタは null で、リストの終わりを示します。

挿入/削除のメモリ効率

配列と比較すると、リンク リストは要素の「移動」を必要としないため、挿入/削除の点でメモリ効率が高くなります。リンクされたリスト内の任意の場所に要素を追加または削除する操作には がかかります $O(1)$O(1) 時間。ただし、かかります $O(n)$O(n) 最悪の場合、リンク リストをたどって要素を追加または削除するのに時間がかかります (最初の要素の追加または削除には適用されません)。

リンクされたリストには、各ノードにデータとともにポインターが格納されるため、余分なメモリ オーバーヘッドがあることを指摘する価値があります。

時間計算量の分析

挿入:

• 先頭または末尾 (頭/尾ポインタ付き) → $O(1)$O(1)
• 特定の位置 (トラバースのため) → $O(n)$O(n)

削除:

• 冒頭→ $O(1)$O(1)
• 最後に→ $O(n)$O(n)
• 特定の位置 → $O(n)$O(n)

トラバーサル/検索: $O(n)$O(n)

JavaScriptの実装

古典的なOOP

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

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;
};

以上が単一リンクリストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。