連結リストと配列の違い

連結リストはアドレスが隣り合っているとは限らない！！

連結リストの次の要素に（現在の要素のポインタ++）でアクセスしようとするとずっとオーバーフローが起きていたのでなんでかなーと思っていたら、連結リストの各要素のアドレスが隣り合っていないことが原因でした！！

今まで配列で次の要素にアクセスする時にポインタのアドレスを一つ動かすことでアクセスできていたので、連結リストもそれでいけると思っていたら違いました。

配列は各要素のアドレスがぎっしり隙間なく並んでいるのに対して、連結リストでは次の要素のアドレスを指しているだけでそのアドレスが隣にあるとは限らない。

だから、配列ではポインタのポインタつまり二次元配列で表されるのに対して、連結リストでは一次元の構造体の連なりで表される。

だから、配列とは違って初めから全要素分のメモリを確保する必要がなくなるし、後から新たな要素を追加したいと思っても次の要素を指すポインタを新たな要素に変更して新たな要素の指すポインタを前の要素のポインタが元々指していた場所にするだけで追加できる。

配列と絵連結リストのメモリの位置のイメージは下記事を参照。
https://qiita.com/tsudaryo1715/items/12c4848028716ab015bb