自组织链表是一种实用的数据结构,可以根据访问序列动态调整列表结构,适应访问模式,目的是减少平均访问时间并提高链表的性能。如果被访问的数据局部性较强,自组织链表能够比非自组织链表显示出更强的性能优势。将自组织链表应用于并发环境下,可以充分发挥多核处理器的优势,获取更高的性能。非阻塞的并发自组织链表的实现比基于锁的实现具有更好的可靠性和健壮性。因此,论文对非阻塞自组织链表进行了研究,首先提出了一种无锁的自组织链表,在此基础上进行扩展,实现了具有无等待特性的自组织链表。实验表明,新的无等待自组织链表具有良好的实用价值。论文在已有的并发自组织链表的研究基础上,完成了以下工作:(1)总结了已有的并发自组织链表算法,包括基于MTF(Move-To-Front)规则和换位规则的非阻塞自组织链表;(2)提出并实现了一个基于MTF规则的无锁自组织链表算法,在此基础上提出无等待自组织链表算法,保证每个进程在有限步骤内演进;(3)从可线性化性、无锁、无等待和自组织四个方面对新算法进行了正确性证明;(4)对已有的无等待链表进行性能分析,实验以吞吐率作为性能评价指标,实验结果表明,在局部性数据上,本文提出的无等待自组织链表优于已有的无等待链表。