クラスによる連結リストの実装
クラス定義コード
クラス定義コードのリストは、dlnode クラスの概要を参照してください。
クラスを使用するには、@dlnode
というフォルダーを作成して、dlnode.m
をこのフォルダーに保存します。@dlnode
の親フォルダーは、MATLAB® パス上になければなりません。または、dlnode.m
をパス フォルダーに保存します。
dlnode
クラスの設計
dlnode
は二重連結リストを作成するクラスで、このリストの各ノードは以下を含みます。
データ配列
次のノードへのハンドル
前のノードへのハンドル
それぞれのノードには、そのノードに以下を行うことができるメソッドがあります。
連結リストの指定されたノードの前に挿入する
連結リストの特定のノードの後に挿入する
リストから除去する
クラス プロパティ
dlnode
クラスは、各ノードを、以下の 3 つのプロパティをもつハンドル オブジェクトとして実装します。
Data
— ノードのデータを含みますNext
— リスト内の次のノードのハンドルを含みます (SetAccess = private
)Prev
— リスト内の前のノードのハンドルを含みます (SetAccess = private
)
次の図は、3 つのノード n1
、n2
、n3
をもつリストを示します。これは、ノードが前後の各ノードを参照する様子も示しています。
クラス メソッド
dlnode
クラスは、以下のメソッドを実装します。
dlnode
— ノードを作成し、Data
プロパティへの入力として渡された値を割り当てますinsertAfter
— 指定したノードの後にノードを挿入しますinsertBefore
— 指定したノードの前にノードを挿入しますremoveNode
— このノードをリストから除去し、残りのノードを再接続しますclearList
— 長いリストを効率的に除去しますdelete
— リストを削除する場合に MATLAB によって呼び出されるプライベート メソッドです
二重連結リストの作成
dlnode
クラス コンストラクターにノードのデータを渡すことによって、ノードを作成します。たとえば、以下のステートメントは、1
、2
、3
のデータ値をもつ 3 つのノードを作成します。
n1 = dlnode(1); n2 = dlnode(2); n3 = dlnode(3);
この目的のために設計されたクラス メソッドを使用して、これらのノードを二重連結リストに構築します。
n2.insertAfter(n1) % Insert n2 after n1 n3.insertAfter(n2) % Insert n3 after n2
これで、3 つのノードがリンクされます。
n1.Next % Points to n2
ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]
n2.Next.Prev % Points back to n2
ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]
n1.Next.Next % Points to n3
ans = dlnode with properties: Data: 3 Next: [] Prev: [1x1 dlnode]
n3.Prev.Prev % Points to n1
ans = dlnode with properties: Data: 1 Next: [1x1 dlnode] Prev: []
連結リストにハンドル クラスを使用する理由
同じノードに対して前または次に成り得るのは 1 つのノードに限られるという点で、各ノードは固有です。
たとえば、node オブジェクト node
は、その Next
プロパティに次の node オブジェクト node.Next
のハンドルを含みます。同様に、Prev
プロパティは、前のノード node.Prev
のハンドルを含みます。前の節で定義した 3 つのノードを連結したリストを使用すると、以下のステートメントが true であることを説明できます。
n1.Next == n2 n2.Prev == n1
ここで、x
に n2
を代入します。
x = n2;
すると、次の 2 つの等式が true になります。
x == n1.Next x.Prev == n1
しかし、ノードの各インスタンスは 1 つしかないので、n1.Next
に等しく、Prev
プロパティに n1
へのハンドルを含むという条件を満たすリストには、ノードが 1 つに限られます。したがって、x
は同じノードを n2
としてポイントしなければなりません。
複数の変数が同じオブジェクトを参照する方法が必要になります。MATLAB の handle
クラスは、x
と n2
の両方が同じノードを参照する手段を提供します。
ハンドル クラスが eq
メソッド (ハンドル クラス メソッドをリストするために、methods('handle')
を使用) を定義し、これによりすべてのハンドル オブジェクトに ==
演算子が使用できるようになります。
関連情報
ハンドル クラスについての詳細は、ハンドル クラスと値クラスの比較を参照してください。
dlnode
クラスの概要
この節では dlnode
クラスの実装について説明します。
コード例 | 説明 |
---|---|
classdef dlnode < handle
| |
properties
Data
end | dlnode クラスの設計 |
properties (SetAccess = private)
Next = dlnode.empty
Prev = dlnode.empty
end
| プロパティの属性: これらのプロパティを プロパティについての一般情報は、プロパティ構文を参照してください。 |
methods | メソッドについての一般情報は、クラス設計でのメソッドを参照してください。 |
function node = dlnode(Data) if (nargin > 0) node.Data = Data; end end | 個別ノード (接続されていない) の作成に必要なのはデータのみです。 コンストラクターについての一般情報は、コンストラクターのガイドラインを参照してください。 |
function insertAfter(newNode, nodeBefore) removeNode(newNode); newNode.Next = nodeBefore.Next; newNode.Prev = nodeBefore; if ~isempty(nodeBefore.Next) nodeBefore.Next.Prev = newNode; end nodeBefore.Next = newNode; end | ノードを二重連結リスト内の指定されたノードの後ろに挿入するか、リストがない場合は、指定された 2 つのノードを連結します。 |
function insertBefore(newNode, nodeAfter) removeNode(newNode); newNode.Next = nodeAfter; newNode.Prev = nodeAfter.Prev; if ~isempty(nodeAfter.Prev) nodeAfter.Prev.Next = newNode; end nodeAfter.Prev = newNode; end | ノードを二重連結リスト内の指定されたノードの前に挿入するか、リストがない場合は、指定された 2 つのノードを連結します。このメソッドは、 ノードの挿入を参照してください。 |
function removeNode(node) if ~isscalar(node) error('Nodes must be scalar') end prevNode = node.Prev; nextNode = node.Next; if ~isempty(prevNode) prevNode.Next = nextNode; end if ~isempty(nextNode) nextNode.Prev = prevNode; end node.Next = = dlnode.empty; node.Prev = = dlnode.empty; end | ノードを削除して、残りのノードが正しく繋がるようにリストを修正します。 ノードへの参照がなくなると、MATLAB はそのノードを削除します。 |
function clearList(node) prev = node.Prev; next = node.Next; removeNode(node) while ~isempty(next) node = next; next = node.Next; removeNode(node); end while ~isempty(prev) node = prev; prev = node.Prev; removeNode(node) end end | リスト変数をクリアした結果としてデストラクターが再帰的に呼び出されるのを防ぎます。リスト全体をループして、各ノードを切断します。ノードに対する参照がなくなると、MATLAB はノードを削除する前にクラス デストラクター ( |
methods (Access = private) function delete(node) clearList(node) end | クラス デストラクター メソッド。MATLAB は |
end end | プライベート メソッドの終端およびクラス定義の終端 |
クラス プロパティ
Next
プロパティと Prev
プロパティはプライベートの SetAccess (SetAccess = private
) をもつので、これらのプロパティを設定できるのは dlnode
クラス メソッドのみです。プライベートの set アクセスを使用すると、クライアントのコードによるこれらのプロパティの不正確な操作を防ぐことができます。dlnode
クラス メソッドは、これらのノードで許可されているすべての演算を実行します。
Data
プロパティはパブリックの SetAccess と GetAccess をもつため、必要に応じて Data
の値を照会して変更することができます。
ここでは、dlnode
クラスによってプロパティが定義される方法を示します。
properties Data end properties(SetAccess = private) Next = dlnode.empty; Prev = dlnode.empty; end
node オブジェクトの作成
node オブジェクトを作成するには、node のデータを次のコンストラクターへの引数として指定します。
function node = dlnode(Data) if nargin > 0 node.Data = Data; end end
ノードの挿入
ノードをリストに挿入する方法は 2 つ (insertAfter
と insertBefore
) あります。これらのメソッドは同様の動作を実行するので、この節では insertAfter
のみを詳細に説明します。
function insertAfter(newNode, nodeBefore) removeNode(newNode); newNode.Next = nodeBefore.Next; newNode.Prev = nodeBefore; if ~isempty(nodeBefore.Next) nodeBefore.Next.Prev = newNode; end nodeBefore.Next = newNode; end
insertAfter
の機能. 最初に insertAfter
は、新しいノードが他のノードに接続されていないことを確認するために removeNode
メソッドを呼び出します。次に、insertAfter
は newNode
Next
プロパティと Prev
プロパティを、リスト内の newNode
の位置の前後にあるノードのハンドルに割り当てます。
たとえば、n1—n2—n3
を含むリストにおいて、既存のノード n1
の後に新規のノード nnew
を挿入するものとします。
最初に、nnew
を作成します。
nnew = dlnode(rand(3));
次に、insertAfter
を呼び出して、n1
の後で nnew
をリストに挿入します。
nnew.insertAfter(n1)
insertAfter
メソッドは、n1
と n2
の間のリストで nnew
を挿入するために、以下のステップを実行します。
nnew.Next
をn1.Next
(n1.Next
はn2
) に設定します。nnew.Next = n1.Next;
nnew.Prev
をn1
に設定します。nnew.Prev = n1;
n1.Next
が空でない場合、n1.Next
は依然としてn2
であり、n1.Next.Prev
はn2.Prev
なのでnnew
に設定されます。n1.Next.Prev = nnew;
n1.Next
は次に設定されます。nnew
n1.Next = nnew;
ノードの除去
removeNode
メソッドはリストからノードを削除し、残りのノードを再接続します。insertBefore
と insertAfter
メソッドは、リンクされたリストに接続を試みる前に、常に、挿入するノードに removeNode
を呼び出します。
removeNode
を呼び出すことにより、Next
または Prev
プロパティに割り当てる前に、ノードが既知の状態にあることが確認されます。
function removeNode(node) if ~isscalar(node) error('Input must be scalar') end prevNode = node.Prev; nextNode = node.Next; if ~isempty(prevNode) prevNode.Next = nextNode; end if ~isempty(nextNode) nextNode.Prev = prevNode; end node.Next = dlnode.empty; node.Prev = dlnode.empty; end
たとえば、n2
を 3 つのノードのリスト (n1–n2–n3
) から削除するとします。
n2.removeNode;
removeNode
は n2
をリストから削除し、残りのノードを次の手順で再接続します。
n1 = n2.Prev; n3 = n2.Next; if n1 exists, then n1.Next = n3; if n3 exists, then n3.Prev = n1
n1
は n3
に接続し、n3
は n1
に接続しているので、リストは再結合しています。最終手順は、n2.Next
と n2.Prev
がいずれも空である (つまり、n2
が接続されていない) ことの確認です。
n2.Next = dlnode.empty; n2.Prev = dlnode.empty;
リストからのノードの削除
10 個のノードをもつリストを作成し、リストの先頭にハンドルを保存するとします。
head = dlnode(1); for i = 10:-1:2 new = dlnode(i); insertAfter(new,head); end
ここで、3 番目のノード (3
の値が割り当てられた Data
プロパティ) を除去します。
removeNode(head.Next.Next)
これで、リストの 3 番目のノードはデータ値が 4
になります。
head.Next.Next
ans = dlnode with properties: Data: 4 Next: [1x1 dlnode] Prev: [1x1 dlnode]
さらに、前のノードは Data
値が 2
になります。
head.Next
ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]
ノードの削除
ノードを削除するには、該当のノードで removeNode
メソッドを呼び出します。removeNode
メソッドによってノードが切断され、リストが再接続された後に、MATLAB は除去されたノードを破棄します。他のノードの参照先となっていたノードが除去されて、リストが再接続されることで、MATLAB はそのノードを破棄します。
リストの削除
連結リストを作成し、たとえば、リストの先頭または末尾が含まれる変数を割り当てる場合、その変数がクリアされると、デストラクターによってリスト全体に再帰処理が行われます。リストの規模が大きい場合、リストの変数がクリアされると、MATLAB で再帰制限の超過が発生する可能性があります。
clearList
メソッドは、リストでループ処理を行って各ノードを切断することで、再帰を回避して大規模なリストを削除するパフォーマンスを向上させます。clearList
はリスト内の任意のノードのハンドルを受け入れ、残りのノードを除去します。
function clearList(node) if ~isscalar(node) error('Input must be scalar') end prev = node.Prev; next = node.Next; removeNode(node) while ~isempty(next) node = next; next = node.Next; removeNode(node); end while ~isempty(prev) node = prev; prev = node.Prev; removeNode(node) end end
たとえば、ノードが多数あるリストを作成するものとします。
head = dlnode(1); for k = 100000:-1:2 nextNode = dlnode(k); insertAfter(nextNode,head) end
変数 head
にはリストの先頭にあるノードへのハンドルが含まれています。
head
head = dlnode with properties: Data: 1 Next: [1x1 dlnode] Prev: []
head.Next
ans = dlnode with properties: Data: 2 Next: [1x1 dlnode] Prev: [1x1 dlnode]
clearList
を呼び出してリスト全体を除去することができます。
clearList(head)
MATLAB によって削除されていないノードは、明示的な参照が存在するノードのみです。この場合の参照は、head
と nextNode
です。
head
head = dlnode with properties: Data: 1 Next: [] Prev: []
nextNode
nextNode = dlnode with properties: Data: 2 Next: [] Prev: []
これらのノードは、変数をクリアすることで除去できます。
clear head nextNode
delete メソッド
delete
メソッドは単に clearList
メソッドを呼び出します。
methods (Access = private) function delete(node) clearList(node) end end
delete
メソッドはプライベートのアクセスをもち、ユーザーが単一のノードを削除する際に delete
を呼び出すことを防ぎます。リストが破棄される場合、MATLAB は暗黙的に delete
を呼び出します。
リストから単一ノードを削除するには、removeNode
メソッドを使用します。
dlnode
クラスの特化
dlnode
クラスは、二重連結リストを実装し、より特化したタイプの連結リストを作成する際に使いやすい始点を与えます。たとえば、リストを作成して、各ノードが名前をもつようにするとします。
dlnode
クラスの実装に使用するコードをコピーして拡張するのではなく、dlnode
から新しいクラス (つまり、dlnode
のサブクラス) を派生させることができます。dlnode
のすべての機能を備えたクラスを作成し、独自の追加機能も定義できます。さらに、dlnode
はハンドル クラスなので、この新しいクラスもハンドル クラスです。
NamedNode
クラスの定義
クラスを使用するには、@NamedNode
というフォルダーを作成して、NamedNode.m
をこのフォルダーに保存します。@NamedNode
の親フォルダーは、MATLAB パス上になければなりません。または、NamedNode.m
をパス フォルダーに保存します。
以下のクラス定義は、dlnode
クラスから NamedNode
クラスを派生する方法を表します。
classdef NamedNode < dlnode properties Name = '' end methods function n = NamedNode (name,data) if nargin == 0 name = ''; data = []; end n = n@dlnode(data); n.Name = name; end end end
NamedNode
クラスは、ノードの名前を保存する Name
プロパティを追加します。
コンストラクターは、dlnode
クラスのクラス コンストラクターを呼び出し、Name
プロパティに値を割り当てます。
NamedNode
を使用した二重連結リストの作成
各 node オブジェクトに名前を指定する場合以外は、dlnode
クラスのような NamedNode
クラスを使用します。以下に例を示します。
n(1) = NamedNode('First Node',100); n(2) = NamedNode('Second Node',200); n(3) = NamedNode('Third Node',300);
ここで、以下のリストを作成するために dlnode
から継承された insert メソッドを使用します。
n(2).insertAfter(n(1)) n(3).insertAfter(n(2))
1 つのノードは、そのプロパティをクエリするとき、その名前とデータを表示します。
n(1).Next
ans = NamedNode with properties: Name: 'Second Node' Data: 200 Next: [1x1 NamedNode] Prev: [1x1 NamedNode]
n(1).Next.Next
ans = NamedNode with properties: Name: 'Third Node' Data: 300 Next: [] Prev: [1x1 NamedNode]
n(3).Prev.Prev
ans = NamedNode with properties: Name: 'First Node' Data: 100 Next: [1x1 NamedNode] Prev: []