杭州建站,合肥建设工程交易网站,汝州市文明建设门户网站,内蒙建设厅投诉网站Java实现链表结构按链表的组织形式分有ArrayList和LinkList两种。ArrayList内部其实是用数组的形式实现链表#xff0c;比较适合链表大小确定或较少对链表进行增删操作的情况#xff0c;同时对每个链表节点的访问时间都是constant#xff1b;而LinkList内部以一个List实现链…Java实现链表结构按链表的组织形式分有ArrayList和LinkList两种。ArrayList内部其实是用数组的形式实现链表比较适合链表大小确定或较少对链表进行增删操作的情况同时对每个链表节点的访问时间都是constant而LinkList内部以一个List实现链表比较适合需要频繁对链表进行操作的情况对链表节点的访问时间与链表长度有关O(N)。另外根据实现形式可以分为直接式和使用Iterator迭代模式两种方法。使用Iterator时需要实现
java.lang中的Iterable接口或者也可以自己在链表内部定义自己的Iterator method使用迭代模式的优点 1实现功能分离简化容器接口。让容器只实现本身的基本功能把迭代功能委托给外部类实现符合类的设计原则。 2隐藏容器的实现细节。 3为容器或其子容器提供了一个统一接口一方面方便调用另一方面使得调用者不必关注迭代器的实现细节。4可以为容器或其子容器实现不同的迭代方法或多个迭代方法。5. 迭代效率高Iterator 集合框架中的接口主要用于迭代集合中的元素而对于像LinkedList如果你用For循环则LinkedList的get方法效率是非常低的因为它每次访问一个元素都要从头开始。而对于Iterator来说它就像你用吸管从饮料瓶吸饮料一样每吸一口就消耗掉一点它的迭代效率很高。我觉得第4点说的很好对于一堆数据而言不同的人或业务逻辑使用它的方式也不尽相同定义一个theIterator继承Iterator不仅提供nexthasNext 以及remove这个最小的操作集合同时也可以提供更多的其它方法。在theIterator的实现类中具体实现不同的迭代方法比如顺序、逆序或根据其它语义进行遍历等再通过类厂的方式将一个theIterator实现的对象交给用户使用。首先是直接式实现链表的例子这个例子只提供了几种链表操作的基本方法仅用于示意public class MyListAnyType { private class NodeAnyType{ public NodeAnyType pre; public NodeAnyType next; public AnyType data; public Node(AnyType d, NodeAnyTypep, NodeAnyType n){} public Node(){} } private int theSize; private NodeAnyType Header; private NodeAnyType Tail; public MyList(){} public void add(AnyType item){} public boolean isEmpty(){} public int size(){} public AnyType get( int idx){} public void print(){} } NodeAnyType类定义了双向链表中节点的结构它是一个私有类而其属性和构造函数都是公有的这样其父类可以直接访问其属性而外部类根本不知道Node类的存在。Data是节点中的数据pre指向前一个Node节点next指向后一个Node节点。其构造函数的实现如下不解释[java] view plain copypublic Node(AnyType d, NodeAnyTypep, NodeAnyType n){ this.data d; this.pre p; this.next n; } public Node(){ this.data null; this.pre null; this.next null; } 下面我们看一下链表的构造函数实现[java] view plain copypublic MyList(){ theSize 0; Header new NodeAnyType(null,null,null); Tail new NodeAnyType(null,Header,null); Header.next Tail; } 我们构造了一个带有头、尾节点的双向链表头节点的Next指向尾节点为节点的pre指向头节点。链表长度起始为0。
继续贴上链表类其它方法的实现不解释了应该比较清楚[java] view plain copypublic void add(AnyType item){ NodeAnyType aNode new NodeAnyType(item,null,null); Tail.pre.next aNode; aNode.pre Tail.pre; aNode.next Tail; Tail.pre aNode; theSize; } public boolean isEmpty(){ return ( theSize 0); } public int size(){ return theSize; } public AnyType get( int idx){ if(idx theSize-1 || idx 0) throw new IndexOutOfBoundsException(); NodeAnyType current new NodeAnyType(null,Header,null); for(int i 0; iidx; i) current current.next; return current.data; } public void print(){ NodeAnyType current Header.next; while(current.next ! null){ //如果AnyType是你自己定义 //的数据类型那么请务必提供 //一个toString方法要么就不 //要在链表里实现print方法。 System.out.println(current.data.toString()); current current.next; } } 第二个例子是用迭代方法实现链表的例子下面是类定义[java] view plain copypublic class MyListItrType implements IterableType { private class NodeType{ public Type data; public NodeType pre; public NodeType next; public Node(){} public Node(Type d, NodeType p, NodeType n){} } private NodeType Header; private NodeType Tail; private int theSize; public MyListItr(){} public void add(Type item){} public void print(){} public int size(){} Override public IteratorType iterator() {} private class MyListIterator implements IteratorType{ Override public boolean hasNext() {} Override public Type next() {} Override public void remove() {} } } 这里主要说一下与前面例子不同的地方MyListItr类实现了java.lan.Itrable接口因此我们必须实现其public IteratorType iterator() {}方法它的返回值是一个迭代器对象那么我就定义一个内部私有类——MyListIterator这个类实现了iterator接口。在public IteratorType iterator() 方法中我就构造这么一个MyListIterator的对象并返回。Iterator接口有三个方法是我们必须实现的hasNextnext和remove这是迭代操作的最小集合了。对于不同的迭代器执行方式我们可以定义多个类似MyListIterator这样的实现类只要在链表类中的iterator() 方法中把具体实现类的对象返回给用户就OK了。罗嗦两句我感觉如果我们定义链表类时如果不继承Iterable接口而是直接在类内部提供 public theIterator Iterator() 方法theIterator是一个自定义接口继承自Iterator接口这样我们可以提供遵循theIterator接口的各种迭代方式的不同实现类并通过一个类厂方法在链表的public theIterator Iterator() 方法中把具体迭代实现类的对象交给用户以此就可以根据不同的需求提供链表的多种迭代方式。我觉得这种方法是可行的但并没有具体实验。下面只贴出链表iterator()方法和迭代实现类的MyListIterator代码其它方法就不重复贴了[java] view plain copyOverride public IteratorType iterator() { return new MyListIterator(); } private class MyListIterator implements IteratorType{ NodeType current Header.next; Override public boolean hasNext() { return (current ! Tail); } Override public Type next() { if(!hasNext()) throw new IndexOutOfBoundsException(); Type item current.data; current current.next; return item; } Override public void remove() { if( !hasNext()) throw new NoSuchElementException(); current.pre.next current.next; current.next.pre current.pre; current current.next; theSize--; } }
参考博文https://blog.csdn.net/wangkr111/article/details/7884322
