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

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

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

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

逻辑结构与物理结构逻辑结构：是指数据对象中元素之间的相互关系集合结构

线性结构

树状结构

图形结构

物理结构：是指数据的逻辑结构在计算机中的存储形式顺序存储结构

链式存储结构

数据结构研究的内容线性表：零个或多个数据元素的有序序列队列：只允许在一端插入，而在另一端进行删除操作的线性表堆栈：栈是限定仅在表尾进行插入和删除操作的线性表树：树是n个节点的有序集。节点可以像树一样越向叶子节点就没有交集图论：由顶点的又穷空集合和顶点之间边的集合组成排序和查找算法：排序是对数据进行顺序排列，查找是在大量数据中寻找我们需要的数据的过程数组简单：数组是一种最简单的数据结构占据连续内存: 数组空间连续，按照申请的顺序存储，但是必须指定数组大小数组空间效率低：数组中经常有空闲的区域没有得到充分的应用操作麻烦：数组的增加和删除操作很麻烦顺序表线性表

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

物理结构划分顺序存储结构(一个萝卜一个坑，美女排队)链式存储结构(天龙三兄弟)数据节点

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

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

看ArrayList的源码ArrayList 是由数组来实现数据存储的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的底层操作机制源码分析（重点）

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

* 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;

}查 getpublic 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();        }    }

作业：

链表

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

添加节点

注意顺序：

① 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;

源码解析

优点

缺点

应用

顺序表

存储空间连续 允许随机访问 尾插、尾删方便

插入效率低 删除效率低 长度固定

哪哪都在用

单链表

随意进行增删改 插入效率高 长度可以随意删改

内存不连续 不能随机查找

双链表

随机进行增删改 插入效率高 删除效率高O 长度可以随意修改 查找效率比单链表快一倍

应用：linkedList

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

作业：

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

算法题：

实现单链表节点

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

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速度和内存速度之间速度差异问题

软件缓存内存缓存预先将数据写到了容器(list, map, set)等数据存储单元中，就是软件内存缓存数据库缓存网络缓存内存缓存淘汰机制FIFO (First In, First Out)LFU (Least Frequently Used)LRU (Least Recently Used) "喜新厌旧"LRU算法新数据插入到链表头部当缓存命中(即缓存数据被访问)，数据要移到表头当链表满的时候，将链表尾部的数据丢弃队列线程池

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

队列的存储结构

队列的基本操作

队列的分类

ThreadPoolExecutor线程池实现类

private final BlockingQueue<Runnable> workQuene;								//阻塞队列private final ReentrantLock mainLock = new ReentrantLock(); 		//互斥锁private final HashSet<Worker> Workers = new HashSet<Worker>();	//线程集合 一个Worker对应一个xianchengprivate 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个任务时，执行的顺序应该是怎样的？

首先执行1、2、3然后任务4-13被放入队列这时候队列满了，任务14、15、16会被马上执行而任务17-20则会抛出异常最终顺序：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 / +计算机采用的——后缀表达式：逆波兰表达式

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

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