用Java实现链表结构

　　这里主要记录了一下学习用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.后来又看到了。

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

　　使用迭代模式的优点：

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

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

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

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

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