容器与容器遍历 多态的应用 最终用泛型实现（Object—->泛型E） 泛型使用时指定类型，但不需要强转（Object需要强转） 泛型（可以随便起，但最好见名知义）

  • Element
  • Type
  • Key
  • Value

需求

  • 自己写一容器
    • 数组实现
    • 链表实现
  • 能自由添加元素
  • 大小能动态拓展
    • List.add();
  • 实现对容器的遍历
    • 通用的便利方式——对数组、对链表
    • ❓通过接口强转回去只能打印出来不能使用？

存储结构

  • 数据结构——物理结构（就两种）
    • 连续存储——>数组
    • 非连续存储——>链表
  • 数据结构——逻辑结构
    • 二叉树——>可数组实现、可链表实现
    • 栈
    • 队列
    • ……

迭代器

  • 只能让每个容器实现自己的遍历
  • 不能在外面做，在外面做不光不知道该容器的结构还破坏了容器的封装性
  • 定义一迭代器，通过迭代器遍历
  • 可以不用知道具体的遍历方式而拿到里面的元素
  • 每个容器提供一个Iterator，内部自己实现
  • 迭代器中要有hasNext();和next();方法
  • 不是容器类实现Iterator接口，而是在容器类实现一内部类（嵌套类可以直接使用外部类的属性）
    • 不用内部类也没关系，但是这个类与其他类没有关系，隐藏在内部可以省很多麻烦；用公共类不能阻止别人去用他，在内部类中用private修饰更安全
    • 自己实现Iterator也行但是破坏了单一职责原则，iterator() return this;
    • 只要返回这样一个Iterator对象即可，内部怎么实现和用的人没有关系（模仿jdk的实现）
    • 这样做可以解耦
    • 迭代器迭代到哪和容器类本身没有关系
    • 迭代器只是作为容器类的一个属性但是又不当作成员变量

UML类图

image.png

Collection接口实现了Iteratorable接口

实现

Collection_接口

  1. package com.mashibing.dp.Iterator.v5;
  3. public interface Collection_ {
  4.     void add(Object o);
  5.     int size();
  7.     Iterator_ iterator();
  8. }

Iterator接口

  1. package com.mashibing.dp.Iterator.v5;
  3. public interface Iterator_ {
  4.     boolean hasNext();
  6.     Object next();
  7. }

数组

  1. package com.mashibing.dp.Iterator.v5;
  4. /**
  5.  * 相比数组，这个容器不用考虑边界问题，可以动态扩展
  6.  */
  7. class ArrayList_ implements Collection_ {
  8.     Object[] objects = new Object[10];
  9.     //objects中下一个空的位置在哪儿,或者说，目前容器中有多少个元素
  10.     private int index = 0;
  11.     public void add(Object o) {
  12.         if(index == objects.length) {
  13.             Object[] newObjects = new Object[objects.length*2];
  14.             System.arraycopy(objects, 0, newObjects, 0, objects.length);
  15.             objects = newObjects;
  16.         }
  18.         objects[index] = o;
  19.         index ++;
  20.     }
  22.     public int size() {
  23.         return index;
  24.     }
  26.     @Override
  27.     public Iterator_ iterator() {
  28.         return new ArrayListIterator();
  29.     }
  31.     private class ArrayListIterator implements Iterator_{
  33.         private int currentIndex = 0;
  35.         @Override
  36.         public boolean hasNext() {
  37.             if(currentIndex >= index) return false;
  38.             return true;
  39.         }
  41.         @Override
  42.         public Object next() {
  43.             Object o = objects[currentIndex];
  44.             currentIndex ++;
  45.             return o;
  46.         }
  47.     }
  50. }

链表

  1. package com.mashibing.dp.Iterator.v5;
  3. /**
  4.  * 相比数组，这个容器不用考虑边界问题，可以动态扩展
  5.  */
  6. class LinkedList_ implements Collection_ {
  7.     Node head = null;
  8.     Node tail = null;
  9.     //目前容器中有多少个元素
  10.     private int size = 0;
  12.     public void add(Object o) {
  13.         Node n = new Node(o);
  14.         n.next = null;
  16.         if(head == null) {
  17.             head = n;
  18.             tail = n;
  19.         }
  21.         tail.next = n;
  22.         tail = n;
  23.         size++;
  24.     }
  26.     private class Node {
  27.         private Object o;
  28.         Node next;
  30.         public Node(Object o) {
  31.             this.o = o;
  32.         }
  34.         public Object getObject() {
  35.             return o;
  36.         }
  37.     }
  39.     public int size() {
  40.         return size;
  41.     }
  43.     @Override
  44.     public Iterator_ iterator() {
  45.         return new LinkedListIterator();
  46.     }
  48.     private class LinkedListIterator implements Iterator_{
  50.         private Node currentIndex = head;
  52.         @Override
  53.         public boolean hasNext() {
  54.             if(currentIndex == tail) return false;
  55.             return true;
  56.         }
  58.         @Override
  59.         public Object next() {
  60.             currentIndex = currentIndex.next;
  61.             return currentIndex.getObject();
  62.         }
  63.     }
  64. }

使用

  1. package com.mashibing.dp.Iterator.v5;
  3. import java.util.Iterator;
  5. /**
  6.  * v1:构建一个容器，可以添加对象
  7.  * v2:用链表来实现一个容器
  8.  * v3:添加容器的共同接口，实现容器的替换
  9.  * v4:如何对容器遍历呢？
  10.  * v4:用一种统一的遍历方式，要求每一个容器都要提供Iterator的实现类
  11.  *    作业：实现LinkedList的Iterator
  12.  */
  14. public class Main {
  15.     public static void main(String[] args) {
  16.         Collection_ list = new ArrayList_();
  17.         for(int i=0; i<15; i++) {
  18.             list.add(new String("s" + i));
  19.         }
  20.         System.out.println(list.size());
  22.         //这个接口的调用方式：
  23.         Iterator_ it = list.iterator();
  24.         while(it.hasNext()) {
  25.             Object o = it.next();
  26.             System.out.println(o);
  27.         }
  28.     }
  29. }

jdk中的Iterator(源码见jdk)

  1. package com.mashibing.dp.Iterator.v6;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  5. import java.util.Iterator;
  7. /**
  8.  * v1:构建一个容器，可以添加对象
  9.  * v2:用链表来实现一个容器
  10.  * v3:添加容器的共同接口，实现容器的替换
  11.  * v4:如何对容器遍历呢？
  12.  * v4:用一种统一的遍历方式，要求每一个容器都要提供Iterator的实现类
  13.  *    作业：实现LinkedList的Iterator
  14.  * v6:JDK的容器的Iterator
  15.  */
  17. public class Main {
  18.     public static void main(String[] args) {
  19.         Collection c = new ArrayList();
  20.         for(int i=0; i<15; i++) {
  21.             c.add(new String("s" + i));
  22.         }
  24.         Iterator it = c.iterator();
  25.         while(it.hasNext()) {
  26.             System.out.println(it.next());
  27.         }
  28.     }
  29. }

泛型实现

实现详见gitlab

🤏随想

  1. 用父类引用子类调用子类重写的父类方法时调用的是子类重写的方法（String的toString和Object的toString）
  2. 用父类引用子类调用子类自己的方法时必须要进行强制类型转换