Java集合自定义模拟实现

自定义实现ArrayList和LinkedList,绝不是为了自造轮子，只是为了加深自己对JDK集合类设计相关设计思想的理解。当然不可能对其所有接口和类进行全部实现，只是大致模拟下。

     查看JDK API文档，我们知道，JDK自带的ArrayList继承了同包下的AbstractList抽象类，而AbstractList又继承自AbstractCollection抽象类，最后AbstractCollection抽象类实现了Collection接口，查看ArrayList的源码，我们知道，其实它底层是基于Object数组实现的，ArrayList之所以可以实现集合长度可变，其实是调用System类的arraycopy()方法进行数组copy的，所以我们常说ArrayList不适用于添加和删除元素，就是这个道理。而LinkedList是基于链表实现的，何为链表？就是由一个节点一个节点连接起来的，好比生活中的链条，前一个连接着下一个，如果链条哪一个节点坏了，我们只需把坏掉的哪一节换掉或去掉，效率都非常高，而如果要找到第几节，那就必须顺藤摸瓜一个一个的找，所以我们常说链表适用于增删元素，不适用于检索某个元素。正由于两个list的实现完全风格迥异，所以两者的遍历方式不统一，而sun为了统一list的遍历方式，就定义了一个Iterator接口，它的出现就是为了解决list遍历方式不统一的问题。这种设计方式的巧妙之处在于，它把list的遍历实现交给各自子接口的实现类去实现，父接口只定义了实现统一list遍历方式必须实现的方法，各自的list只要返回Iterator对象，有了iterator对象，就相当于拿到了统一遍历list的接口，而实际返回的是子类内部自己实现的Iterator对象，实际调用的iterator遍历方法也是子类实现的遍历方式，设计之精巧，很是耐人寻味！下面是我自定义实现ArrayList和LinkedList的代码，虽然没有完全按照JDK里Collection的体系结构来实现，但大致结构和内部实现都是类似的，可能算法上有点差别，毕竟这里我只关心它的实现原理，至于性能方面暂不考虑，比如ArrayList的容量扩充规则JDK内部是怎么实现的，我不是很清楚，但是这个跟它的设计思想没关系，可以忽略不予考虑。
        package com.list;

/**
 * 集合接口
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:46:20
 */
public interface Collection {
 /**
  * 往集合中添加元素
  */
 public void add(Object object);
 
 /**
  * 返回集合元素总个数
  */
 public int size();
 /**
  * 返回集合迭代器
  */
 public Iterator iterator();
 //其他方法尚未实现
}

package com.list;

/**
 * 集合迭代器
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:50:26
 */
public interface Iterator {
 /**
  * 返回下一个元素
  */
 Object next();
 /**
  * 是否有下一个元素
  */
 boolean hasNext();
}

package com.list;

/**
 * ArrayList自定义实现
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:14:25
 */
public class ArrayList implements Collection{
 private static final int DEFAULT_SIZE = 10; //默认容量大小
 private int index = 0;
 private Object[] objects = new Object[DEFAULT_SIZE];
 
 /**
  * 添加元素
  * @param 待添加元素
  */
 public void add(Object object){
  //超过默认容量，则扩充容量
  if(index == objects.length){
   Object[] newObjects = new Object[DEFAULT_SIZE*3/2 + 1];
   System.arraycopy(objects, 0, newObjects, 0, objects.length);
   objects = newObjects;
  }
  objects[index] = object;
  index++;
 }
 
 /**
  * 返回集合中元素总个数
  */
 public int size(){
  return index;
 }
 
 public Iterator iterator(){
  return new ArrayListIterator();
 }
 
 private class ArrayListIterator implements Iterator{
  //当前索引值
  private int currentIndex = 0;
  public boolean hasNext() {
   return currentIndex < index;
  }
  public Object next() {
   Object o = objects[currentIndex];
   currentIndex++;
   return o;
  }
 }
}

package com.list;

/**
 * 链表节点类
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:32:31
 */
public class Node {
 /**
  * 当前节点存储的Object
  */
 private Object data;
 /**
  * 指向的下一个节点
  */
 private Node next;
 public Object getData() {
  return data;
 }
 public void setData(Object data) {
  this.data = data;
 }
 public Node getNext() {
  return next;
 }
 public void setNext(Node next) {
  this.next = next;
 }
 
 public Node(Object data,Node next){
  this.data = data;
  this.next = next;
 }
}

package com.list;

/**
 * LinkedList自定义实现
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:31:39
 */
public class LinkedList implements Collection{
 /**
  * 第一个节点
  */
 private Node head;
 /**
  * 最后一个节点
  */
 private Node tail;
 /**
  * 累计链表元素总个数
  */
 private int size = 0;
 /**
  * 往链表中添加元素
  */
 public void add(Object object){
  Node node = new Node(object,null);
  //若第一个节点为空,把当前添加的节点作为第一个节点
  if(null == head){
   head = node;
   tail = node;
  }
  tail.setNext(node);
  tail = node;
  size++;
 }
 /**
  * 返回当前集合内元素总个数
  */
 public int size(){
  return size;
 }
 
 /**
  * 返回自身的集合迭代器
  */
 public Iterator iterator() {
  return new LinkedListIterator();
 }
 
 private class LinkedListIterator implements Iterator{
  //从第一个节点开始遍历
  Node currentNode = head;
  public boolean hasNext() {
   return null != currentNode.getNext();
  }
  public Object next() {
   //若已经没有下一个节点，则返回null
   if(!hasNext()){
    return null;
   }
   currentNode = currentNode.getNext();
   return currentNode.getData();
  }
 }
}

package com.list;

/**
 * 这个类只是用于辅助测试
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:25:00
 */
public class Student {
 private Long id;

 public Long getId() {
  return id;
 }

 public void setId(Long id) {
  this.id = id;
 }
 
 public Student(){}
 
 public Student(Long id){
  this.id = id;
 }
 @Override
 public String toString() {
  return "student" + id.toString();
 }
}

package com.list;

/**
 * 测试自定义的ArrayList
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:24:41
 */
public class TestArrayList {

 public static void main(String[] args) {
  //ArrayList al = new ArrayList();
  Collection c  = new ArrayList();
  for (int i = 0; i < 15; i++) {
   Student student = new Student(new Long(i));
   c.add(student);
  }
  System.out.println(c.size());
 }
}

package com.list;

/**
 * 测试自定义的LinkedList类
 * @author       Lanxiaowei
 * @createTime   2011-10-17 下午08:44:11
 */
public class TestLinkedList {
 public static void main(String[] args) {
  //LinkedList lk = new LinkedList();
   Collection c = new LinkedList();
  for (int i = 0; i < 15; i++) {
   Student student = new Student(new Long(i));
   c.add(student);
  }
  System.out.println(c.size());
  //注意这里使用的是自定义的Iterator迭代器，而不是JDK自带的迭代器
  for (Iterator iterator = c.iterator(); iterator.hasNext();) {
   Student student = (Student)iterator.next();
   System.out.println(student);
  }
 }
}

若有哪里写的不妥的，还望多多指教！(*^__^*) 嘻嘻。好，就写到这里吧！

本文来源 我爱IT技术网 http://www.52ij.com/jishu/103.html 转载请保留链接。