クラスによる連結リストの実装

クラス定義コード

クラス定義コードのリストは、dlnode クラスの概要を参照してください。

クラスを使用するには、@dlnode というフォルダーを作成して、dlnode.m をこのフォルダーに保存します。@dlnode の親フォルダーは、MATLAB^® パス上になければなりません。または、dlnode.m をパスフォルダーに保存します。

`dlnode` クラスの設計

dlnode は二重連結リストを作成するクラスで、このリストの各ノードは以下を含みます。

データ配列
次のノードへのハンドル
前のノードへのハンドル

それぞれのノードには、そのノードに以下を行うことができるメソッドがあります。

連結リストの指定されたノードの前に挿入する
連結リストの特定のノードの後に挿入する
リストから除去する

クラスプロパティ

dlnode クラスは、各ノードを、以下の 3 つのプロパティをもつハンドルオブジェクトとして実装します。

Data — ノードのデータを含みます
Next — リスト内の次のノードのハンドルを含みます (SetAccess = private)
Prev — リスト内の前のノードのハンドルを含みます (SetAccess = private)

次の図は、3 つのノード n1、n2、n3 をもつリストを示します。これは、ノードが前後の各ノードを参照する様子も示しています。

Three nodes of a doubly linked list

クラスメソッド

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	dlnode クラスの設計連結リストにハンドルクラスを使用する理由ハンドルクラスと値クラスの比較
properties Data end	dlnode クラスの設計
properties (SetAccess = private) Next = dlnode.empty Prev = dlnode.empty end	プロパティの属性: `SetAccess`. これらのプロパティを `empty` の `dlnode` オブジェクトに初期化します。プロパティについての一般情報は、プロパティ構文を参照してください。
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 つのノードを連結します。`Next` および `Prev` プロパティに適切な値を代入します。ノードの挿入
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 つのノードを連結します。このメソッドは、`Next` および `Prev` プロパティに適切な値を代入します。ノードの挿入を参照してください。
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	ノードを削除して、残りのノードが正しく繋がるようにリストを修正します。`node` 引数はスカラーでなければなりません。ノードへの参照がなくなると、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 はノードを削除する前にクラスデストラクター (`delete` メソッドを参照) を呼び出します。
methods (Access = private) function delete(node) clearList(node) end	クラスデストラクターメソッド。MATLAB は `delete` メソッドを呼び出して、まだリストに接続されているノードを削除します。
end end	プライベートメソッドの終端およびクラス定義の終端

クラスコードの拡張

classdef dlnode < handle
   % dlnode A class to represent a doubly-linked node.
   % Link multiple dlnode objects together to create linked lists.
   properties
      Data
   end
   properties(SetAccess = private)
      Next = dlnode.empty
      Prev = dlnode.empty
   end
   
   methods
      function node = dlnode(Data)
         % Construct a dlnode object
         if nargin > 0
            node.Data = Data;
         end
      end
      
      function insertAfter(newNode, nodeBefore)
         % Insert newNode after nodeBefore.
         removeNode(newNode);
         newNode.Next = nodeBefore.Next;
         newNode.Prev = nodeBefore;
         if ~isempty(nodeBefore.Next)
            nodeBefore.Next.Prev = newNode;
         end
         nodeBefore.Next = newNode;
      end
      
      function insertBefore(newNode, nodeAfter)
         % Insert newNode before nodeAfter.
         removeNode(newNode);
         newNode.Next = nodeAfter;
         newNode.Prev = nodeAfter.Prev;
         if ~isempty(nodeAfter.Prev)
            nodeAfter.Prev.Next = newNode;
         end
         nodeAfter.Prev = newNode;
      end
      
      function removeNode(node)
         % Remove a node from a linked list.
         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
      
      function clearList(node)
         % Clear the list before
         % clearing list variable
         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
   end
   
   methods (Access = private)
      function delete(node)
         clearList(node)
      end
   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;
```

New node inserted into doubly linked list

ノードの除去

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;

Disconnecting links after removing a node from doubly linked list

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 はそのノードを破棄します。

Reconnecting links after deleting node from doubly linked list

リストの削除

連結リストを作成し、たとえば、リストの先頭または末尾が含まれる変数を割り当てる場合、その変数がクリアされると、デストラクターによってリスト全体に再帰処理が行われます。リストの規模が大きい場合、リストの変数がクリアされると、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: []