本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解线性表，代码均为自己实现。

线性表

线性表表示0个或者多个数据元素的有限序列。

线性表的特性有:

除第一个元素外,每一个元素均有一个直接前驱，除最后一个元素外,每一个元素均有一个直接后继。

线性表抽象数据类型

IList接口如下：

1
2
3
4
5
6
7
8
9

public interface IList<E> {
	boolean isEmpty();
	void clear();
	E get(int i);
	boolean contains(Object o);
	E insert(int i , E e);
	E remove(int i);
	int size();
}

程序 = 数据结构 + 算法

基本概念和术语

​ 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。不仅包括整型、实型等数值类型，还包括字符以及声音、图像、视频等非数值类型。
​ 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
​ 数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。虽然数据项是数据的最小单位，但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。
​ 数据对象：是性质相同的数据元素的集合，是数据的子集。在不产生混淆的的情况下，我们都将数据对象简称为数据。

内存模型的基本概念

​ 计算机在执行程序时，每条指令都是在CPU中执行的，而执行指令过程中，势必涉及到数据的读取和写入。由于程序运行过程中的临时数据是存放在主存（物理内存）当中的，这时就存在一个问题，由于CPU执行速度很快，而从内存读取数据和向内存写入数据的过程跟CPU执行指令的速度比起来要慢的多，因此如果任何时候对数据的操作都要通过和内存的交互来进行，会大大降低指令执行的速度。因此在CPU里面就有了高速缓存。

​ 也就是说，当程序在运行过程中，会将运算需要的数据从主存复制一份到CPU的高速缓存当中，那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据，当运算结束之后，再将高速缓存中的数据刷新到主存当中。

锁的相关概念介绍

可重入锁

如果锁具备可重入性，则称作为可重入锁。像synchronized和ReentrantLock都是可重入锁，可重入性表明了锁的分配机制：基于线程的分配，而不是基于方法调用的分配。举个简单的例子，当一个线程执行到某个synchronized方法时，比如说method1，而在method1中会调用另外一个synchronized方法method2，此时线程不必重新去申请锁，而是可以直接执行方法method2。

可中断锁

synchronized就不是可中断锁，而Lock是可中断锁。如果某一线程A正在执行锁中的代码，另一线程B正在等待获取该锁，可能由于等待时间过长，线程B不想等待了，想先处理其他事情，我们可以让它中断自己或者在别的线程中中断它，这种就是可中断锁。下面的lockInterruptibly()的用法时已经体现了Lock的可中断性。

公平锁

公平锁即尽量以请求锁的顺序来获取锁。比如同是有多个线程在等待一个锁，当这个锁被释放时，等待时间最久的线程（最先请求的线程）会获得该所，这种就是公平锁。

非公平锁即无法保证锁的获取是按照请求锁的顺序进行的。这样就可能导致某个或者一些线程永远获取不到锁。

synchronized就是非公平锁，它无法保证等待的线程获取锁的顺序。而对于ReentrantLock和ReentrantReadWriteLock，它默认情况下是非公平锁，但是可以设置为公平锁。

共享锁和排它锁

共享锁就是允许多个线程同时获取一个锁，一个锁可以同时被多个线程拥有。排它锁，也称作独占锁，一个锁在某一时刻只能被一个线程占有，其它线程必须等待锁被释放之后才可能获取到锁。

ReentrantLock就是一种排它锁。CountDownLatch是一种共享锁。这两类都是单纯的一类，即，要么是排它锁，要么是共享锁。
ReentrantReadWriteLock是同时包含排它锁和共享锁特性的一种锁，这里主要以ReentrantReadWriteLock为例来进行分析学习。我们使用ReentrantReadWriteLock的写锁时，使用的便是排它锁的特性；使用ReentrantReadWriteLock的读锁时，使用的便是共享锁的特性。

volatile的原理

在学习volatile关键字用法之前，首先了解java的内存模型。

volatile的定义与实现

​ volatile 变量可以被看作是一种 “程度较轻的 synchronized”；与 synchronized 块相比，volatile 变量所需的编码较少，并且运行时开销也较少，但是它所能实现的功能也仅是 synchronized 的一部分。在某些情况下，如果读操作远远大于写操作，volatile 变量还可以提供优于锁的性能优势。

​ 一旦一个共享变量（类的成员变量、类的静态成员变量）被volatile修饰之后，那么就具备了两层语义：保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。禁止进行指令重排序。但是不能保证原子性！

Runnable

Runnable是个接口，在它里面只声明了一个run()方法：

1
2
3

public interface Runnable {
	public abstract void run();
}

使用很简单：

1.实现该接口并重写run方法 2.利用该类的对象创建线程 3.线程启动时就会自动调用该对象的run方法

相对于继承Thread来创建线程方式，使用Runnable可以让你的实现类同时实现多个接口，而相对于Callable及Future，Runnable方法并不返回任务执行结果且不能抛出异常。

通常在开发中结合ExecutorService使用,将任务的提交与任务的执行解耦开,同时也能更好地利用Executor提供的各种特性。

进程和线程的概念

​ 先了解一下操作系统的一些相关概念，大部分操作系统(如Windows、Linux)的任务调度是采用时间片轮转的抢占式调度方式，也就是说一个任务执行一小段时间后强制暂停去执行下一个任务，每个任务轮流执行。任务执行的一小段时间叫做时间片，任务正在执行时的状态叫运行状态，任务执行一段时间后强制暂停去执行下一个任务，被暂停的任务就处于就绪状态等待下一个属于它的时间片的到来。这样每个任务都能得到执行，由于CPU的执行效率非常高，时间片非常短，在各个任务之间快速地切换，给人的感觉就是多个任务在“同时进行”，这也就是我们所说的并发(并发简单来说多个任务同时执行)。