数据结构之表的总结
在项目中当我们使用list、ArrayList、HashMap等等有没有想过他们到底是如何实现的呢？为什么要使用他们？为什么在面试的时候都要求会数据结构呢？数据结构强大在哪里呢？
本文讲解最基础也是最简单和最基本的三种数据结构：表、栈和队列，在程序的任何地方都至少使用了一种这样的数据结构。
文章内容较长，你可以泡杯咖啡慢慢看。
接下来我们慢慢揭开这层面纱，带你走进数据结构。
1. 理解数据结构中的表
数据结构是计算机内存中数据的一种安排也可以理解为数据单元的一种抽象或者组织形式。
抽象数据类型（abstract data type,ADT）：是带有一组操作的一些对象的集合。诸如表、集合、图以及与他们各自的操作一起形成的这些对象都可以被看做是抽象数据类型。
什么是表？
A0,A1,A2,A3......An-1; 表的大小为n.可以insert，remove 从某个位置插入和删除元素,find 查找某个元素.等等操作。我们称之为数据结构中的表。也可以说表是带有一组操作的一些对象的集合。
数据结构中的表又分为：顺序表和链表。还有顺序表和链表结合的一种表为哈希表。
相信你已经知道什么是表了，你一定会想
- 有一种表就行了，为什么有好几种表呢？
- 这几种表的区别呢？
- Java中那些地方用到了这些表呢？
- 这些表有哪些优点和缺点呢？
- Java源码中这些表是如何实现的呢？
- 能不能自己实现一种表呢？
- 面试中经常会问到关于表的那些问题呢？
那么不(biao)要着急,带着疑问接下来 一 一 讲解这三种表的结构。
如果你的咖啡凉了或者没了，重新泡一杯，接下来需要你聚精会神的来看了。
1-1. 顺序表
顺序表：对表的所有这些操作都可以通过数组来实现。
实际上顺序表就是数组和对数组的操作:insert、remove、find等等。那么这也应验了上述所说的表是带有一组操作的一些对象的集合。
顺序表的类模型
class Array {
arrays[40];
int size;
}
我们都清楚创建一个数组是由固定容量创建的，那么固定容量的数组，当达到一定的容量时，如何对数组扩容呢？可以用双倍的容量创建一个不同的数组，这样就解决了使用数组最扬中的问题。看下面的一段代码为对数组的扩容：
int[] arr = new int[10];
....
//扩大arr的容量
int[] newArr = new int[arr.length * 2];
for(int i = 0;i<arr.length;i++){
newArr[i] = arr[i];
}
arr = newArr;
时间复杂度为O(1),对性能上消耗不大，同时要查找数组中的某个元素，也很简单，arr[i],随机访问效率很高，不过插入和删除操作却花费很昂贵的花销，这要看插入和删除发生在什么位置。
如果从第0个位置或中间某个位置开始插入，需要将整个或部分元素向后移一个位置。
无标题.png
如果从第0个位置或中间某个位置删除，那么整个或一些元素要向前移动一个位置。
顺序表中间或头部删除
而这种两个操作时间复杂度就很高了，最坏的情况为O(N)，效率非常低。
如果插入和删除发生在尾部，那就不需要移动元素，只花费O(1)的时间。
总结一下：在项目中如果对数组进行频繁的插入和删除操作(除了尾部的插入和删除)，是不建议用顺序表这种数据结构的。
顺序表的优点：尾部插入或删除效率高；支持随机访问。
顺序表的缺点：中间或头部插入或删除效率低。
应用：ArrayList 底层便是对数组的操作。
通过以上讲解，顺序表是非常简单的，说白了你只要会数组的一些操作就会顺序表，下面来看看ArrayList底层是如何实现的。
1-1-1. ArrayList 源码解析
建议打开ArrayList 源码，根据以下思路分析。
- ArrayList 的继承结构开始分析
public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, Serializable {
ArrayList 实现list 接口能对它进行队列操作.
ArrayList 实现了Cloneable接口，覆盖了函数clone().
ArrayList 实现了java.io.Serializable 接口，支持序列化，能通过序列化传输数据.
ArrayList 实现了RandomAccess接口是List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。在对List特别的遍历算法中，要尽量来判断是属于RandomAccess(如ArrayList)还是SequenceAccess(如LinkedList），因为适合RandomAccess List的遍历算法，用在SequenceAccess List上就差别很大。
可以看到ArrayList extends AbstractList
AbstractList<E> extends AbstractCollection<E> implements List<E>
AbstractCollection<E> implements Collection<E>
Collection<E> extends Iterable<E>
从Collection类中可以看到，一些常见的方法，这些方法都是在用Array List时常用的方法。
Collection 接口扩展了Iterable接口
int size();
boolean isEmpty();
boolean contains(Object var1);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] var1);
boolean add(E var1);
boolean remove(Object var1);
boolean containsAll(Collection<?> var1);
boolean addAll(Collection<? extends E> var1);
boolean removeAll(Collection<?> var1);
实现Iterable接口的那些类可以增强for循环，可以看Iterable的代码
Iterator<T> iterator();
default void forEach(Consumer<? super T> var1) {
Objects.requireNonNull(var1);
Iterator var2 = this.iterator();
while(var2.hasNext()) {
Object var3 = var2.next();
var1.accept(var3);
}
}
- ArrayList 的属性
/**
*
ArrayList的元素存储在其中的数组缓冲区。
ArrayList的容量是这个数组缓冲区的长度。当添加第一个元素时，任何具有elementData == EMPTY_ELEMENTDATA的空ArrayList将展开为DEFAULT_CAPACITY。
私有包允许从java.util.Collections访问。
*/
transient Object[] elementData;
/**
* 记录数组的大小
*
* @serial
*/
private int size;
/**
* 数组默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 一个空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
顺便提一下关键字transient
关键字transient 标识的字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。
然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
- 构造函数分析
// 定义容量 也就是数组的大小 需计算好
public ArrayList(int initialCapacity) {
super();
// 若传入的值小于0 抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//初始化定义容量的数组
this.elementData = new Object[initialCapacity];
}
/**
* 默认构造函数 初始化一个空的数组
*/
public ArrayList() {
super();
// private static final Object[] EMPTY_ELEMENTDATA = {};
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 构造一个含有元素的列表
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
// 初始化含有元素的数组
elementData = c.toArray();
// 数组的大小
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
- 尾部插入
public boolean add(E e) {
// 检查插入一个元素后确保数组有足够的容量
ensureCapacityInternal(size + 1);
//进行完数组的自增长后才向数组中添加元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果elementData 是个空数组 没有元素
if (elementData == EMPTY_ELEMENTDATA) {
//minCapacity 取DEFAULT_CAPACITY 和 minCapacity 的最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 确保显式容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果插入元素后的大小 minCapacity 大于数组的长度则自增长数组的容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 实现数组的自增长
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:
// 对数组进行copy 扩大数组的长度
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
5.中间插入
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 同理 首先确保数组容量
ensureCapacityInternal(size + 1);
// 将插入元素 之后的所有元素后移一位
src:源数组；
srcPos:源数组要复制的起始位置；
dest:目的数组；
destPos:目的数组放置的起始位置； l
ength:复制的长度。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 向数组中index位置添加元素
elementData[index] = element;
size++;
}
- 查找元素
非常简单并且效率 非常高
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
- 替换元素
非常简单并且效率 非常高
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;
}
- 删除元素
删除某个位置的元素 效率低
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)
//对数组进行copy src:源数组； srcPos:源数组要复制的起始位置；
//dest:目的数组；
//destPos:目的数组放置的起始位置； l
//ength:复制的长度。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// size - 1 前一位置空
elementData[--size] = null; // clear to let GC do its work
// 返回删除的元素
return oldValue;
}
同理 删除元素 效率低
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;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
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
}
以上就是ArrayList 的核心方法.
好吧，不管你是否一口气读完，反正我写到这就要累死了。。。。。。
看个妹纸图，放松一下。
妹纸图
1-1-2. 手写ArrayList
额。。。。 看完妹纸图，我们喝瓶营养快线。。。继续撸
既然我们分析了ArrayList的源码，但是仅仅是看明白了，是不能够掌握了，只有真正的手撸(coding)出来,才能够真正掌握，打实基础。万丈高楼平地起，盖起一栋楼，一半的时间都用在打地基上了。
(本例实现参考数据结构与算法分析一书)
我们将实现主要的核心代码：
- 提供范型的实现。
- 保持基础数组，数组的容量以及存储在list中的当前个数。
- 提供一种扩展数组容量的机制。通过获得一个新数组，将老数组拷贝到新数组中来改变数组的容量。
- 提供get和set的实现。
- 提供基本的方法如add、size、isEmpty、clear、remove。
- 实现Iterator接口。这个类将存储迭代序列中的下一项的下标，并提供next、hasNext、和remove等方法的实现。
MyArrayList 实现非常简单只要你将前面的ArrayList源码弄懂了，就很好实现。注释都在代码中大家自己看吧！
public class MyArrayList<T> implements Iterable<T> {
//默认数组容量为10
private static final int DEFAULT_CAPACITY = 10;
//存储MyArrayList的大小
private int size;
//数组
private Object[] Items;
private static final Object[] EMPTY_ELEMENTDATA = new Object[DEFAULT_CAPACITY];
public MyArrayList() {
size = 0;
Items = EMPTY_ELEMENTDATA;
}
// 初始化是将list清空
private void doClear() {
for (int i = 0; i < size; ++i) {
this.Items[i] = null;
}
size = 0;
}
//确保数组有足够的容量 newCapacity 为新的数组容量
private void ensureCapacity(int newCapacity) {
//如果新的容量 大于 数组的大小则增长扩容
int length = Items.length;
if (newCapacity - length > 0) {
Object[] old = Items;
Items = new Object[length + (length >> 1)];
for (int i = 0; i < size; i++) {
Items[i] = old[i];
}
}
}
private T getItems(int index) {
return (T) this.Items[index];
}
//向最后一个位置插入元素
public boolean add(T vlaue) {
ensureCapacity(size + 1);
this.Items[size++] = vlaue;
return true;
}
//向某个位置插入元素
public boolean add(int index, T value) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
ensureCapacity(size + 1);
//第一种循环的方法实现
// for (int i = size - 1; i >=index; i--) {
// Items[i] = Items[i + 1];
// }
//第二种方法实现 Java的API 拷贝数组
System.arraycopy(this.Items, index, this.Items, index + 1, this.size - index);
Items[index] = value;
++size;
return true;
}
//移除某个位置的元素
public T remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
T item = getItems(index);
//第一种循环方法实现
// for (int i = index; i < size - 1; i++) {
// Items[i] = Items[i+1];
// }
//第二种Java API实现
int var3 = this.size - index - 1;
if (var3 > 0) {
System.arraycopy(this.Items, index + 1, this.Items, index, var3);
}
size--;
return item;
}
//清空list
public void clear() {
doClear();
}
//list 的大小
public int size() {
return size;
}
//list 是否为空
public boolean isEmpty() {
return this.size == 0;
}
//获取list中某个位置的元素
public T get(int index) {
// 获取某个元素越界
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return getItems(index);
}
//将list中某个位置的元素替换掉
public T set(int index, T value) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
T oldValue = getItems(index);
Items[index] = value;
return oldValue;
}
@Override
public Iterator<T> iterator() {
return new ArrayListIterator<T>(this);
}
private class ArrayListIterator<T> implements Iterator<T>{
private int current = 0;
private MyArrayList<T> list;
public ArrayListIterator(MyArrayList<T> list) {
this.list = list;
}
@Override
public boolean hasNext() {
return current < list.size();
}
@Override
public T next() {
if (!hasNext()){
throw new NoSuchElementException();
}
return list.get(current++);
}
@Override
public void remove() {
list.remove(--current);
}
}
}
代码已经写完，我们来测试一下吧
@Test
public void testList(){
MyArrayList<String> myArrayList = new MyArrayList<>();
myArrayList.add("0");
myArrayList.add("1");
myArrayList.add("2");
myArrayList.add("3");
myArrayList.add("4");
myArrayList.add("5");
myArrayList.add("6");
System.out.println("remove 3 --> "+myArrayList.remove(3));
for (int i = 0; i < myArrayList.size(); i++) {
System.out.println("list:"+myArrayList.get(i));
}
System.out.println("add 4 --> 10");
myArrayList.add(4,"10");
for (int i = 0; i < myArrayList.size(); i++) {
System.out.println("list:"+myArrayList.get(i));
}
}
看下输出结果
remove 3 --> 3
list:0
list:1
list:2
list:4
list:5
list:6
add 4 --> 10
list:0
list:1
list:2
list:4
list:10
list:5
list:6
结果完全正确，是不是很简单就能实现ArrayList，建议自己手撸一边MyArrayList,加深掌握。
OK，这里休息一下，ArrayList都能手写出来了，链表会难吗？回想我们上述所学到的知识点。
- 什么是表？（表是带有一组操作的一些对象的集合）
- 顺序表的特点？及优缺点？
实践是检验真理的唯一标准。
我们再总结一遍顺序表：回想我们之前些的代码，验证总结是否正确。
顺序表的优点：尾部插入或删除效率高；支持随机访问。
顺序表的缺点：中间或头部插入或删除效率低。
1-2. 链表
为了避免插入和删除的线性开销，保证表可以不连续存储，否则表的每个部分可能需要整体移动，于是便有了链表的思想。解决顺序表的插入和删除效率问题。
链表同时也分为单链表和双链表。
我们带着以下问题来一一讲解
- 链表和顺序表(数组)有那些不同？
- 单链表和双链表的区别？
- 链表的优点和缺点？
1-2-1. 单链表
单链表.jpg
如上图所示，是一个单链表。由一系列节点组成，这些节点不必在内存中相连，每个节点都包含表元素和后继到节点链。通俗到来说，一个节点包含表元素和只向下一个节点指针域。最后一个单元到next链引用null.
可以通过修改next的引用，来优化删除和插入操作。
- 如何进行插入操作呢？
单增.png
如上图所示，在p 和 p.next 中间插入一个s,将插入节点的前一个节点的指针域指向插入节点，插入节点的指针域指向后一个节点，已知p.next = p.next,我们只需将p.next = s , s.next = p.next;只需要O(1)的时间完成了插入操作。
这里思考一下顺序表是如何进行插入操作呢？对比两者的插入操作，很明显链表的插入效率更高。
- 如何进行删除操作呢？
单减.png
如上图所示，如果要删除p.next,将删除节点的前一个指针域指向删除节点的后一个节点，只需要将p.next = p.next.next;就完成了删除操作。
很明显链表的删除效率要比顺序表高。
-
如何进行查找操作呢？
链表的查找，需要从表的第一个节点开始然后用后继的next指针域遍历该表即可。
很明显链表的的查找要比顺序表(数组)实现的效率低。
链表的查找操作需要for循环，而顺序表a[i].
总结：
通过上述讲解，可以很快的分析出链表的优点和缺点。
优点：插入和删除效率高。
缺点：不支持随机访问(查找要循环的方式查找 效率低)
Android 中的应用场景 MessageQueue
很显然链表虽然解决了顺序表(数组)的缺点，同时链表也存在着缺点。
大致明白了链表的思想，接下来通过代码来实现单链表。
单链表模型类：
class List{
class Node{
Object data;
Node next;
}
}
回忆以下顺序表的模型类：
class List{
Object[] o;
int size;
}
很明显顺序表是存储的数组，而链表存储的是一个个的节点node,同时不用担心链表容量的问题。
1-2-1-1. 手写单链表
我们撸起袖子加油干，完成手写单链表再休息。
新建一个SingleList<E>类，注意所有的方法都是在SingleList中。
第一步 新建节点
public class SingleList<E> {
//1 首先要写一个节点类
private static class Node<E>{
E date;
Node<E> next;
public Node(E date, Node<E> next) {
this.date = date;
this.next = next;
}
}
}
第二步 属性
//第一个节点
private Node<E> frist;
//链表的大小
private int size;
第三部 基础操作
//尾部插入
public void add(E date){
lastAdd(date);
}
private void lastAdd(E date) {
Node<E> newNode = new Node<E>(date,null);
Node p = last;
last = newNode;
if (p == null){
frist = newNode;
}else {
p.next = newNode;
}
size++;
}
//中间插入
public void add(E data, int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == size) {//尾部插入
lastAdd(data);
} else {//中间插入
if (index == 0) {//插入第一个位置
Node<E> l = frist;
Node<E> newNode = new Node<>(data, l);
frist = newNode;
} else {//中间插入
//查找插入位置的前一个位置
Node<E> perNode = findNode(index - 1);
Node<E> next = perNode.next;
Node<E> newNode = new Node<>(data,next);
perNode.next = newNode;
}
size++;
}
}
private Node<E> findNode(int i) {
Node<E> l = frist;
for (int j = 0; j < i; j++) {
l = l.next;
}
return l;
}
//删除某个位置的节点
private void remove(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == 0) {//删除头部
Node<E> l = frist;
frist = l.next;
} else if (index == size) {//删除尾部
Node<E> per = findNode(index - 1);//找到尾部的前一个
per.next = null;//删除最后一个节点
last = per;
} else {
Node<E> eNode = findNode(index - 1);//找到要删除的前节点
Node<E> next = eNode.next.next;
eNode.next = next;
}
size--;
}
//获取某个位置的元素
public E get(int index){
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
return findNode(index).date;
}
测试以下 插入、删除和查找。
SingleList<Integer> singleList = new SingleList<>();
singleList.add(1);
singleList.add(2);
singleList.add(3);
singleList.add(4);
singleList.add(5);
// singleList.add(9,0);
// singleList.add(8,5);
// singleList.add(7,2);
// singleList.remove(6);
// singleList.remove(3);
for (int i = 0; i < singleList.size; i++) {
System.out.print(singleList.get(i) + " ");
}
OK，累死了，手撸完上面的代码是否茅厕顿开。。。并不是很难吗。
活动下身体，我们继续。
1-2-1-2. 面试中常问的单向链表的问题
了解了单向链表的实现，手撸一个单链表那是手到擒来了。然而在面试中链表是被提及最频繁的数据结构，当然问题都是有点难度的。
常见的问题(参考剑指offer)：
- 在O(1)时间内从尾到头打印链表（2.3.3）
- 在O(1)时间内删除链表的节点
- 链表中删除重复的节点
- 反转链表
- 合并两个排序的链表
- 链表中倒数第k个节点
- 链表中环的入口节点
- 复杂链表的复制
- 两个链表的第一个公共节点
在上述的手写单链表到代码中扩展
- 从尾到头打印链表
我们先说常见到思路：
这样虽然可以实现，但是很明显没有考虑算法复杂度 嵌套了for循环 O(2)，如果面试这样写是不能过关的。
public void printListReseve() {
System.out.println("从尾到头打印链表：");
for (int i = size - 1; i >= 0; i--) {//从最后一个循环
E node = get(i);//同时循环找到某个节点
System.out.println(" " + node);//
}
}
private Node<E> findNode(int i) {
Node<E> l = frist;
for (int j = 0; j < i; j++) {
l = l.next;
}
return l;
}
public E get(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
return findNode(index).date;
}
完美的实现思路：
解决这个问题肯定是要遍历链表。遍历的顺序是从头到尾，也就是说第一个遍历的节点最后输出，最后遍历的节点第一个输出。这是典型的后进先出，可以用栈实现这种顺序，也就是说每经过一个节点的时候，把该节点放入栈中，遍历完整个链表后，顺序从栈顶输出每个节点的值，此时节点的顺序就反转过来了。
//创建一个栈
Stack<Node> nodes = new Stack<>();
Node<E> frist = this.frist;
while (frist != null) {//顺序遍历链表
nodes.push(frist);//将每个节点放入栈中
frist = frist.next;
}
while (!nodes.empty()) {//将栈的数据顺序从栈顶取出。
Node pop = nodes.pop();
System.out.println(" " + pop.date);
}
很明显上述代码的时间复杂度为O(1)
- 删除链表的节
在O(1)时间内删除链表节点。
在单链表中删除一个节点，常规的做法无疑是从链表的头节点开始，顺序遍历查找要删除的节点，并在链表中删除节点，如下代码：
//删除某个位置的节点
public void remove(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == 0) {//删除头部
Node<E> l = frist;
frist = l.next;
} else if (index == size) {//删除尾部
Node<E> per = findNode(index - 1);//找到尾部的前一个
per.next = null;//删除最后一个节点
last = per;
} else {
Node<E> eNode = findNode(index - 1);//找到要删除的前节点
Node<E> next = eNode.next.next;
eNode.next = next;
}
size--;
}
上述代码的思路是，从头节点顺序遍历找到删除的节点的前一个节点，然后将删除的节点的前一个节点的指针指向删除节点的后一个节点，就可以安全地删除节点并保证链表断开。单向链表中，节点没有指向前一个节点的指针，所以只好从头节点开始顺序查找，这种的思路的时间复杂度自然是O(n).
另一种思路：
是不是一定要得到删除节点的前一个节点呢？答案是否定的
如下链表
a --> b --> .... h --> i --> j --> ...
假设我们要删除i节点，把j节点的内容复制到i节点，接下来再把节点i的指针指向j的下一个节点，再删除节点j,这种方法不需要遍历节点i前面的节点。
但是这种思路还存在一个问题：如果删除的节点位于尾部，没有下一个节点怎么办？仍需要从头遍历到删除节点的前序节点，完成删除操作。
如果链表只有一个节点，需要再删除节点后把链表置空。
代码如下：
public void remove(Node<E> deleteNode){
if (frist==null || deleteNode == null){
return;
}
if (deleteNode.next != null){//删除的为中间节点
Node<E> newNode = deleteNode.next;
deleteNode.date = newNode.date;
deleteNode.next = newNode.next;
newNode = null;
}else if (deleteNode == frist){//只有一个节点
frist = null;
deleteNode = null;
}else {
Node<E> frist = this.frist;
while (frist.next != deleteNode){
frist = frist.next;
}
frist.next = null;
last = frist;
deleteNode = null;
}
size--;
}
这道题实际上是考察打破常规的思维模式，创新思维能力。
- 删除链表中重复的节点
这道题的思路很简单主要考察思维的全面性。
首先我们需要从头遍历整个链表，如果当前节点的值与下一个节点的值相同，为重复节点，可以删除，同时还需要保证链表的相连性。
public void deleteDuplication(){
if (frist == null) return;
Node<E> pNode = this.frist;
Node<E> perNode = null;
while (pNode!=null){
Node<E> next = pNode.next;
boolean needDelete = false;
if (next != null && next.date == pNode.date){
needDelete = true;
}
if (needDelete){
perNode = pNode;
pNode = pNode.next;
}else {
E date = pNode.date;
Node<E> pToBeDel = pNode;
while (pToBeDel!=null && pToBeDel.date == date){
next = pToBeDel.next;
pToBeDel = next;
}
if (perNode == null){
this.frist = next;
}else {
perNode.next = next;
}
pNode = next;
}
}
}
- 反转链表
循环法：
public void reverList() {
Node<E> pNode = this.frist;
Node<E> rever = null;
while (pNode != null) {
Node<E> temp = pNode;
temp.next = rever;
rever = temp;
pNode = pNode.next;
}
frist = rever;
}
image.png
如上图所示：
第一次循环后得到的 --》 temp = 1 curr =2 temp.next = null reve = temp = 1 ;链表的结构就变为 1 --> null 2 --> 3 --> 4.
第二次循环后得到的 --》 temp = 2 curr = 3 temp.next = 1 reve = temp = 2 ;链表的结构就变为 2 --> 1 --> null 3 --> 4
第三次循环后得到的 --》 temp = 3 curr = 4 temp.next = 2 reve = temp = 3 ;链表的结构就变为 3 --> 2 --> 1 --> null 4
....
如此类推就可以得到一个逆置的单链表。
递归法：
/**
* 递归的方式转置
*/
public Node<T> reverse(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> tail = reverse(head.next);
head.next.next = head;
head.next = null;
return tail;
}
public void transterReverse() {
this.frist = reverse(this.frist);
}
image.png
如上图所示递归法的逆置逻辑：
1 --> 2 --> 3 <-- 4
1 --> 2 <-- 3 <--4
1 <-- 2 <-- 3 <--4
1-2-2. 双向链表
上述详细讲解了单链表，那么双链表是什么呢？给一张图你就明白了，请看下图
双链表
很简单其实就是比单链表多了个指针域，这个多的指针域是表示当前节点的前一个节点。这里很容易理解就不再复述了。
1-2-2-1. LinkedList 源码解析
接下来我们来分析LinkedList的源码，看看LinedList是如何实现双链表的。
在分析一个类时，首先分析类的继承关系，再分析构造方法和属性。
LinkedList 继承关系
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- LinkedList 继承 AbstractSequentialList,而 AbstractSequentialList<E> extends AbstractList<E> 在上一期中 ArrayList 继承AbstractList ，AbstractSequentialList 它实现了list 的一些位置相关的操作。
- 实现list 接口能对它进行队列操作。
- Deque双端队列，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两邊进行
- Cloneable 覆盖了函数clone()
- Serializable 支持序列化，能通过序列化传输数据
LinkedList 属性
关键字transient 标识的字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列
化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Seril
izable接口，这个类的所有属性和方法都会自动序列化。
然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属
性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安
全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信
息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存
中而不会写到磁盘里持久化。
总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要
序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目
的地中。
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
每个节点都是存储对象Node，包括(E item;Node<E> next;Node<E> prev;)这就意味着LinkedList 占用的内存会比较大,ArrayList 只包括 E,LinkedList 比ArrayList 占用内存大
private static class Node<E> {
//当前节点的 item
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;
}
}
LinkedList 构造方法
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList 有两个构造方法，第一个就不必说了，第二个构造一个链表，传入的是一个list(interface List<E> extends Collection<E>)
addAll(c) 方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//判断 index >= 0 && index <= size;
checkPositionIndex(index);
//将list 转换成一个数组
Object[] a = c.toArray();
int numNew = a.length;
//若数组的长度为0 返回false 不能构造链表
if (numNew == 0)
return false;
Node<E> pred, succ;
//若插入的位置 == 链表的大小
if (index == size) {
succ = null;
//准备要插入的节点 == last 链表的最后一个节点，准备循环从最后一个节点添加
pred = last;
} else {
//若插入的位置 ！= 链表的大小 找到要插入的位置
succ = node(index);
//准备插入的节点 == 插入位置的前一个节点
pred = succ.prev;
}
//循环数组中的Object 创建Node 节点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建新的节点Node
Node<E> newNode = new Node<>(pred, e, null);
//若准备插入的节点为null 说明 index == size 而 pred = last链表为空
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//succ == null 说明 index == size
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
LinkedList 添加节点
双向链表插入.JPG
- add(E e) 尾部插入
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
//尾部节点
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
//尾部 == 新的节点
last = newNode;
//注意判断尾部是否为空，若尾部last为空 则说明链表为空
if (l == null)
//第一个节点 == newNode
first = newNode;
else
//之前的尾部节点的next 指向新添加的节点
l.next = newNode;
//链表大小加一
size++;
modCount++;
}
- add(int index, E element) 中间插入
public void add(int index, E element) {
//插入的位置必须>=0 并且 <= size
checkPositionIndex(index);
//尾部插入
if (index == size)
linkLast(element);
else
//中间插入 首先找到插入位置的节点
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//插入位置的节点的前一个节点
final Node<E> pred = succ.prev;
//new 要插入的节点
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//插入的位置 < 链表大小的一半 则从左侧 first 节点查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//插入的位置 > 链表大小的一半则从右侧 last 节点查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
LinkedList 删除节点
public E remove(int index) {
checkElementIndex(index);
//要删除某个节点 同样要找到该位置的节点
return unlink(node(index));
}
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 = 删除节点的下一个节点
first = next;
} else {
//删除的节点前一个不为空 删除节点的前一个节点的next
//指向删除节点的下一个节点
prev.next = next;
//将删除节点 prev 置为null
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//将删除节点的item 置为null
x.item = null;
//链表减一
size--;
modCount++;
return element;
}
LinkedList 查找节点
查找节点为耗时较长，算法复杂度为 o(n) = n
Node<E> node(int index) {
// assert isElementIndex(index);
//插入的位置 < 链表大小的一半 则从左侧 first 节点查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//插入的位置 > 链表大小的一半则从右侧 last 节点查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从上述分析我们可以得出，链表(LinkedList)的尾插效率高，中间插入和删除算法复杂度为 o
(n) = n,对比顺序表（ArrayList ）插入删除都用到了复制System.arraycopy(
elementData, index, elementData, index + 1,size - index);
算法复杂度要比双链表的插入和删除复杂度高。如果频繁的插入和删除操作建议用链表的存储结构；
如果要想快速的查找到某条数据建议用顺序表的存储结构。
1-2-2-2. 手写双链表
如何手写一个双链表，我们可以仿照LinkedList 的源码写一个简单的双链表
首先双链表的模型类：
class Node{
Object data;
Node next;
Node per;
}
需要的属性
int size;
Node frist;
Node last;
Node静态类
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;
}
}
完整的代码如下：
public class LinkedList<E> {
public LinkedList() {
}
Node<E> frist;
Node<E> last;
int size;
/**
* 向链表的尾部添加一个元素
*
* @param e
*/
public void add(E e) {
linkLast(e);
}
//中间插入一个元素
public void add(int index, E e) {
if (index < 0 || index > size) return;
if (index == size) {//插入尾部
linkLast(e);
} else {
Node<E> currentNode = node(index);//拿到当前位置要插入的节点
Node<E> prev = currentNode.prev;
Node<E> newNode = new Node<>(prev, e, currentNode);
if (prev == null) {//头部插入
frist = newNode;
} else {//中间插入
prev.next = newNode;//Note : 这里两个位置不能换
}
currentNode.prev = newNode;//Note: 查到的节点prev 要指向新的节点
size++;
}
}
//移除某个节点
public void remove(int index) {
if (index < 0 || index > size) return;
unLinkNode(node(index));
}
private void unLinkNode(Node<E> node) {
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null){
frist = next;
}else {
prev.next = next;
node.prev = null;
}
if (next == null){
last = prev;
}else {
next.prev = prev;
node.next = null;
}
size --;
}
/**
* 获取某个节点的元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index > size) return null;
return node(index).item;
}
//查找某个位置的节点
private Node<E> node(int index) {
if ((size >> 1) < index) {//从尾部开始循环
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = last.prev;
}
return node;
} else {//从头部开始循环
Node<E> node = frist;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
}
private void linkLast(E e) {
Node<E> newNode = new Node<>(last, e, null);
Node<E> l = last;//拿到之前的最后一个节点
last = newNode;//将添加的新节点newNode 赋给last 最后一个节点
if (l == null) {//如果之前的最后一个节点为空
frist = newNode;
} else {//如果之前的最后一个节点不为空
l.next = newNode;
}
size++;
}
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;
}
}
}
OK，到此你已经完全掌握了链表的所有知识，以后面试如果问到链表的问题你完全可以装逼一把。休息十分钟。。。。。。
1-3. 哈希表（Hash）
为什么有哈希表这个数据结构？我们回忆以下链表和顺序表的优缺点。
众所周知数据结构中表分为顺序表和链表
-
顺序表的特点：寻址容易，插入删除困难。如Array list 如果对大量对数据进行插入和删除性能会非常低。
-
链表的特点: 寻址困难，插入删除容易。如LinkedList 插入删除容易，但是寻址就必须从表头或者表尾进行循环查找，性能很低。
综合两者对优缺点，变出现了寻址容易、插入删除容易的数据结构：Hash 表。
哈希表的概念
哈希表：（Hash Table 也叫散列表）是根据关键码值(key value)而直接进行访问的数据结构,它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。哈希表实际上就是顺序表和链表对结合。
几个重要对概念：
关键码值(key value) 可以当成key的hash值
映射函数 叫做 散列函数 f(key) = hash值
存放记录的数组 叫做 散列表 实际上就是一个有固定大小对数组。
hash冲突 通过散列函数计算得到对hash值相同，为hash冲突。
装填因子 表中存放对数据元素个数n与hash表地址空间大小m对比值，n/m一般填充因子在0.6～0.9对范围最佳。
根据一下对举例来理解这几个重要对概念：
key = {14,19,5,7,21,1,13,0,18} 需要key来计算hash值。
散列函数f(key) = key mod 13 = hash值; 求key的模
| f(key) | hsah值 |
|---|---|
| f(14) | 1 |
| f(19) | 6 |
| f(7) | 7 |
| f(21) | 8 |
| f(1) | 1 |
| f(13) | 0 |
| f(0) | 0 |
| f(18) | 5 |
散列表 a[13] 大小为13对数组,数组对下标对应这hash值。数组中存入对是key
| a[13] | key |
|---|---|
| 0 | 13 0 |
| 1 | 14 1 |
| 2 | |
| 3 | |
| 4 | |
| 5 | 18 |
| 6 | 19 |
| 7 | 7 |
| 8 | 21 |
| 9 | |
| 10 | |
| 11 | |
| 12 |
可以明显的看出 hash值冲突了，a[0] 只能存一个key,a[1] 也只能存一个key.
如何解决hash冲突呢？
我们可以自己定义一个解决方案比如，如果遇到冲突hash值+1，根据存入对顺序计算，那么得到的结果就是 a[2] = 1 a[3] = 0,f(14) = 1;f(1) = 1 --> 1+1 = 2 而a[2] 中没有存入任何值，a[2] = 1。同理 f(13) = 0 ,f(0) = 0,f(0) = 0 就是hash值冲突了，0+1 = 1 a[1] = 14 ,a[1] 中有值 继续+1 0+1+1 =2 a[2] = 1 ;继续+1 0+1+1+1 = 3 a[3] 没有值，将0存入到a[3]中。
| a[13] | key |
|---|---|
| 0 | 13 |
| 1 | 14 |
| 2 | 1 |
| 3 | 0 |
| 4 | |
| 5 | 18 |
| 6 | 19 |
| 7 | 7 |
| 8 | 21 |
| 9 | |
| 10 | |
| 11 | |
| 12 |
OK 基本概念讲解完了，我们举个实际应用中对例子，每个人手机上都有一个电话薄，是按照人名对首字母进行排序的（人名X 到首字母的F(X)的一个函数关系），必须我们在首字母查找“苏”姓的电话号码，显然比从头开始查找要快的多。以人名作为key,F(key)函数得到首字母，存放首字母的表对应散列表。如果还是对这些概念不理解，对着你的手机通讯录想一想。
哈希表（Hash）的特点
hash表的数据结构<key,value>
优点：查找、插入、删除只需要接近敞亮的时间O（1），实际上就是几条及其指令，在速度和易用性上是非常棒的。
缺点：基于数组，数组创建后都是固定大小的，难于拓展，当hash表被填满后，性能下降很严重，所以要求预先清楚表中存储多少数据。
更新补充：
链表问题补充
