配列と連結リストの違いを学んで説明しようとしたのですが「せっかくだから実際の実装から取ってこようぜ」という欲を出した結果コードリーディング力が問われて挫折することに……。
配列と連結リストの違い
配列は定規のメモリに名札がついているイメージ。
連結リストは鎖に名札がついているイメージ。
配列（固定長の基本的なやつ）は宣言した長さのメモリを確保して、indexから決まるメモリアドレスにアクセスします。
連結リストは要素それぞれが前後の要素のアドレスを持ち、たどるようにアクセスします。リスト構造体は始点と長さを持ちます。
それゆえ、連結リストは切り貼りしたりずらしたりに強く、配列は弱い。
逆にindexが重要となる場合には配列のほうが得意、という特徴があります。
以下、Goのソースコードでチェックしようとして挫折した原因。
Goのソースコードを読み解いていきましょう。
連結リスト
containers/list/list.goにあります。
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value interface{}
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
解説
連結リストは簡単に見つかります。
省略していますが各構造体に適切なメソッドが実装されています。
配列
問題だったのは配列の方です。
考えればわかることだし、調べればすぐ気がつくのですが、配列は言語仕様です。
つまり、構文解析とか評価とかあのあたりのコンパイラの概念を理解した上で探さなければたどり着けません。
一度始めたからにはやるっきゃないと今日一日時間の許す限り探しましたが、到達できませんでした……。
Goの内部構造に興味をもつ良い機会でした。
コンパイラを学びながら調べるのを続けます。