一、概述
数据结构是研究数据如何在计算机中进行高效的组织和存储的一门学科。数据结构有逻辑结构和存储结构之分，逻辑结构描述的是数据与数据之间的关系，主要分为以下几种：
- 线性结构：数据与数据之间是一对一的关系。主要有数组、栈、队列、链表、哈希表等。
- 树形结构：数据与数据之间是一对多的关系。主要有二叉树、二分搜索树、AVL、红黑树、堆、线段树、Treap、Trie、哈夫曼树等。
- 图形结构：数据与数据之间是多对多的关系。主要有邻接矩阵和邻接表。
存储结构就是数据在计算机中是怎样进行存储的，主要分为：
- 顺序存储：用一组连续的空间来进行存储，底层用数组实现。
- 链式存储：存储空间可以是不连续的，底层用链表实现。
二、数组
1. 什么是数组？
关于数组的概念就不多说了，大家应该都知道。数组因为有索引，所以数组的优点就是查询快。这里强调两点，一是数组只能存储同一类型的数据，可以是基本类型也可以是引用类型，二是数组长度是不可变的。
2. 封装数组：
java给我们提供的数组可以进行的操作有限，我们可以将数组再次封装一下，让其可以进行增删改查等操作。
public class Array<E>{ private E[] data;//存储数据的数组 private int size;//数组中元素的个数 /** 构造函数，capacity表示数组的容量，即length */ public Array(int capacity){ data = (E[]) new Object[capacity]; size = 0; } /** 默认构造函数 */ public Array(){ this(10); } /** 获取数组中元素的个数 */ public int getSize(){ return size; } /** 获取数组的容量，即length */ public int getCapacity(){ return data.length; } /** 判断数组是否为空 */ public boolean isEmpty(){ return size == 0; } /** 往数组末尾添加元素 */ public void addLast(E e){ add(size,e); } /** 往数组第一个位置添加元素 */ public void addFirst(E e){ add(0,e); } /** 往数组index索引处添加元素 */ public void add(int index,E e){ if (size == data.length) throw new IllegalArgumentException("数组已满"); if (index < 0 || index > size) throw new IllegalArgumentException("插入位置不合法"); for (int i = size - 1;i >= index; i --){ data[i+1] = data[i];//目标位置之后(包括目标位置)的元素后移 } data[index] = e; size ++; } /** 获取index索引处的元素 */ public E get(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("查询位置不合法"); return data[index]; } /** 获取最后一个元素 */ public E getLast(){ return get(size - 1); } /** 获取第一个元素 */ public E getFirst(){ return get(0); } /** 修改index索引处的元素 */ public void update(int index,E e){ if (index < 0 || index >= size) throw new IllegalArgumentException("查询位置不合法"); data[index] = e; } /** 查找数组中是否包含元素e */ public boolean contains(E e){ for (int i = 0; i < size; i++){ if (data[i] .equals(e)) return true; } return false; } /** 查找元素e所在的索引 */ public int find(E e){ for (int i = 0; i < size; i++){ if (data[i].equals(e)) return i; } return -1; } /** 删除index索引处的元素 */ public E remove(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("位置不合法"); E temp = data[index]; for (int i = index + 1;i< size; i++){ data[i-1] = data[i];//目标位置之后的元素前移 } size --; data[size] = null;//这句话可有可无 return temp; } /** 删除数组中的第一个元素 */ public E removeFirst(){ return remove(0); } /** 删除数组中的最后一个元素 */ public E removeLast(){ return remove(size-1); } /** 删除指定元素e */ public void removeElement(E e){ int index = find(e); if (index != -1){ remove(index); } } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("size = %d,capacity = %d\n",size,data.length)); res.append("["); for (int i = 0;i < size; i++){ res.append(data[i]); if (i != size -1){ res.append(", "); } } res.append("]"); return res.toString(); } }
上面就将静态数组再次封装了一下，可以对数组元素进行增删改查等操作。但是呢这还是静态数组，也就是说，我们new Array的时候传入的capacity是多少，那么这个数组长度就是多少，不能再改变了。接下来看看动态数组如何实现。
3. 动态数组：
要动态的改变数组的长度，其实是不能直接实现的。但是我们可以创建一个新数组，将旧数组的的元素全都放入新数组，然后让旧数组的引用指向新数组即可。看代码实现：
/** 给数组扩容 */ private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity];//新数组 for (int i = 0; i< size;i++){ newData[i] = data[i];//旧数组的值存入新数组对应的位置 } data = newData;//指向新数组 }
有了这个方法，就可以对刚才上面的add和remove方法做一些修改。
/** 往数组index索引处添加元素 */ public void add(int index,E e){ if (index < 0 || index > size) throw new IllegalArgumentException("插入位置不合法"); if (size == data.length)//数组已满 resize(2 * data.length);//扩容两倍,如果以前为10，现在就是20 for (int i = size - 1;i >= index; i --){ data[i+1] = data[i]; } data[index] = e; size ++; } /** 删除index索引处的元素 */ public E remove(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("位置不合法"); E temp = data[index]; for (int i = index + 1;i< size; i++){ data[i-1] = data[i]; } size --; if (size == data.length/4 && data.length / 2 != 0){//如果删除元素后数组只使用了1/4的容量 resize(data.length/2);//那就缩小到以前容量的一半 } return temp; }
小结：数组是线性结构的，一经定义长度就不可变。删除数组中元素的思路就是将目标元素之后的元素都前移一位；添加元素的思路就是将目标位置开始的元素都后移一位，再把目标元素添加到目标位置；给数组动态地扩容的思路就是创建一个容量更大的新数组，把旧数组的元素放到新数组对应的位置，最后把旧数组的引用指向新数组。
三、链表
1. 什么是链表？
链表也是一种线性结构。上面说的动态数组、栈和队列，底层都是用静态数组实现的，而链表是一种简单的真正的动态数据结构。它也可以辅助实现其他的数据结构，也就说，像栈和队列，也可以链表来实现。链表是用节点来存储数据的，节点中有数据域和指针域，数据域存放数据，指针域连接下一个节点。这就像火车一样，火车车厢用来搭载乘客，同时每一节车厢又连接着下一节车厢。静态数组定义时就需要声明长度，使用的是计算机中连续的内存空间，可以通过索引访问元素，因此查询元素是非常快的。而链表所使用的空间是不连续的，长度也是不固定的，无法通过索引访问元素，所以查询慢，而增删很快，因为增删时只需要改变一个节点的指针域即可。
2. 链表的实现：
上面说到了链表是用节点来存放数据的，同时节点又连接着下一个节点。所以先要有一个节点类Node，Node应该要有两个属性，一个是用来存放数据的，应该定义为泛型，另一个属性就是Node类型的next，表示的是下一个节点。链表类就应该int类型的size属性，用来记录链表中元素的个数，Node类型head属性，表示链表的头节点。现在来分析一下链表是如何添加和删除元素的。
- 添加元素：
有如下链表：
- 现要在链表最前面添加一个节点node，那么应该执行的操作就是：
node.next = head; head = node;
添加完成后就成了这样：
如果是要在链表中间的某个位置添加元素，比如在元素 “1” 的后面添加节点 “666” ,那么首先我们要找到要插入位置之前的那个节点prev，这里prev就是 “1” 这个节点。接下来执行的操作就是：
node.next = prev.next; prev.next = node;
在指定位置添加元素我们需要找到目标位置的前一个节点，但是如果目标位置是第一个位置的时候，就没有前一个节点了。其实我们可以搞一个虚拟头节点。如下图。
- 删除元素：
删除节点同样也要先找到需要删除的元素的前一个节点prev，需要删除的节点假设叫做delNode。那么删除delNode要执行的操作就是：
prev.next = delNode.next; delNode.next = null;
有了上面的分析，就用代码来实现链表这种数据结构。
- 代码实现：
public class MyLinkedList<E> { /** 节点设计成内部类 */ private class Node { public E e;//存放的元素 public Node next;//下一个节点 public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node dummyhead;//虚拟头节点 private int size;//存储的元素个数 public MyLinkedList() { dummyhead = new Node(null, null); size = 0; } /** 获取链表中元素个数 */ public int getSize() { return size; } /** 判断链表是否为空 */ public boolean isEmpty() { return size == 0; } /** 在链表指定位置添加元素，(index是从0开始的) */ public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("位置不合法"); } Node prev = dummyhead; for (int i = 0; i < index; i++) { prev = prev.next;//找到目标位置的前一个节点 } /*Node node = new Node(e); node.next = prev.next; prev.next = node;*/ prev.next = new Node(e, prev.next);//与上面3行代码等效 size++; } /** 在链表末尾添加元素 */ public void addLast(E e) { add(size, e); } /** 往链表头添加元素 */ public void addFirst(E e) { add(0,e); } /** 获取链表指定位置的元素(index从0开始) */ public E get(int index){ if (index<0 || index>=size){ throw new IllegalArgumentException("位置不合法"); } Node cur = dummyhead.next; for (int i=0;i<index;i++){ cur = cur.next; } return cur.e; } /** 获取第一个元素 */ public E getFirst(){ return get(0); } /** 获取链表最后一个元素 */ public E getLast(){ return get(size -1); } /** 更新指定位置的元素 */ public void set(int index,E e){ if (index<0 || index>=size){ throw new IllegalArgumentException("位置不合法"); } Node cur = dummyhead.next; for (int i=0;i<index;i++){ cur = cur.next; } cur.e = e; } /** 查找链表中是否存在元素e */ public boolean contains(E e){ Node cur = dummyhead.next; while (cur != null){ if (cur.e.equals(e)) return true; cur = cur.next; } return false; } /** 删除指定位置的元素 */ public E remove(int index){ if (index<0 || index>=size){ throw new IllegalArgumentException("位置不合法"); } Node prev = dummyhead; for (int i = 0;i<index;i++){ prev = prev.next;//找到目标节点的前一个节点 } Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size --; return delNode.e; } /** 删除链表中第一个元素 */ public E removeFirst(){ return remove(0); } /** 删除链表中最后一个元素 */ public E removeLast(){ return remove(size -1); } @Override public String toString(){ StringBuilder res = new StringBuilder(); Node cur = dummyhead.next; while (cur != null){ res.append(cur + "-->"); cur = cur.next; } res.append("NULL"); return res.toString(); } }
小结：链表也是线性结构的，是一种不同于数组的动态数据结构，链表的英文翻译的linkedList，注意和java提供的LinkedList集合区分开，LinkedList集合底层正是用链表实现的。
