データ構造の連結リストって何ですの？

Leetcodeをやっている中で連結リストというのに遭遇したんですけど、これまで1回も実務で見たことがなかったので、今回ちゃんと調べていこうとおもいます。

概要

めちゃくちゃザックリいうと、配列と似てるんですけど、配列の弱みを補ってくれるデータ構造なんです。
配列のデメリットは以下の通りです。

• サイズが固定されていて静的なデータ構造であること
• 要素が連続したメモリに格納されるため、挿入処理と削除処理にコストがかかる

2個目の挿入処理と削除処理にコストがかかるというのは、どういうことかというと、例えば以下のJavaScriptのコードで、shiftメソッドを使ったとしましょう

var array = [1, 3, 4, 5, 6, 8]
array.shift()
console.log(array)
// [3, 4, 5, 6, 8]

この処理を行うと、配列から1が消えて、それぞれの要素が左詰めになるように処理がされますね。そしてアドレスもそれによって変わるので、これが1000個とかあったらかなりのコストがかかりますね。popメソッドも同じです。それを解決するのが連結リストです。

連結リストのイメージは以下の画像のようなイメージです。

【参考資料】

連結リストにはそれぞれNodeというのがあって、そこに値とポインタというのがセットになっています。
先ほどの画像を見てみると分かるとおもいますが、Node1には14という数字があって、次に参照するNode2の参照場所の2つを持っているんです。こうすることで挿入処理が配列よりコスパがよくできます。
Node1の次に新しい要素を加えたいとき、Node1のポインタに次の参照場所を変更すれば済むだけの話なので簡単ですね。

実際に連結リストのコードをJavaScriptで書いてみます。

var head;

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

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

let list = new LinkedList(node1)
console.log(list)
//   LinkedList {
//      head: ListNode { data: 2, next: ListNode { data: 5, next: null } }
//   }

上記のコードで連結リストが作成することができます。

挿入するメソッド

一例として挿入するメソッドを以下に記述していきます。

function insert(prev_node, new_node){
    var new_node = new ListNode(new_node);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
}

insert(node1, 8)

// LinkedList {
//  head: ListNode { data: 2, next: ListNode { data: 8, next: ListNode { data: 5, next: null } } }
// }

【参考資料】