Matlab中如何实现双向链表(Double Linked List)

Matlab中双向链表是基于matlab支持面向对象编程（OOP）的特性来实现的。基于这样的共识，来看一下具体是如何实现建立双向链表过程的。

Matlab建立了一个dlnode类专门用于创建双向链表，其中的每一个节点都包含了如下：

要想使用该类，必须要新建一个名为@dlnode的文件夹，将dlnode.m代码保存在该文件夹下，并且把它添加到matlab路径。

matlab的dlnode文件位于

Matlab derctory\help\techdoc\matlab_oop\examples\@dlnode

每一个节点中都赋予了相应的一些方法：

dlnode类将每一个节点当作句柄对象进行操作，每一个对象包含了如下三个特性：

下图展示了三个节点是如何相互引用的：

dlnode -- Construct a node and assign the value passed as an input to the Data property

insertAfter -- insert this node after the specified node

insertBefore -- insert this node before the sepecified node

removeNode -- Remove this node from list and reconnect the remainning nodes

clearList -- Romve large list efficiently

delete -- Privte meethod called by MATLAB when deleting the list

来看看具体是如何使用的：

通过将节点数据传给dlnode类构造器创建如下三个节点：

n1 = dlnode(1);

n2 = dlnode(2);

n3 = dlnode(3);

使用相应的类方法将上述三个节点放置于相应的双向链表当中：

n2.insertAfter(n1)    将节点n2插入到节点n1的后面

n3.insertAfter(n2)    将节点n3插入到节点n2的后面

基于此，三个节点就被链接起来了：

n1.Next指向n2，n2.Next.Prev指向n2，n1.Next.Next指向n3，n3.Prev.Prev指向n1

如果不是特别指出，你可能不会去想，为什么在链表的创建过程中需要用到句柄类？

假如将节点n2赋给x:

x = n2;

则下面的两个等式成立：

x == n1.Next

x.Prev == n1

但是在链表中，仅仅只能有一个节点满足与前一个结点之间的相互链接，因此对于x和n2来说，它们各自不能是一个具体的节点，只能是一个指向节点的变量。因此，必须要有一种方法，将多个变量指向同一个节点。句柄类能够提供这样的一个方法。

相关参考：Comparison of Handle and Value Classes.

classdef dlnode < handle

   properties
      Data
   end

 properties (SetAccess = private)
      Next = dlnode.empty;
      Prev = dlnode.empty;
   end

  methods

Construct a Node Object

  function node = dlnode(Data)
         if (nargin > 0)
            node.Data = Data;
         end
      end

Insert Nodes

    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

      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

Removing a Node From a List

      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

Delete the List

      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

 methods (Access = private)
      function delete(node)
         clearList(node)
      end

   end
end 

假如你想给创建的双向链表中每个节点都附上名字，那么就使用NameNode类，其定义如下：

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

用法与dlnode类似，举例：

n(1) = NamedNode('First Node',100);
n(2) = NamedNode('Second Node',200);
n(3) = NamedNode('Third Node',300);

n(2).insertAfter(n(1))
n(3).insertAfter(n(2))

在matlab的命令窗口中输入：

注意：必须要在所在的文件夹下新建@dlnode类文件夹，并且将dlnode.m文件放在该类文件夹下，否则会报没有定义相关类的错误：

DOUBLE linked 双向链表 matlab 链表 list