自组织链表是针对搜索问题提出的,它能够在响应未知访问请求序列的过程中不断调整节点位置,使链表结构逐渐进入一个能充分利用访问请求序列特性的状态,从而降低总体访问代价,提高链表性能。随着计算机硬件技术的发展,为了充分利用多处理器的协同计算能力,需要设计一种有效的共享并发自组织链表。　　 非阻塞数据结构使用非互斥方法,可以同时被多个并发线程访问,避免了互斥方法中一个位于临界区中的线程的延迟对其它线程产生的影响。它能够保证在有限步内至少有一个线程能够完成若干操作,具有更强的健壮性和更高的可依赖性。　　 论文提出了两种非阻塞自组织链表:只读型非阻塞自组织链表和读写型非阻塞自组织链表。两种新链表均满足可线性化条件。其中读写型非阻塞自组织链表采用MTF规则,是已知的第一个支持常见字典操作的非阻塞自组织链表。　　 只读型非阻塞自组织链表中引入了“热点”元素的概念。它为每个线程分配一个热点数组,通过热点数组来指导链表的自组织行为。此外,热点数组还可以提高热点元素的查找效率,为充分利用高速缓存带来了契机。　　 读写型非阻塞自组织链表在数据节点之外引入了操作节点。一方面,执行相关操作的线程之间通过操作节点相互通信、获取其它线程的执行结果、以及通知其它线程自身的执行结果,保证了操作的非阻塞性和正确性。另一方面,通过让操作节点起到数据节点的作用,能够及时、准确地对访问元素执行MTF操作,从而实现链表的自组织行为。　　 实验表明,当访问请求序列具有较强局部性时,两种新链表的性能超过了已有的无自组织行为的非阻塞链表和使用粗粒度加锁方式实现的阻塞自组织链表。