数据结构 1 线性表详解 链表、 栈 、 队列 结合JAVA 详解
- 2020 年 3 月 6 日
- 笔记
前言
其实在学习数据结构之前，我也是从来都没了解过这门课，但是随着工作的慢慢深入，之前学习的东西实在是不够用，并且太皮毛了。太浅，只是懂得一些浅层的，我知道这个东西怎么用，但是要优化、或者是解析，就不知道该咋弄了。比如JAVA 最有名的几个容器:
- List
- Set
- MAP
- Queue
这些都是涉及到有关数据结构的，以及一些简单的算法。排序、冒泡排序、二分法这些，都要涉及到时间复杂度、以及数据结构的知识，这门课，还是很重要的。
为了啥
其实数据结构，结构这个词，就是将我们原本的一些数据，按照某种结构放到一起，为了更加便利以及后期对于这些数据的利用。不能胡来，乱放一遭，那样整理起来很麻烦，并且不方便以后的二次利用。
平时使用的数据，要么是基本类型、要么就是引用类型、数组、这些就是最基本的。加入需要存一个比如层级结构的岗位，那普通的数组就没有办法了。
这里我们所涉及到的内容其实就是 数据的 结构
结构分类
数据结构的分类，到底有哪些呢，如何去理解他们，就是我们本节课的内容。这里我们将接触到线性表、树状图、图存储结构等
线性表
线性表其实和数组有些类似。我们都知道，所有数据的类型都可以通过
最基本的 数组 指针（引用类型） 这两种最基本的类型构造。
线性表可以细分为：
- 顺序表
- 链表
- 栈
- 队列
本节课就围绕线性表，将这几种类型依次解释清楚
顺序表
顺序表最常见的，当然就是数组（不等同数组），满足 一对一 何谓一对一呢，就是其里面存储的元素，他们的类型，都是存在相同类型的关系，并且紧挨着连接起来的。例如：
String [] array = new String[] {"a","b","c"};类似于这种，除掉首元素和尾元素，每个元素前后都有相邻的元素。这样的我们就叫做顺序表
JAVA 里面我们知道最基本的List 接口，下面有一个 ArrayList
ArrayList 底层就是以一个数组，其就是一个顺序表。
基本操作
我这里全部以JAVA 为例。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }通过这个构造函数，我们可以发现，传入一个指定的大小数，大于0，则指定基本数组的大小为传入大小。 虽然这个数组是支持自动扩容的，我们还是研究一下
add() 增加元素到尾部
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }ensureCapacityInternal是对数组的监测，若大小不足以容纳，则扩容的机制
这里的增加元素其实很简单，就将元素放到size ，也就是容器当中元素数的位置，首次放入元素的时候，size 初始化就是0 而后自增，很简单
add() 插入元素
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++; } rangeCheckForAdd 检查插入位置有没有超过数组大小。则直接抛出异常
扩容后，将插入点后面的元素往后移动一个位置，通过System.arraycopy复制方式实现
查找指定下标 get()
public E get(int index) { rangeCheck(index); return elementData(index); }这个就不细说了，太简单了。
remove() 移除元素
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = 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; }这个和上面指定位置插入一个元素刚好相反，把指定位置的元素移除掉后，后面的元素往前移动一位，而后将最后元素的位置进行清理。
总结
顺序表最大的特点是：查询快，因为是数组，直接下标出。插入和移除就比较慢了。因为要移动、复制数组，很麻烦
链表
在上面我们已经说过了，任何的数据类型都可以通过最基本的数组和指针构造。链表也不例外，相比于数组，数组则是定长的，不管存储的满否，都申请了一定大小的内存空间，而链表则不是，链表的空间是随用随申请，数据的位置相比于数组，其实不连续的，一般来说，需要在元素上指定下一个元素的指针，来达成链接关系。
每个元素上都有一块位置用于指向下一个元素（指针）
这里我画的不连续也就是为了表示元素的不连续性
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }链表在JAVA 当中最具代表性的就是 LinkedList(双向链表)，就是每个元素会带有它的上一个节点和下一个节点的指针，我们图上画出来的是单向链表。
add(E e)
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }新下挂一个节点的时候，将最后一个节点（null）保存到 l 下，然后构造出一个新节点，将本节点作为最后一个最后一个节点。
add(int Index,E e)
void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }这里两个参数，E 表示将要插入的元素，
两边链表断开，new 一个新的节点，连接即可。
get(i) 查找
Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 链表的查找指定下标就比较费时了。需要一个个遍历。其实是很麻烦的。
remove(i)
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }移除一个指定位置的节点，这个其实和增加一个节点时候其实是类似的。将上下节点对于这个节点的引用进行修改即可。
小结
链表还是比较适合于快速增加、删除、不适合于索引。因为需要全盘遍历
栈 Stack
堆还是按照数组为基础实现的，只不过它是一个半开的数组，怎么理解这个半开的数组呢，如图，就好像一个瓶子一样，往里面丢元素，先进后出原则
入栈 push
将一个元素加入的栈里面，此时的元素是最外层的一个元素，此时执行出栈命令，则这个元素会被删除并返回
出栈 pop
删除此堆栈顶部的对象，并将该对象作为此函数的值返回。
查看 peek
通过 peek 查看当前栈顶的元素，只是查看，并不执行删除
队列 Queue
队列遵循先进先出原则
队列还提供额外的插入，提取和检查操作。 这些方法中的每一种都有两种形式：如果操作失败，则抛出一个异常，另一种返回一个特殊值（ null或false ，具体取决于操作）。
这里使用 ArrayBlockingQueue 以数组实现的阻塞队列
BlockingQueue<String> strings = new ArrayBlockingQueue<String>(2);一个有限的blocking queue由数组支持。 这个队列排列元素FIFO（先进先出）。 队列的头部是队列中最长的元素。 队列的尾部是队列中最短时间的元素。 新元素插入队列的尾部，队列检索操作获取队列头部的元素。
这是一个经典的“有界缓冲区”，其中固定大小的数组保存由生产者插入的元素并由消费者提取。 创建后，容量无法更改
入队 add()/offer()/put()
add 和 offer 都可以将元素加入到队列中。但是add 在超过队列容量的时候会抛出异常，offer 则会返回false
而put 操作则会在队列没有空间的时候阻塞，直到队列有空间执行
出队 poll()/take()
- poll检索并删除此队列的头，如果此队列为空，则返回 null 。
- take 在没有元素的时候则会阻塞
小结
通过本小结，我们已经学习到了最基本的线性表，而线性表又包含哪些呢
- 顺序表 ArrayList
- 链表 LinkedList
- 栈 Stack
- 队列 Queue
下一节我们将继续学习有关于字符串、数组、广义表等内容
参考：
http://c.biancheng.net/view/3352.html
