总结

数据结构

数据结构：保存数据的一种方式

常见的数据结构

通过数组来保存，基于数组的数据结构（动态数组，长度可变的数组）
基于数组的结构的优缺点

		1.通过下标查询元素，效率高

		2.通过下标修改元素，效率高
		**查改快**

		在需要扩容的时候：添加慢，删除慢，插入元素慢
		**增删插慢**

```java
/**
 * 模拟一个动态数组
 */
public class MyArrayList {

    private Object[] values; // 保存任意类型的数据
    private int size; // 数组有效元素的个数

    public MyArrayList(){
        this(10);
    }
    public MyArrayList(int initSize) {
        values = new Object[initSize];
    }

    private void grow() {
        // 计算扩容的长度：1.5
        int len = values.length + (values.length >> 1);
        values = Arrays.copyOf(values,len);
    }

    public  void add(Object element) {
        // 多参数进行判断
        if(element == null)
            throw new IllegalArgumentException("非法参数，参数不能为null");
        if(size == values.length)
            grow();
        values[size++] = element;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(values[i]).append("\t");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add(true);
        list.add(1);
        list.add("sdafdsf");
        list.add(3.14);
        list.add(true);
        System.out.println(list);
    }
}
```

通过一个对象变量来保存数据，基于变量保存数据的结构称为链表结构
增删插快
查改慢

/**
 * 模拟一个基于链表的结构
 */
public class MyLinkedList {
    private Node head; // 链表头部
    private Node footer; // 尾部
    public void add(Object o) {
        if(head == null) {
            head.val = o;
            footer = new Node(o);
        }else {
            footer = new Node(o);
        }
    }


    static class Node { // 声明的一个内部类
        private Object val;
        private Node next; // 装下一个对象，形成链条


    }
}

队列
单向队列：一个是进口，一个是出口，先进先出（FIFO）
双向队列：两端既是进口又是出口
栈结构：只有一个口，既是进口也是出口
先进后出：FILO（后进先出:LIFO）
树形结构：是链表的一种变形结构

集合

集合：基于某种数据结构的容器

了解集合的体系结构：

Collection:集合的根接口（父接口）：定义方法的标准

第一个子接口：list:可以存放重复元素，而且有序（有序：存入的顺序和取出来的顺序一致（存取一致）），有序可重复

/**
* 使用接口的实现类
*/
class ArrayList implements List {

}
abstract class AbstractList implements List {
    将list里面所有的抽象方法实现了
}
class ArrayList extends AbstractList implements List {
       // 想重写那个就从哪个
}

List接口的实现子类：

ArrayList:基于数组的集合（线程不安全）
LinkedList：基于链表的集合
Vector：基于数组的集合（线程安全）

第二子接口：set:不能存放相同的元素（去重），无序（存取不一致），无序不可重复

List接口的实现类

ArrayList:基于数组的集合

/**
 * 讲解实现List接口的实现类
 *  ArrayList:基于数组的集合
 */
public class ListDemo2 {
    public static void main(String[] args) {
        // 创建ArrayList的对象
        ArrayList list = new ArrayList(); // 基于数组的集合
        // 常用方法
        // add(Object e) add(index,e)
        list.add(true); // 第一次添加的时候
        list.add(3.14);
        list.add("磊哥不行了");
        list.add(true);
        list.add('a');
        list.add(0,'a');
        System.out.println(list);
        System.out.println(list.size());

        ArrayList list2 = new ArrayList(20);
        list2.add(list); // 将集合作为一个值添加到集合
        list2.add("蘋蘋");
        list2.addAll(0,list); // 将list集合里面元素一个一个添加list2里面
        System.out.println(list2);
        System.out.println(list2.size());

        // contains(Object o): 判断集合中是否存在该对象
        System.out.println(list.contains(false));

        // get(int index):通过指定下标获取对象
        System.out.println(list.get(0));

        // indexOf(Object o) :查询对象在集合中第一次出现位置
        System.out.println(list.indexOf('a'));

        // lastIndexOf(Object o)
        System.out.println(list.lastIndexOf('a'));

        // remove(int index) :通过下标删除指定对象
        list.remove(0);
        list.add(1);
        System.out.println(list);
        //  remove(Object o) :删除指定对象
        Integer i = 1;
        list.remove(i);

        ArrayList list3 = new ArrayList();
        list3.add(true);
        list3.add(3.14);

        list.removeAll(list3);
        System.out.println(list);

        // set(int index, E element)
        list.set(0,"3254354");
        System.out.println(list);
    }
}

ArrayList集合的遍历

public class ListDemo3 {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("abc");
        list.add("bbc");
        list.add("cbc");
        list.add("dbc");
        list.add("ebc");
        // 遍历第一种方式：循环（for）
//        for (int i = 0; i < list.size(); i++) {
//            System.out.println(list.get(i));
//        }
//        System.out.println("============================");
//        for (int i = list.size() - 1; i >= 0; i--) {
//            System.out.println(list.get(i));
//        }
        // 遍历第二种方式：foreach
//        for (Object o : list) {
//            System.out.println(o);
//        }

        // 遍历集合的第三种方式：迭代器
        // 单向迭代器：只能从第一个元素到最后一个元素：iterator() 
//        Iterator it = list.iterator();// 获取遍历list集合的迭代器
//        boolean b = it.hasNext();
//        System.out.println(b);
//        Object o = it.next();
//        System.out.println(o);
//        boolean b1 = it.hasNext();
//        System.out.println(b1);
//        Object o1 = it.next();
//        System.out.println(o1);
//        while (it.hasNext()) {
//            System.out.println(it.next());
//        }

        // 双向迭代器 listIterator()
//        ListIterator li = list.listIterator();
//        while (li.hasNext()) {
//            System.out.println(li.next());
//        }
//        System.out.println("===========================");
//        while (li.hasPrevious()) {
//            System.out.println(li.previous());
//        }
        ListIterator li = list.listIterator(2);
        while (li.hasPrevious()) {
            System.out.println(li.previous());
        }

    }
}

LinkedList:基于链表的集合

public class ListDemo4 {
    public static void main(String[] args) {
        // 创建LinkedList对象
        LinkedList list = new LinkedList();
        list.add(3.14);
        list.add(3.14);
        list.add(3.1415);
        list.add(3.1415926);
        list.add(3.149999);
        list.add(0,9999999);
        System.out.println(list);

        System.out.println(list.get(0));
        Iterator it = list.iterator();
        ArrayList集合的遍历
/**
 *  LinkedList集合的遍历
 */
        while (it.hasNext()) {
            System.out.println(it.next());
        }
        System.out.println("======================");
        ListIterator li = list.listIterator(list.size());
        while (li.hasPrevious()) {
            System.out.println(li.previous());
        }
    }
}

Linked实现的队列（双向队列）

public class ListDemo5 {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // 在头尾操作的方法
        list.addFirst("aaa");
        list.addLast("bbb");
        list.add("cccc");
//        System.out.println(list.getFirst());
//        System.out.println(list.getLast());
////        list.removeFirst();
//        list.removeLast();
//        System.out.println(list);

        // element()
        System.out.println(list);
        System.out.println(list.element());
        // offer(E e)
        list.offer("dddd");

        list.offerFirst("蘋蘋");
        list.offerLast("辰辰");

        // peek()
//        System.out.println(list.peek());
        // poll
        System.out.println(list.poll());
        System.out.println(list.pollFirst());
        System.out.println(list.pollLast());

        System.out.println(list);


    }
}

LinkedList栈结构

栈的特征：FILO(先进后出)

public class ListDemo6 {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // push(e):压栈，将对象放入栈内存
        list.push("a");
        list.push("b");
        list.push("c");
        System.out.println(list);
        // pop():出栈，将栈里面对象取出
        System.out.println(list.pop());
        System.out.println(list);

    }
}