MyList接口

  1. package collection;
  3. /**
  4.  * 自定义接口Mylist，模仿List
  5.  * @param <E>
  6.  */
  8. public interface MyList<E> {
  9.     int size();
  10.     boolean isEmpty();
  11.     void add(E obj);
  13.     void add(int index, E obj);
  14.     void set(int index, E obj);
  16.     boolean contains(E obj);
  17.     Object[] toArray();
  18.     boolean remove(E obj);
  19.     void clear();
  20. }

MyArrayList类

  1. package collection;
  3. import java.util.Arrays;
  5. public class MyArrayList<E> implements MyList<E>{
  7.     private static final int DEFAULT_CAPACITY = 10;
  8.     // size是列表元素个数
  9.     private int size;
  11.     private Object[] elementData;
  13.     public MyArrayList() {
  14.         this(DEFAULT_CAPACITY);
  15.     }
  17.     public MyArrayList(int initialCapacity) {
  18.         if (initialCapacity < 0) {
  19.             try {
  20.                 throw new Exception("大于零");
  21.             } catch (Exception e) {
  22.                 e.printStackTrace();
  23.             }
  24.         }else{
  25.             this.elementData = new Object[initialCapacity];
  26.         }
  27.     }
  29.     public static void main(String[] args) {
  30.         MyArrayList<String> myList1 = new MyArrayList<>();
  31.         System.out.println(myList1);
  32.         myList1.add("aa");
  33.         myList1.add("bb");
  34.         myList1.add("cc");
  35.         myList1.add("dd");
  36.         myList1.add("ee");
  37.         myList1.add("ff");
  38.         myList1.add(2,"fuck");
  39.         System.out.println(myList1.set(0,"start"));
  40.         System.out.println(myList1.get(4));
  41.         System.out.println(myList1.contains("ee"));
  42.         myList1.remove(2);
  43.         myList1.remove("start");
  44.         System.out.println(myList1);
  45. //        myList1.clear();
  46.     }
  48.     @Override
  49.     public int size() {
  50.         return size;
  51.     }
  53.     @Override
  54.     public boolean isEmpty() {
  55.         return size == 0;
  56.     }
  58.     @Override
  59.     public void add(E obj) {
  60.         ensureCapacity();
  61.         elementData[size] = obj;
  62.         size++;
  63.     }
  65.     @Override
  66.     public void add(int index, E obj) {
  67.         rangeCheck(index);
  68.         ensureCapacity();
  70.         System.arraycopy(elementData,index,elementData,index+1,size-index);
  71.         elementData[index] = obj;
  72.         size++;
  74.     }
  76.     private void rangeCheck(int index){
  77.         if (index<0 || index>=size) {
  78.             try {
  79.                 throw new Exception("index参数不合法");
  80.             } catch (Exception e) {
  81.                 e.printStackTrace();
  82.             }
  83.         }
  84.     }
  86.     private void ensureCapacity(){
  87.         if(size == elementData.length){
  88.             Object[] newElementsData = new Object[2*size+1];
  89.             System.arraycopy(elementData,0,newElementsData,0,size);
  90.             elementData = newElementsData;
  91.         }
  93.     }
  95.     public void remove(int index){
  96.         rangeCheck(index);
  97.         int numMoved = size - (index + 1);
  98.         if (numMoved > 0){
  99.             System.arraycopy(elementData,index+1,elementData,index,numMoved);
  100.         }
  101.         size--;
  102.         elementData[size] = null;
  103.     }
  105.     @Override
  106.     public E set(int index, E obj) {
  107.         rangeCheck(index);
  108.         Object oldValue =  elementData[index];
  109.         elementData[index] = obj;
  110.         return (E) oldValue;
  111.     }
  113.     public E get(int index){
  114.         rangeCheck(index);
  115.         return  (E) elementData[index];
  116.     }
  118.     @Override
  119.     public boolean contains(E obj) {
  120.         for (Object el : elementData) {
  121.             if (el.equals(obj)) {
  122.                return true;
  123.             }
  124.         }
  125.         return false;
  126.     }
  128.     @Override
  129.     public Object[] toArray() {
  130.         return elementData;
  131.     }
  133.     @Override
  134.     public boolean remove(E obj) {
  135.         for (int i = 0; i < size; i++) {
  136.             if (elementData[i].equals(obj)) {
  137.                 remove(i);
  138.                 return true;
  139.             }
  140.         }
  141.         return false;
  142.     }
  144.     @Override
  145.     public void clear() {
  146.         for (int i = 0; i < size; i++) {
  147.             elementData[i] = null;
  148.         }
  149.         size = 0;
  150.     }
  152.     @Override
  153.     public String toString() {
  154.         StringBuilder sb = new StringBuilder();
  155.         sb.append("[");
  156.         for (int i = 0; i < size; i++) {
  157.             sb.append(elementData[i]);
  158.             if (i !=size-1) {
  159.                 sb.append(",");
  160.             }
  161.         }
  162.         sb.append("]");
  163.         return sb.toString();
  164.     }
  165. }

MyLinkedList类

  • 结构分析 每个节点存储了数据内容、前一个和后一个节点的内容
  • 与arraylist相比，不便于查找，但是便于插入与删除
    1. class Node {
    2.   Node prevoius;   // 前一个节点
    3.   Object element;   // 本节点保存的数据
    4.   Node next;   // 后一个节点
    5. }
    ```java package collection;

public class MyLinkedList implements MyList{ private Node first; private Node last; private int size;

  1. public static void main(String[] args) {
  2.     MyLinkedList<String> mll = new MyLinkedList<>();
  3.     mll.add("aa");
  4.     mll.add("bb");
  5.     mll.add("cc");
  6.     mll.add("dd");
  7.     mll.add("ee");
  8.     mll.add("ff");
  9.     Node nn = mll.getNode(5);
  10.     mll.add(5,"fuck");
  11.     System.out.println(mll);
  12. }
  14. private void rangeCheck(int index){
  15.     if (index<0 || index>=size) {
  16.         try {
  17.             throw new Exception("index参数不合法");
  18.         } catch (Exception e) {
  19.             e.printStackTrace();
  20.         }
  21.     }
  22. }
  24. private Node getNode(int index){
  25.     rangeCheck(index);
  26.     Node n = null;
  27.     if (first != null) {
  28.         if ((size >> 1) > index) {
  29.             // 从前向后
  30.             n = first;
  31.             for (int i = 0; i < index; i++) {
  32.                 n = n.getNext();
  33.             }
  34.         } else {
  35.             // 从后向前
  36.             n = last;
  37.             for (int i = size-1; i > index; i--) {
  38.                 n = n.getPrevious();
  39.             }
  40.         }
  41.     }
  42.     return n;
  43. }
  45. @Override
  46. public int size() {
  47.     return size;
  48. }
  50. @Override
  51. public boolean isEmpty() {
  52.     return size == 0;
  53. }
  55. @Override
  56. public void add(E obj) {
  57.     Node<E> n = new Node<>();
  58.     if (size == 0) {
  59.         n.setPrevious(null);
  60.         n.setNext(null);
  61.         n.setElement(obj);
  63.         first = n;
  64.         last = n;
  65.     }else{
  66.         n.setPrevious(last);
  67.         n.setNext(null);
  68.         n.setElement(obj);
  70.         last.setNext(n);
  71.         last = n;
  72.     }
  73.     size++;
  74. }
  76. @Override
  77. public void add(int index, E obj) {
  78.     Node target = this.getNode(index);
  79.     Node previous = target.getPrevious();
  80.     Node<E> n = new Node<>();
  81.     n.setElement(obj);
  82.     n.setPrevious(previous);
  83.     n.setNext(target);
  84.     if (previous != null){
  85.         previous.setNext(n);
  86.     }
  87.     target.setPrevious(n);
  88.     // 处理一下链表
  89.     if (index == 0){
  90.         first = n;
  91.     }
  92.     if (index == size() -1){
  93.         last = n.getNext();
  94.     }
  95.     size++;
  96. }
  98. @Override
  99. public Object set(int index, Object obj) {
  100.     return null;
  101. }
  103. @Override
  104. public E get(int index) {
  105.     return (E) getNode(index).getElement();
  106. }
  108. @Override
  109. public boolean contains(Object obj) {
  110.     return false;
  111. }
  113. @Override
  114. public Object[] toArray() {
  115.     return new Object[0];
  116. }
  118. @Override
  119. public boolean remove(Object obj) {
  120.     return false;
  121. }
  123. @Override
  124. public void remove(int index) {
  126. }
  128. @Override
  129. public void clear() {
  131. }

}

class Node { Node previous; E element; Node next;

  1. public Node() {}
  3. public Node getPrevious() {
  4.     return previous;
  5. }
  7. public void setPrevious(Node previous) {
  8.     this.previous = previous;
  9. }
  11. public Object getElement() {
  12.     return element;
  13. }
  15. public void setElement(E element) {
  16.     this.element = element;
  17. }
  19. public Node getNext() {
  20.     return next;
  21. }
  23. public void setNext(Node next) {
  24.     this.next = next;
  25. }

}

```