更好的链接列表处理 [英] Better Linked List Handling

问题描述

刚刚完成关于链接列表的新IBM DeveloperWorks文章，并且

认为您可能都感兴趣。它不是一个介绍 - 它

而是涵盖链表的一些更有趣的方面。

http://www.ibm.com/developerworks/li...ry/l-listproc/


Jon

----

学习使用Linux汇编语言编程
http://www.cafeshops.com/bartlettpublish.8640017

解决方案

2005年1月6日星期四11:42:16 -0500，Jonathan Bartlett

< jo ***** @ eskimo.com>写道：

刚刚完成关于链接列表的新的IBM DeveloperWorks文章，并且
认为你们可能都感兴趣。这不是一个介绍 - 它取而代之的是链接列表中一些更有趣的方面。

http://www.ibm.com/developerworks/li...ry/l-listproc/

也许你想通过一个好的lint处理器运行它来消除

未定义的行为。当你在这里时，你可能也会摆脱无用的演员表
，这只是一个不好的例子。

<<删除电子邮件的del>> ;

Jonathan Bartlett写道：

刚刚完成关于链表的新的IBM DeveloperWorks文章，并且认为你们都可能会感兴趣。这不是一个介绍 - 它取而代之的是链接列表中一些更有趣的方面。

http://www.ibm.com/developerworks/li...ry/l-listproc/

我喜欢强调Scheme和尾部共享的解释。

将NULL定义为0可能会让一些人感到困惑，尽管它是'相当

正确（参见comp.lang.c FAQ 5.5及相关问题）;

假设他们知道NULL是安全的。


还有一种更好的方法来做通用链表数据结构，

假设每个节点中的值是固定的（只读）：首先将下一个指针放在

，然后为特定的
$ b分配足够的值$ b数据对象，可以节省空间（分配

offsetof（数据）+ sizeof（无论如何））。由于你可以删除一个旧节点并换上一个新节点，因此只读限制并不是很重要。


标签也非常浪费空间，因为大多数列表都是单一类型的数据b $ b;对于这些列表，最好将标记放在

列表的数据结构中。如果你真的对异类

列表感兴趣，一种有效的方法是从池中分配节点，

其中每个池只包含一种类型的数据。您可以通过指针比较确定对象所在的
池。然后你有一个小表

映射池号到标签。随着游泳池的填满，你会赚更多的东西（随着你赚得更多而获得更多的b $ b）并展开桌子。


最后，我认为cdr编码和展开的链表绝对值得提供 - 这是两个常见的解决方案，可以解决令人讨厌的空间开销问题，以及与简单链接列表相关的缓存问题，尽管它们很难实现
复杂化一些操作。

-

Derrick Coetzee

我将此新闻组发布到公共领域。我不承担所有

明示或暗示保证并承担所有责任。我不是专业人士。

Barry Schwarz写道：

< jo ***** @ eskimo.com>写道：

刚刚完成关于链接列表的新的IBM DeveloperWorks文章，并且
认为你们可能都感兴趣。这不是一个介绍 - 它取而代之的是链接列表中一些更有趣的方面。

http://www.ibm.com/developerworks/li...ry/l-listproc/

也许你想通过一个好的lint处理器运行它来消除未定义的行为。当你在这里的时候，你也可能会摆脱无用的演员阵容，这只是一个不好的例子。

看起来好像他有很大程度上改名为lisp作为计划，并且

避免给予信用。


-

查克F（cb ***** ***@yahoo.com）（cb********@worldnet.att.net）

可用于咨询/临时嵌入式和系统。

< HTTP：//cbfalconer.home.att.net>使用worldnet地址！

Just finished a new IBM DeveloperWorks article on linked lists, and
thought you all might be interested. It''s not an introduction -- it
instead covers some of the more interesting aspects of linked lists.

http://www.ibm.com/developerworks/li...ry/l-listproc/

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

解决方案

On Thu, 06 Jan 2005 11:42:16 -0500, Jonathan Bartlett
<jo*****@eskimo.com> wrote:

Just finished a new IBM DeveloperWorks article on linked lists, and
thought you all might be interested. It''s not an introduction -- it
instead covers some of the more interesting aspects of linked lists.

http://www.ibm.com/developerworks/li...ry/l-listproc/

Maybe you want to run it through a good lint processor to eliminate
the undefined behavior. While you are at it, you might also get rid
of the useless cast which serves only as a bad example.
<<Remove the del for email>>

Jonathan Bartlett wrote:

Just finished a new IBM DeveloperWorks article on linked lists, and
thought you all might be interested. It''s not an introduction -- it
instead covers some of the more interesting aspects of linked lists.

http://www.ibm.com/developerworks/li...ry/l-listproc/

I like the emphasis on Scheme, and the explanation of tail-sharing.
Defining NULL as 0 might confuse some people, although it''s quite
correct (see the comp.lang.c FAQ question 5.5 and related); it''s safe to
assume they know about NULL.

There''s also a better way to do the generic linked list data structure,
assuming that the value in each node is fixed (read-only): by placing
the next pointer first, then allocating just enough for the specific
data object, you can save space (allocate
offsetof(data)+sizeof(whatever)). The read-only restriction isn''t too
big of a deal, since you can cut out an old node and put in a new one.

The tags are also quite wasteful of space, since most lists are of data
of a single type; for these list it''s better to put the tag in the
list''s data structure. If you are really interested in heterogenous
lists, one effective approach is to allocate the nodes out of pools,
where each pool only contains data of one type. You can determine which
pool an object is in by pointer comparison. Then you have a small table
mapping pool number to tag. As pools fill up you make more (getting
larger as you make more) and expand the table.

Finally, I think cdr coding and unrolled linked lists definitely deserve
a mention - these are two common solutions to the nasty space overhead
and cache problems associated with simple linked lists, although they
complicate some operations.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.

Barry Schwarz wrote:

<jo*****@eskimo.com> wrote:

Just finished a new IBM DeveloperWorks article on linked lists, and
thought you all might be interested. It''s not an introduction -- it
instead covers some of the more interesting aspects of linked lists.

http://www.ibm.com/developerworks/li...ry/l-listproc/

Maybe you want to run it through a good lint processor to eliminate
the undefined behavior. While you are at it, you might also get rid
of the useless cast which serves only as a bad example.

Looks to me as if he has largely renamed lisp as scheme, and
avoided giving credit.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

这篇关于更好的链接列表处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！