Main Content

このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

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

クラス定義コード

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

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

dlnode クラスの設計

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

  • データ配列

  • 次のノードへのハンドル

  • 前のノードへのハンドル

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

  • 連結リストの指定されたノードの前に挿入する

  • 連結リストの特定のノードの後に挿入する

  • リストから除去する

クラス プロパティ

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

  • Data — ノードのデータを含みます

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

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

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

クラス メソッド

dlnode クラスは、以下のメソッドを実装します。

  • dlnode — ノードを作成し、Data プロパティへの入力として渡された値を割り当てます

  • insertAfter — 指定したノードの後にノードを挿入します

  • insertBefore — 指定したノードの前にノードを挿入します

  • removeNode — このノードをリストから除去し、残りのノードを再接続します

  • clearList — 長いリストを効率的に除去します

  • delete — リストを削除する場合に MATLAB によって呼び出されるプライベート メソッドです

二重連結リストの作成

dlnode クラス コンストラクターにノードのデータを渡すことによって、ノードを作成します。たとえば、以下のステートメントは、123 のデータ値をもつ 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

ここで、xn2 を代入します。

x = n2;

すると、次の 2 つの等式が true になります。

x == n1.Next
x.Prev == n1

しかし、ノードの各インスタンスは 1 つしかないので、n1.Next に等しく、Prev プロパティに n1 へのハンドルを含むという条件を満たすリストには、ノードが 1 つに限られます。したがって、x は同じノードを n2 としてポイントしなければなりません。

複数の変数が同じオブジェクトを参照する方法が必要になります。MATLAB の handle クラスは、xn2 の両方が同じノードを参照する手段を提供します。

ハンドル クラスが eq メソッド (ハンドル クラス メソッドをリストするために、methods('handle') を使用) を定義し、これによりすべてのハンドル オブジェクトに == 演算子が使用できるようになります。

関連情報

ハンドル クラスについての詳細は、ハンドル クラスと値クラスの比較を参照してください。

dlnode クラスの概要

この節では dlnode クラスの実装について説明します。

コード例説明
classdef dlnode < handle

dlnode クラスの設計

連結リストにハンドル クラスを使用する理由

ハンドル クラスと値クラスの比較

   properties
      Data
   end
dlnode クラスの設計
   properties (SetAccess = private)
      Next = dlnode.empty
      Prev = dlnode.empty
   end

プロパティの属性: SetAccess.

これらのプロパティを emptydlnode オブジェクトに初期化します。

プロパティについての一般情報は、プロパティ構文を参照してください。

   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  

プライベート メソッドの終端およびクラス定義の終端

 クラス コードの拡張

クラス プロパティ

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 つ (insertAfterinsertBefore) あります。これらのメソッドは同様の動作を実行するので、この節では 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 メソッドを呼び出します。次に、insertAfternewNode Next プロパティと Prev プロパティを、リスト内の newNode の位置の前後にあるノードのハンドルに割り当てます。

たとえば、n1—n2—n3 を含むリストにおいて、既存のノード n1 の後に新規のノード nnew を挿入するものとします。

最初に、nnew を作成します。

nnew = dlnode(rand(3));

次に、insertAfter を呼び出して、n1 の後で nnew をリストに挿入します。

nnew.insertAfter(n1)

insertAfter メソッドは、n1n2 の間のリストで nnew を挿入するために、以下のステップを実行します。

  • nnew.Nextn1.Next (n1.Nextn2) に設定します。

    nnew.Next = n1.Next;
  • nnew.Prevn1 に設定します。

    nnew.Prev = n1;
  • n1.Next が空でない場合、n1.Next は依然として n2 であり、n1.Next.Prevn2.Prev なので nnew に設定されます。

    n1.Next.Prev = nnew;
  • n1.Next は次に設定されます。 nnew

    n1.Next = nnew;

ノードの除去

removeNode メソッドはリストからノードを削除し、残りのノードを再接続します。insertBeforeinsertAfter メソッドは、リンクされたリストに接続を試みる前に、常に、挿入するノードに 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;

removeNoden2 をリストから削除し、残りのノードを次の手順で再接続します。

n1 = n2.Prev;
n3 = n2.Next;
if n1 exists, then
   n1.Next = n3;
if n3 exists, then
   n3.Prev = n1

n1n3 に接続し、n3n1 に接続しているので、リストは再結合しています。最終手順は、n2.Nextn2.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 によって削除されていないノードは、明示的な参照が存在するノードのみです。この場合の参照は、headnextNode です。

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: []

関連するトピック