chainとlinked list

chain2.GIF
chainは、ordered setと対応．
例えば，名簿，symbol table変換表，・・・
linkedlist.GIF
(a)は singly linled list．
(b)は doubly linked list．

chainはlinked listにより表現される事がある．
space.gif
line.gif
space.gif
一般に， linked list 処理系は
次の形：
（ リストの集合, 名前の集合; { insert, delete, search} ）
ここで
space.gif insert : L × N → L
space.gif delete : L × N → L
space.gif search : L × N → { T, F }

ただし，
space.gif L : リストの集合
space.gif N : NAMEの集合
space.gif
line.gif
space.gif
Linked list と，その上の演算の例．

例
名簿（alphabetical order）の表現．

（データの形式）
３種類の record を用いる．
i. "TABLE"は，次の record
tables.GIF
の集まり

ii. "AVAIL" は TABLE 内の使える record へのPOINTER
avails.GIF

iii. "TOP" は名簿の最初の NAME の入っている record へのPOINTER
tops.GIF

全体の形：
alls.GIF

（操作（基本操作））
ポインタのつけかえ，参照
NAMEの書きかえ，参照
space.gif
line.gif
space.gif
例
exa1.GIF
line.gif
exa2.GIF
line.gif
exa3.GIF
line.gif
exa4.GIF
space.gif
line.gif
space.gif
chain の表現例：比較
exa5.GIF
space.gif
line.gif
space.gif
exa6.GIF
space.gif
line.gif
space.gif
C1: 比較に要するtime
C2: ポインタのつけかえtime
C3: 書きかえtime
・ T(n) ≒n・C1 + C2 + C3 （最悪）
・ T(n) ≒log n ・C1 +n・C3（最悪）

WANGのsearch
T(n) ≒ log n・C1
C1 < C3