基础知识

为什么学数据结构与算法？

• 遇到一个实际问题，需要解决两个事情
• 如何将会数据存储在计算机中
• 用什么方法策略解决问题
• 轮子虽然不需要自己造了，但是至少需要知道轮子为什么是圆的

什么是数据结构

数据项：一个数据元素可以由若干数据项组成】

数据对象：有相同性质的数据元素的集合，是数据的子集

数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合

逻辑结构与物理结构

• 逻辑结构：是指数据对象中元素之间的相互关系
• 集合结构
• 
  
• 线性结构
• 
  
• 树状结构
• 
  
• 图形结构
• 
  
• 物理结构：是指数据的逻辑结构在计算机中的存储形式
• 顺序存储结构
• 
  
• 链式存储结构
• 
  

数据结构研究的内容

0. 线性表：零个或多个数据元素的有序序列
1. 队列：只允许在一端插入，而在另一端进行删除操作的线性表
2. 堆栈：栈是限定仅在表尾进行插入和删除操作的线性表
3. 树：树是n个节点的有序集。节点可以像树一样越向叶子节点就没有交集
4. 图论：由顶点的又穷空集合和顶点之间边的集合组成
5. 排序和查找算法：排序是对数据进行顺序排列，查找是在大量数据中寻找我们需要的数据的过程

数组

0. 简单：数组是一种最简单的数据结构
1. 占据连续内存: 数组空间连续，按照申请的顺序存储，但是必须指定数组大小
2. 数组空间效率低：数组中经常有空闲的区域没有得到充分的应用
3. 操作麻烦：数组的增加和删除操作很麻烦

顺序表

线性表

零个或多个元素的有序序列

物理结构划分

0. 顺序存储结构(一个萝卜一个坑，美女排队)

2. 链式存储结构(天龙三兄弟)

数据节点

 class Student {
   Student[40];
   int size;
   ...
 }

顺序表的增删改查

删除节点：将节点后每个元素往前挪一位

看ArrayList的源码

0. ArrayList 是由数组来实现数据存储的
1. ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全(执行效率高) 看源码，在多线程情况下，不建议使用ArrayList

• 通过数组来保存每个元素

 transient Object[] elementData;

扩展：为什么用transient修饰elementData？

被transient修饰的变量不参与序列化和反序列化。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。

elementData不参与默认的序列化和反序列化，不代表没有进行序列化和反序列化 ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。 不直接用elementData来序列化，而采用上诉的方式来实现序列化是因为elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

ArrayList的底层操作机制源码分析（重点）

0. ArrayList中维护了一个Object类型的数组 elementData [debug看源码]
1. transient Object[] elementData; //transient 表示瞬间，短暂的，表示该属性不会被序列化
2. 当创建对象的时，如果使用的是无参构造器，则初始elementDate的容量是0 (JDK7是10)
3. 当添加元素时，如果使用的是无参构造器，如果需要扩容，则调用grow方法，否则直接添加元素到合适位置
4. 如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容elementData为10，如果需要再次扩容的话，则扩容elementData为1.5倍

    //创建了一个空的elementData数组 = {}
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    } 
 
    //执行list.add
    //1. 先确定是否要扩容
    //2. 然后再执行扩容的操作
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
 
    //该方法确定minCapacity
    1.第一次扩容为10
    private void ensureCapaccityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCaacity);
    }
 
    //1. modCount++ 记录集合被修改的次数
    //2. 如果elementData的大小不够，就调用grow()去扩容
    //3. 
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
 
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
 
    //1. 真的扩容
    //2. 使用扩容机制来确定扩容到多大
    //3. 第一次newCapacity = 10
    //4. 第二次及其以后，按照1.5倍扩容
    //5. 扩容使用的是Arrays.copyOf()
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

• 添加add
• 默认在尾部添加
• /**
  * Appends the specified element to the end of this list.
  *
  * @param e element to be appended to this list
  * @return <tt>true</tt> (as specified by {@link Collection#add})
  */
  public boolean add(E e) {
  ensureCapacityInternal(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
  }
• 调用ensureCapactityInternal方法确保列表中有足够的元素来容纳新元素，不足会进行扩容或重新分配内存空间，再添加元素
• System.arraycopy函数
• src – 源数组。
• srcPos – 源数组中的起始位置。
• dest – 目标数组。
• destPos – 目标数据中的起始位置。
• length – 要复制的数组元素的数量。
• 在特定序号添加元素
• public void add(int index, E element) {
  rangeCheckForAdd(index);
  
  ensureCapacityInternal(size + 1); // Increments modCount!!
  System.arraycopy(elementData, index, elementData, index + 1,
  size - index);
  elementData[index] = element;
  size++;
  }
• 通过arrayCopy将index的元素移动到index+1的位置，再将新添加的元素放在空出来位置上，size++
• 添加所有addAll
• 默认从尾部添加
• public boolean addAll(Collection<? extends E> c) {
  Object[] a = c.toArray();
  int numNew = a.length;
  ensureCapacityInternal(size + numNew); // Increments modCount
  System.arraycopy(a, 0, elementData, size, numNew);
  size += numNew;
  return numNew != 0;
  }
• 将新添加的集合先转为array,并记录size，确保容量是否足够后，通过System.arraycopy将新添加的数据复制到数组尾部
• 从指定位置从Collection添加所有
• 
  
• public boolean addAll(int index, Collection<? extends E> c) {
  rangeCheckForAdd(index);
  
  Object[] a = c.toArray();
  int numNew = a.length;
  ensureCapacityInternal(size + numNew); // Increments modCount
  
  int numMoved = size - index;
  if (numMoved > 0)
  System.arraycopy(elementData, index, elementData, index + numNew,
  numMoved);
  
  System.arraycopy(a, 0, elementData, index, numNew);
  size += numNew;
  return numNew != 0;
  }

如果插入元素数大于index,将index后的元素移到新元素之后，再将新元素从index处开始复制

• 删除remove
• 删除指定索引的元素
• public E remove(int index) {
  if (index >= size)
  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
  modCount++;
  E oldValue = (E) elementData[index];
  
  int numMoved = size - index - 1;
  if (numMoved > 0)
  System.arraycopy(elementData, index+1, elementData, index,
  numMoved);
  elementData[--size] = null; // clear to let GC do its work
  
  return oldValue;
  }
• 先判断index是否越界，越界则抛出异常
• 记录原始数据
• 计算位移数
• public boolean remove(Object o) {
  if (o == null) {
  for (int index = 0; index < size; index++)
  if (elementData[index] == null) {
  fastRemove(index);
  return true;
  }
  } else {
  for (int index = 0; index < size; index++)
  if (o.equals(elementData[index])) {
  fastRemove(index);
  return true;
  }
  }
  return false;
  }
• 改set
• /**
  * Replaces the element at the specified position in this list with
  * the specified element.
  *
  * @param index index of the element to replace
  * @param element element to be stored at the specified position
  * @return the element previously at the specified position
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
  public E set(int index, E element) {
  if (index >= size)
  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
  E oldValue = (E) elementData[index];
  elementData[index] = element;
  return oldValue;
  }
• 查 get
• public E get(int index) {
  if (index < 0 || index >= this.size)
  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  if (ArrayList.this.modCount != this.modCount)
  throw new ConcurrentModificationException();
  return (E) ArrayList.this.elementData[offset + index];
  }

Arraylist的继承关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Isterator 接口 -> 用来快速轮询容器

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        // prevent creating a synthetic constructor
        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                // update once at end to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

源码解析

0. ArrayList的大小是如何自动增加的？
1. add函数
2. 什么情况下使用ArrayList？
3. 优点：尾插效率高，支持随机访问 -> 内部是数组
4. 缺点：中间插入或者删除效率低 -> 需要对后面所有节点进行位移
5. 很少删除或插入节点，需要顺序查找用ArrayList
6. 在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？
7. ArrayList如何顺序删节点
8. 迭代器 或 for循环从后往前删
9. ArrayList的遍历方式
10. 迭代器
11. for循环(不能随便用)
12. forEach

作业：

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

https://leetcode.com/problems/search-insert-position/

https://leetcode.com/problems/search-insert-position/

链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元还是可以连续的，也可以是不连续的

添加节点

注意顺序：

① p.next = s

② s.next = p.next

为什么是这个顺序，反了会怎样？

s.next = p.next

p.next = s

会导致s.next指向s

删除节点：

p.next = p.next.next

修改节点

p.data = new data();

查询节点

while(p.next != I)｛
   p = p.next;
｝

双链表

双链表的存储结构单元

private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;
}

双链表的表现形式

增加节点

1: s.next = p.next;

2 p.next.prev = s;

3 s.prev = p;

4 p.next = s;

注意:2和4不能调换位置

删

p.next.prev = p.prev;

p.pre.next = p.next;

源码解析

List总结

0. List是一个接口，它继承于Collection接口，它代表着有序的队列
1. AbstractList是一个抽象类，它继承于AbstractCollection。AbstructList实现List接口中处理size(), get(int location) 之外的函数
2. AbstructSequentialList是一个抽象类，它继承于AbstructList。AbstructSequentialList实现了"链表中，根据index索引值操作链表的全部函数"
3. ArrayList、LinkedList、Vector、Stack是List的四个实现类

面试总结

0. ArrayList与LinkedList的区别？

作业：

0. 手写一个单链表，并且实现单链表元素的逆置，（a0, a1,a2,a3,..an）-> (an,an-1,… a1, a0),算法的空间复杂度和时间复杂度经可能低。
1. 手写双向链表， 实现增删改查，同时对比自己的LinkList 和源码Linkedlist的异同点
2. 对比源码Arraylist 和LinkedList 的优缺点

算法题：

https://leetcode.cn/problems/merge-two-sorted-lists/

https://leetcode.c/problems/swap-nodes-in-pairs/

https://leetcode.com/problems/copy-list-with-random-pointer/

实现单链表

节点

    //节点的信息
    class Node {
        T data;
        Node next;

        public Node(T data, Node node) {
            this.data = data; //记录当前节点的数据
            this.next = node; //记录当前节点的下一个节点
        }

• 属性：
• data：记录节点的数据
• next：记录下一个节点

属性

LinkedList类

• list ：保存初始节点
• size：记录链表有多少节点

public class LinkedList<T> {
	Node list;
	int size;   
}

构造函数

public LinkedList() {
  	size = 0; //新创建节点数为0
}

添加节点

• 在头部添加节点
• 
  
• 在添加节点后，将新添加的节点作为初始节点
• public void put(T data) { //传入添加节点的数据
  Node head = list;
  Node curNode = new Node(data, list); //创建新节点，其next节点是原首节点
  list = curNode; //将新添加节点作为首节点
  size++; //节点数+1
  }
• 在指定位置添加节点
• 
  
• 
  
• public void put(int index, T data) {
  checkPositionIndex(index);
  Node cur = list;
  Node head = list;
  for (int i = 0; i < index; i++) {
  head = cur;
  cur = cur.next;
  }
  
  Node node = new Node(data, cur);
  head.next = node;
  size++;
  }
• 检查索引是否合法
• //检查index是否在链表范围内
  public void checkPositionIndex(int index) {
  if (!(index >= 0 && index <= size)) {
  //若超过，则抛出节点
  throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
  }
  }

删除节点

• 删除头部节点

单链表实现LRU算法

什么是缓存？

硬件缓存

CPU缓存：位于CPU与内存之间的临时存储器。解决CPU速度和内存速度之间速度差异问题

软件缓存

0. 内存缓存
1. 预先将数据写到了容器(list, map, set)等数据存储单元中，就是软件内存缓存
2. 数据库缓存
3. 网络缓存

内存缓存淘汰机制

0. FIFO (First In, First Out)
1. LFU (Least Frequently Used)
2. LRU (Least Recently Used) "喜新厌旧"

LRU算法

0. 新数据插入到链表头部
1. 当缓存命中(即缓存数据被访问)，数据要移到表头
2. 当链表满的时候，将链表尾部的数据丢弃

队列

线程池

队列在线程池中是什么情况

队列的存储结构

队列的基本操作

队列的分类

ThreadPoolExecutor线程池实现类

private final BlockingQueue<Runnable> workQuene;								//阻塞队列
private final ReentrantLock mainLock = new ReentrantLock(); 		//互斥锁
private final HashSet<Worker> Workers = new HashSet<Worker>();	//线程集合 一个Worker对应一个xiancheng
private final Condition termination = mainLock.newCondition();  //终止条件
private int largestPoolSize;																		//线程池中线程数量曾经达到过的最大值
private long completedTaskCount;  //已完成任务数量
private volatile ThreadFactory threadFactory;		//ThreadFactory对象，用于创建线程
private volatile RejectedExecutionHandler handler; //拒绝策略的处理句柄
private volatile long keepAliceTime; 						//线程池维护线程所允许的空闲时间
private volatile boolean allowCoreThreadTimeOut;
private volatile int corePoolSize;							//线程池维护线程的最小数量，哪怕是空闲的
private volatilee int maximumPoolSize;					//线程池维护的最大线程数量

线程池排队：

假设队列大小为10，corePoolSize为3，maximumPoolSize为6，那么当加入20个任务时，执行的顺序应该是怎样的？

0. 首先执行1、2、3
1. 然后任务4-13被放入队列
2. 这时候队列满了，任务14、15、16会被马上执行
3. 而任务17-20则会抛出异常
4. 最终顺序：1、2、3、14、15、16、4、5、6、7、8、9、10、11、12、13

什么是队列？

队列(queue)又叫先进先出表，它是一种运算受限的线程表。

其权限是仅允许在表的一端进行插入和另一端取数据，插入是数据的一端是队尾，取数据的一端是队头

栈

什么是栈？

栈(stack)又名后进先出表，它是一种运算受限的线性表

其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对的，把另一端称为栈底

栈基本概念

进栈：入栈或压栈，将新元素放到栈顶 元素的上面，使之成为新的栈顶元素

出栈：退站，将栈顶元素删除掉，使之与其相邻的元素成为新的栈顶元素

栈的面试题

Java中的Stack是通过Vector来实现的，这种设计被认为是不良的设计，说说你的看法？

由于Stack继承了Vector，有了很多不符合栈的特性的方法 ，比如add方法

栈的经典应用-逆波兰表达式法

逆波兰表达式是一种利用栈来进行运算的数学表达式

• 9 + （3-1）* 3 + 10 / 2
• 标准四则运算表达式——中缀表达式
• 9 3 1 - 3 * + 10 2 / +
• 计算机采用的——后缀表达式：逆波兰表达式

中缀表达式转为后缀表达式：

0. 从左至右扫描一中缀表达式
1. 若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数栈
2. 若读取的是运算符
0. 该运算符为左括号"("，则直接存入运算符栈堆
1. 该运算符为右括号")"，则输出运算堆栈中的运算符到操作数堆栈，直到遇到左括号为止，此时抛弃该左括号
2. 该运算符为非括号运算符
3. 若运算符为非括号运算符：
0. 若运算符堆栈栈顶的运算符为左括号，则直接存入运算符堆栈
1. 若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈
2. 若比运算符堆栈栈顶的运算符优先级低或相等，则输出栈顶运算符到操作数堆栈，直至运算符栈栈顶运算符低于(不包括等于)该运算符优先级，或为左括号，并将当前运算符压入运算符堆栈
3. 当表达式读取完后运算符堆栈中尚有运算符时，则依序取出运算符到操作数栈，直到运算符堆栈为空