Main Content

通过类实现链表

类定义代码

有关类定义代码列表，请参阅 dlnode 类概要。

要使用该类，请创建一个名为 @dlnode 的文件夹，并将 dlnode.m 保存到该文件夹中。@dlnode 的父文件夹必须位于 MATLAB® 路径上。或者，将 dlnode.m 保存到路径文件夹。

dlnode 类设计

dlnode 是用于创建双链表的类，其中每个节点均包含：

  • 数据数组

  • 下一个节点的句柄

  • 上一个节点的句柄

每个节点都有相应的方法，使该节点能够：

  • 插入到链表中的指定节点之前

  • 插入到链表中的特定节点之后

  • 从列表中删除

类属性

dlnode 类将每个节点实现为具有以下三个属性的句柄对象：

  • Data - 包含此节点的数据

  • Next - 包含列表中下一个节点的句柄 (SetAccess = private)

  • Prev - 包含列表中上一个节点的句柄 (SetAccess = private)

下图显示包含三个节点 n1、n2 和 n3 的列表。它还显示节点如何引用下一个节点和上一个节点。

Three nodes of a doubly linked list

类方法

dlnode 类实现以下方法：

  • dlnode - 构造一个节点，并将作为输入传递的值赋给 Data 属性

  • insertAfter - 在指定的节点之后插入此节点

  • insertBefore - 在指定的节点之前插入此节点

  • removeNode - 从列表中删除此节点，并重新连接其余节点

  • clearList - 高效删除大型列表

  • delete - 删除列表时 MATLAB 调用的私有方法。

创建双链表

通过将节点数据传递给 dlnode 类构造函数来创建节点。例如，以下语句将创建三个节点，分别包含数据值 1、2、3：

n1 = dlnode(1);
n2 = dlnode(2);
n3 = dlnode(3);

使用为此目的设计的类方法将这些节点构建为一个双链表：

n2.insertAfter(n1) % Insert n2 after n1
n3.insertAfter(n2) % Insert n3 after n2

现在，这三个节点就链接在一起了：

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

为什么要对链表使用句柄类？

每个节点都是唯一的，因为不可能有两个节点可以在同一个节点之前或之后。例如，节点对象 node 在其 Next 属性中包含下一个节点对象 node.Next 的句柄。同样，Prev 属性包含前一节点 node.Prev 的句柄。使用上一节中定义的三节点链表，您可以证实以下语句为 true：

n1.Next == n2
n2.Prev == n1

现在假设您将 n2 赋给 x：

x = n2;

则以下两个等式也为 true：

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

但是，由于节点的每个实例都是唯一的，因此列表中只有一个节点能够满足与 n1.Next 相等的条件，并且具有 Prev 属性，该属性包含 n1 的句柄。因此，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

将节点插入到双链表中指定节点之后，或者链接两个指定节点（如果还没有列表）。为 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

将节点插入到双链表中指定节点之前，或者链接两个指定节点（如果还没有列表）。此方法为 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

私有方法结束和类定义结束。

 展开类代码

类属性

只有 dlnode 类方法可以设置 Next 和 Prev 属性，因为这些属性具有私有 set 访问权限 (SetAccess = private)。使用私有 set 访问权限可以防止客户端代码使用这些属性执行任何不正确的操作。dlnode 类方法可对这些节点执行允许的所有操作。

Data 属性具有公共 set 和 get 访问权限，允许您根据需要查询和修改 Data 的值。

以下代码说明 dlnode 类如何定义这些属性：

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

构造节点对象

要创建节点对象，请将节点数据指定为构造函数的参量：

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

插入节点

可以通过两种方法在列表中插入节点 - 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 以将 nnew 插入到列表中 n1 的后面：

nnew.insertAfter(n1)

insertAfter 方法执行以下步骤，将 nnew 插入列表中的 n1 和 n2 之间：

  • 将 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

例如，假设您从三节点列表 (n1–n2–n3) 中删除 n2：

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

现在删除第三个节点（Data 属性的赋值为 3）：

removeNode(head.Next.Next)

现在，列表中第三个节点的数据值为 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 创建双链表

使用 NamedNode 类与使用 dlnode 类相似，不同之处在于您要为每个节点对象指定一个名称。例如： 

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

现在，使用从 dlnode 继承的插入方法来构建列表：

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

查询单个节点的属性时，会显示其名称和数据：

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

相关主题