SLList

singly-linked list, 単方向連結リスト の略.

各ノードuは、データu.xと一つ後ろの要素を指す参照u.nextからなる。じゃんけん列車みたいな感じ。

classの実装が本格的に必要になってくる。

headとtailの参照を持っておくと、扱いが楽になる。tail.next = null になってる。

tailを消すのには時間がかかって、「単方向」連結リストなので、新しいtailの候補…一番後ろから2番目の要素を知るには前から順番にリストを辿らないといけない。

真ん中あたりの要素を見るだけでも、一番最初から順番に辿らないといけない。でも、「切る」「挿入する」みたいなのは素早く処理できる(左右の処理だけで済むので)。配列を使ったやつとは性質が割と反対。