PHP：链表节点对象垃圾收集问题

Question

将第一个和最后一个节点对象标识符设置为 NULL 应该会导致链表内的所有节点对象立即自动垃圾回收，因为没有对包括第一个和最后一个节点在内的所有节点对象的引用。

 $this->first = NULL
 $this->last = NULL

我们是否需要遍历完整的链表并一一取消设置每个节点对象标识符？

我的信念是，将第一个和最后一个设置为 NULL 就足够了，PHP 会代表我们在后台进行垃圾收集。

如果我错了，请纠正我。

Answer 1

如果您运行 PHP <5.3.0 并且使用双向链表，则不会释放任何节点。这是因为早期的 PHP 版本仅使用引用计数 [1]，无法识别循环引用。即使在单链表中，垃圾收集器也可能需要“n”遍才能释放整个列表，具体取决于所使用的确切算法（尽管我认为这不太可能）。

进一步解释一下，在双向链表中，每个节点都指向它之前和之后的节点。考虑有序节点 A、B、C。这意味着 A 被指向，B、C 被 B 指向，B 被 A 和 C 指向。因此，它们的引用计数将始终非零，除非您自己明确地取消设置节点。

对于单向链表，相同的节点 A、B、C，每个节点都由前一个节点指向，除了 A 之外，没有其他节点指向它。因此，如果删除对 A 的引用，它将被垃圾收集。然后，由于 B 不再被指向，它将被释放，依此类推。但是，假设垃圾收集器以相反或随机顺序（而不是从左到右的最佳顺序）访问列表。然后，它可能首先查看 B 并得出结论 A 仍然指向它，因此不需要释放。然后 GC 释放 A 并完成。尽管如此，更有可能的是，GC 算法会不断地收集引用计数为零的内存，直到没有更多的东西可以收集，这样就可以避免这个问题。

值得庆幸的是，从 PHP 5.3.0 开始，我们不必担心循环引用 [2]。该算法的工作原理是从根内存节点构造一棵树。任何未包含在最终树中的内容都必须是孤立的（因此仅由于循环引用而保持活动状态），因此可以被释放。所以是的，只要程序中没有其他内容指向列表中的任何节点，就可以通过删除对开始和结束的引用来释放整个列表。

请注意，释放孤立循环引用的算法比简单的引用计数更昂贵。显式释放代码可能有好处，也可能没有好处。必须进行仔细的基准测试才能找到这一点。

• [1] http://www.php.net /manual/en/features.gc.refcounting-basics.php

• [2] http://www.php.net/manual/en/features.gc.collecting-cycles.php

Answer 2

有时我会遇到 PHP 垃圾收集过程的问题。

您可以在链表的实现中解决这个问题。

• 每次创建数据结构时，将其创建为函数中的局部变量，
  不是全球范围内的。稍后，分配到代码的其他部分，您将在其中使用它。
  如果直接分配变量，则可能有相同引用的副本，
  而不是具有相同数据的新结构。

• 我建议将“List”结构实现为独立结构，
  不仅仅是指向第一个或最后一个节点的指针。

• 对于链表，我添加了 2 个特殊节点，其工作方式类似于您的“第一个”和“第一个”。 “最后的”，
  不存储任何数据，并且永远不会被删除，除非整个链表，
  即将被删除。当列表为空时，它们相互链接，
  当添加真实数据节点时，它们被设置在这些节点之间。

• 当您删除第一个节点时，您不会删除特殊的“第一个”节点标记，而是删除特殊“第一个”标记之后的节点。

• 当您删除最后一个节点时，您不会删除特殊的“最后”节点标记，而是删除特殊“最后”标记之前的节点。

建议：

<?php

/* listitem */ function newitem($data)
{
    // executing a function that returns
    // a local variable,
    // forces php to create a new item, each time,
    // instead of making a copy,
    // that conflicts with garbage collection

    /* listitem var */ $Result = array(
      "data"  => $data,
      "prev"  => null,
      "next"  => null,
    );

    return $Result;
} // listitem function newitem(...)

/* linkedlist */ function newlist()
{
    // executing a function that returns
    // a local variable,
    // forces php to create a new item, each time,
    // instead of making a copy,
    // that conflicts with garbage collection

    /* linkedlist var */ $Result = array(
      "start" => newitem();   // <- "marker" for start of list, don't store data here
      "finish" => newitem();  // <- "marker" for end of list, don't store data here
    )

    return $Result;
} // linkedlist function newlist(...)

/* void */ function linkitem(&$before, &after)
{
  if (($before != null) && ($after != null))
  {
    "start" <=> "item"
    $before["next"] = $after; 
    $after["prev"]  = $before; 
  }
} // void function linkitem(...)

/* void */ function additem(&$list, &item)
{
  if ($item != null)
  {
    "start" <=> "item"
    linkitem(/* & */ $list["start"], /* & */ $item); 
    "item" <=> "finish"
    linkitem(/* & */ $item, /* & */ $list["start"]); 
  }
} // void function additem(...)

/* void */ function example()
{
  /* linkedlist var */ $SolarSystem = newlist();

  /* listitem var */ $item = null;

  $item = newitem("Sun");
  // check for reference parameters
  additem( /* & */ $SolarSystem, /* & */ $item);

  $item = newitem("Mercury");
  additem( /* & */ $SolarSystem, /* & */ $item);

  $item = newitem("Venus");
  additem( /* & */ $SolarSystem, /* & */ $item);

  // ...

} // void function example(...)

?>

视觉表示可能是这样的：

.............................................................
....+-------------------+....................................
....|    SolarSystem    |....................................
....+---------+---------+....................................
..............|..............................................
..............v..............................................
....+---------+---------+...........null.....................
....|  Last   |  First  |............^.......................
....+---+-----+----+----+............|.......................
........|..........|.........+-------+-+.....................
........|..........+-------->|  prev   |.....................
........|....................+---------+....+-----------+....
........|....................|  data   +--->|   "Sun"   |....
........|....................+---------+....+-----------+....
........|....................|  next   |.....................
........|....................+-+-------+.....................
........|......................|.....^.......................
........|......................v.....|.......................
........|....................+-------+-+.....................
........|....................|  prev   |.....................
........|....................+---------+....+-----------+....
........|....................|  data   +--->| "Mercury" |....
........|....................+---------+....+-----------+....
........|....................|  next   |.....................
........|....................+-+-------+.....................
........|......................|.....^.......................
........|......................v.....|.......................
........|....................+-------+-+.....................
........|....................|  prev   |.....................
........|....................+---------+....+-----------+....
........+------------------->|  data   |--->|  "Venus"  |....
.............................+---------+....+-----------+....
.............................|  next   |.....................
.............................+-+-------+.....................
...............................|.............................
...............................v.............................
..............................null...........................
.............................................................

干杯。