< meta http-equiv="description" content="我觉得第4点说的很好,对于一堆数据而言,不同的人(或业务逻辑)使用它的方式也不尽相同,定义一个theIterator继承Iterator,不仅提供next,hasNext 以及remove这个最小的操作集合,同时也可以提供更多的其它方法"/>

用Java实现链表结构

[来源] 达内    [编辑] 达内   [时间]2012-11-09

我觉得第4点说的很好,对于一堆数据而言,不同的人(或业务逻辑)使用它的方式也不尽相同,定义一个theIterator继承Iterator,不仅提供next,hasNext 以及remove这个最小的操作集合,同时也可以提供更多的其它方法

  这里主要记录了一下学习用Java实现链表的方法。假设你有一点Java基础,了解接口、内部类的内容,同时也学过数据结构中链表的内容,对设计模式中的工厂方法和迭代方法知道一些,(因为这里将不介绍这些基础知识,我的水平也讲不清)又想了解在Java中实现链表,那么接着看吧。(最近读严老师<应该没记错名字吧,如果错了抱歉>的帖子说应该在博文中说明帖子的读者范围,不要浪费大家的时间,这里响应一下)。

  首先声明一下,本人菜鸟一只,近日闲来无事做做coding打发光阴,限于我对技术的认知水平,文中说的不对的地方一定不少,如果有热心人能帮忙指出,不胜感激!!批评者,请口下留情,不要打击了俺幼小地心灵。。。。。

  正文:

  最近写程序的过程中想用链表的方法把一些数据组织起来,C/C++的链表倒是比较熟,但是Java里还没写过。在网上搜了搜,Java中的链表应该是有以下几种方法:

  按链表的组织形式分有ArrayList和LinkList两种。ArrayList内部其实是用数组的形式实现链表,比较适合链表大小确定或较少对链表进行增删操作的情况,同时对每个链表节点的访问时间都是constant;而LinkList内部以一个List实现链表,比较适合需要频繁对链表进行操作的情况,对链表节点的访问时间与链表长度有关O(N)。

  另外,根据实现形式可以分为直接式(想不出什么合适的名字,姑且这样吧)和使用Iterator(迭代模式)两种方法。直接式的实现方法和C/C++中的写法差不多;而使用Iterator时,需要实现java.lan中的Iterable接口(或者也可以自己在链表内部定义自己的Iterator method)

  关于直接实现链表好,还是使用迭代模式好这个问题,有两个帖子可以看看:

  1. http://topic.csdn.net/t/20050722/17/4162226.html这篇帖子,虽然短小,但也说出了一些使用迭代模式设计链表的好处;

  2.后来又看到了http://www.java63.com/design_pattern/iterator_pattern.html这篇帖子,觉得说的比较清楚了。

  我这里再捡主要的说一下:

  使用迭代模式的优点:

  1,实现功能分离,简化容器接口。让容器只实现本身的基本功能,把迭代功能委让给外部类实现,符合类的设计原则。

  2,隐藏容器的实现细节。

  3,为容器或其子容器提供了一个统一接口,一方面方便调用;另一方面使得调用者不必关注迭代器的实现细节。

  4,可以为容器或其子容器实现不同的迭代方法或多个迭代方法。

  我觉得第4点说的很好,对于一堆数据而言,不同的人(或业务逻辑)使用它的方式也不尽相同,定义一个theIterator继承Iterator,不仅提供next,hasNext 以及remove这个最小的操作集合,同时也可以提供更多的其它方法。在theIterator的实现类中,具体实现不同的迭代方法,比如顺序、逆序或根据其它语义进行遍历等,再通过类厂的方式将一个theIterator实现的对象交给用户使用。

资源下载