リスト構造

ハッシュテーブルを作る際に、ハッシュ値が被った時の処理を考えると、
自由に要素を追加可能なデータ構造が欲しくなるよね

こんなかんじの
list[0]:〇→〇
list[1]:〇→〇→〇
list[2]:〇
list[3]:〇→〇
list[4]:〇→〇→〇
list[5]:〇
list[6]:〇→〇
list[7]:〇

そうだ、そんなときはリスト構造を使おう！
リスト構造は、データをアドレスでつないだ構造をしています。
一番オーソドックスなリスト構造（単方向リスト）
h:head
t:tail
　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ]

データ単体は以下のような形になります。

 118　　　　　　　アドレス　　
[ 9 ]→NULL      [ データ値]→NULL
　　　　　　　　　　　　　　　↑Next（次のデータのアドレス、初期値はNULL）

• NULL:
  • 何も指さないアドレス。数値みたいに0とかで初期化しようと思っても、0番地にもデータが入ってるかもしれないので、0は使えない。。。
  • そのために、どこにも属してないよってアドレスを表すものが必要。ってことで用意されたのがNULL

リスト型のデータを1個だけ作ると、どこかのアドレスにこんな感じのデータが１個作られます。

 アドレス　　
[ データ値]→NULL
　　　　　 ↑Next（次のデータのアドレス、初期値はNULL）

たとえば、アドレス0x022にデータが作られて、データ値を3で初期化して使おうとすると以下のようになります。

値は
 022　　
[ 3 ]→NULL
　　　　　 ↑Next（次のデータのアドレス、初期値はNULL）

ここから書きかけ

　head:ヘッド（データがここからつなっていく、「はじめ」を表すデータのアドレス）
  tail:テール（データの終わりを表すでーたのアドレス）
　データ：　アドレス部　データ部 ネクス部 でできているよ
　　アドレス部：データ自身のアドレス
　　　データ部：格納したい値
　　ネクスト部：次のデータのアドレス

　整数 [ 1,3,5,7 ] がリストになっているイメージ
　h→1→3→5→7→t
  アクセス法
　①headのデータアドレスを取得
  ②headのnextを見る（最初のデータにアクセスできる）
　③nextのデータのnextを見る（次のデータにアクセスできる）
　④　…
　⑤nextがtailになったらそれ以上データはないよ
　
　今見ているアドレスを変数にしてたどっていく
   031     013     A15     FF2     109     BAD   アドレス（16進）
　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ]
       013     A15     FF2     109     BAD
　         ↑iterator
　Crr = head
  if(Crr.next != tail)
         Crr = Crr.next
	 if(crr.data == 5)5の時の処理
データの追加
   031     013     A15     FF2     109     BAD   アドレス（16進）
　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ]
       013     A15     FF2     109     BAD

　headとtailのアドレスは知っているとき、
　リスト構造のデータを用意 整数データ 9 を追加 
　 118
　[ 9 ]→NULL (NULLはどこにもつながっていないよというアドレス（数値でいう0））
　nextがtailになっているデータにつなぐ！
  if(Crr.next == tail)
     Crr.next = 118   (Crr:109 Crr.next:118)
     Crr = Crr.next   (Crr:118 Crr.next:NULL)
     Crr.next = tail  (Crr:118 Crr.next:tail)

呼ばれ方
ネットを見るといろいろ表記ゆれがありますが、基本的に以下のものは同じリスト構造を指します。

• リスト構造
• リンクリスト
• リンクトリスト
• 連結リスト
• リスト

リスト構造の種類

• 単方向リスト
  • リンクの方向が一方向に決まっているもの
  • 前方リンクと後方リンクがある
  • 単方向循環リスト
    • リンクの最後のデータと最初のデータが円環状につながっているもの、一方向にしかたどれない
    • 前方リンクと後方リンクがある
• 双方向リスト
  • リンクの方向が前後方向のもの、データをたどるときに1個前と1個先のデータへリンクされている
  • 双方向循環リスト
• 循環リスト

配列とリストの違い

#include <iostream>
#include <list>
using std::cout;
using std::cin;
using std::endl;
using std::list;

//STLのlistを使うよっていうinclude
//テンプレート（いろんな方に対応できる便利な奴）



int main() {
	//intのリストを作りたいな
	list<int> ilist;
	//floatのリストを作りたいな
	//list<float> flist;

	int indata;
	do{
		cout << "整数を入力：";
		cin >> indata;
		if(indata != -1)
			ilist.push_back(indata);
		else
			break;
	}while(true);
	
	list<int>::iterator theI = ilist.begin();
	cout << *theI << endl;  //*theI theIのアドレスの中身のデータを取り出す
	theI = std::next(theI); //theI++
	cout << *theI << endl;
	//cout << ilist[2] << endl; ランダムアクセスはできん！
}