通用链表中的虚拟节点

Question

我在写链表。这是我的代码：

Linked_List.ads

generic
   type T is private;
package Linked_List is
   type Node;
   type NodeAccess is access Node;
   type Node is record
      Data : T;
      Next : NodeAccess := null;
   end record;
   type List is record
      Head : NodeAccess;
      Has_Dummy_Head : Boolean;
      Size : Integer;
   end record;
   type ListAccess is access List;
   function Get_New_List(Has_Dummy_Head : Boolean) return ListAccess;
private
   function Get_New_Node(Data : T; Next : NodeAccess) return NodeAccess;
end Linked_List;

Linked_List.adb

package body Linked_List is
   function Get_New_Node(Data : T; Next : NodeAccess) return NodeAccess is
      New_Node : NodeAccess := new Node;
   begin
      New_Node.all := (Data => Data, Next => Next);
      return New_Node;
   end Get_New_Node;
   function Get_New_List(Has_Dummy_Head : Boolean) return ListAccess is
      New_List : ListAccess := new List;
   begin
      if Has_Dummy_Head = True then
         New_List.all := (Head => Get_New_Node(Data => null, Next => null), Has_Dummy_Head => True, Size => 0);
      else
         New_List.all := (Head => null, Has_Dummy_Head => False, Size => 0);
      end if;
      return New_List;
   end Get_New_List;
end Linked_List;

当列表是虚拟头部时，我不知道如何添加头部（Has_Dummy_Head 是正确的）。我尝试将节点中的数据字段设置为空，但我没有用。我不知道如何获取一些类型 T 的值。

Answer 1

您可以尝试使用

Head => new Node'(Data => <>, Next => null)

而不是

Head => Get_New_Node(Data => null, Next => null)

（或者定义一个常量 Null_Node 或类似的常量）。

但一般来说，没有值往往表示包的组织存在缺陷。你真的需要一个假人头吗？为什么不简单地将 Head 指针设置为 null 呢？我知道出于性能原因，使用虚拟头可能会节省一些 if Head /= null then 测试，但您是否已经处于优化级别？

通用链表中的虚拟节点

dummy node in generic linked list

generics

ada

gnat