总结
数据结构
-
数据结构：保存数据的一种方式
-
常见的数据结构
-
通过数组来保存，基于数组的数据结构（动态数组，长度可变的数组）
基于数组的结构的优缺点 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); } } -
讲解ArrayList和LinkedList的使用场景
- 底层结构不同
- ArrayList底层是数组：查改性能好，增删插性能差
- LinkedList底层是一个双向链表，增删插性能好，查改性能差
LinkedList底层 底层还是一个队列，还是一个栈
- 底层结构不同