数据结构和算法-基础篇（一）

1.1 线性表概念

​ 所谓线性表就是将数据排成像一条长线一样的结构，数组、链表、队列、栈都是线性表结构，线性表上的数据最多只有前后两个方向。与这样线性结构相对应的就是非线性结构，比如数组、堆、图等，数据之间并不是简单的前后关系。

1.2 数组（查询快增删慢）

数组的概念： 数组是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。

数组元素的访问：

长度为10的数组来举例

int[] a = new int[10]; //计算机给数组分配了一块连续的空间100-139，其中内存的起始地址为baseAddress=100 a[i] = baseAddress + i * dataTypeSize; //在内存种访问数组a的第i个元素 //数组的角标从0开始是为了减少cpu的一次减法运算 a[i] = baseAddress + (i-1) * dataTypeSize;

数组的特点：

1、高效的随机访问：数组元素是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素。

2、低效的插入和删除：为了保证数组的连续性，在数组中插入和删除的时候需要挪动很多元素导致效率低下。

（在某些特定的场景下，不一定非得追求数组的连续性，将多次删除操作集中在一起执行，从而减少了每次删除操作带来的低效率运行成本，但是随之而来的是在最后一次的删除操作种的长时间的停顿。正如JVM里面的标记-清除垃圾算法！）

4.数组的应用：

​ ArrayList支持动态扩容，每次存储空间不够的时候，它将会把空间自动扩容为1.5倍大小。因为扩容操作设计内存的申请和数据的搬移，是比较耗时的。所以能事先确定需要存储的数据的大小，最好在创建ArrayList的时候先指定数据的大小。

1.3 ArrayList源码分析

ArrayList底层是采用数组来进行数据存储。

1.3.1容器的构建和添加元素

public static void main(String[] args) { //初始化集合 List<String> list = new ArrayList<String>(); //向集合中添加元素 list.add("itcast"); }

数组创建源码分析：

创建ArrayList时采用默认的构造函数创建集合然后往里面添加元素，第一次添加时将数组扩容到10的大小，之后添加元素都不会在扩容，直到第11次添加然后扩容1.5倍取整，扩容的上限值时Integer.MAX_VALUE。

每次扩容时都会创建一个新的数组，然后将原数组中的数据搬移到新的数组中

所以回到开始我们所说的： 如果事先能确定需要存储的数据大小，最好在创建

ArrayList 的时候事先指定数据大小 （这样能够省掉很多次的内存的申请次数和数据搬移的操作）

//ArrayList的带参构造函数 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); } }

1.3.2获取元素

public static void main(String[] args) { //初始化集合 List<String> list = new ArrayList<String>(1); //向集合中添加元素 list.add("itcast"); //获取刚刚存入的元素 String ele = list.get(0); }

查看集合的get方法：

1.3.3ArrayList的优缺点

Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，

而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希

望使用基本类型，就可以选用数组。

如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的

大部分方法，也可以直接使用数组。

对于业务的开发，直接使用容器就可以了。耗费一点点性能不会影响到系统的整体性能。

但是如果是做一些底层的开发，系统的优化要做到极致，这时候数组就会优先于容器成为首选。

1.4链表的概念（查询慢增删快）

​ 链表（Linked list）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

1.4.1链表的类型

单链表：

​ 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next ，如果链表中的某个节点为 p，p 的下一个节点为 q，我们可以表示为：p->next=q

循环链表：

​ 循环链表是一种特殊的单链表**。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的 结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表，和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表，

双向链表：

​ 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的 结点，还有一个前驱指针 prev 指向前面的结点。

​ 双向链表需要额外的两个空间来存储后继结点和前驱结点的地 址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性

双向循环链表：

​ 了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个双向循环链表

1.4.2链表和数组的区别

​ 链表是增删快，查询慢！数组是查询快，增删慢！

1.4.3LinkedList源码分析（底层实现是双向链表）

//一段简单的代码跟踪源码分析 public static void main(String[] args) { //构建容器 List<String> list = new LinkedList<String>(); //向容器中添加数据 list.add("itheima"); list.add("itcast"); }

1.4.3.1容器构建及添加元素

(双向链表的添加是尾插法)

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first;//存储整个链表的头节点 transient Node<E> last;//存储整个链表的尾节点 //LinkedList 构造函数 public LinkedList() { } //静态内部类 Node，也就是我们链表中的概念：节点 private static class Node<E> { E item;// 节点中存储的数据 Node<E> next;//节点中存储的后继指针 next Node<E> prev;//节点中存储的前驱指针 prev //节点的构造函数 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } //添加数据 public boolean add(E e) { linkLast(e); return true; } 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++; } }

1.4.3.2获取元素

//一段简单的代码跟踪源码分析 public static void main(String[] args) { //构建容器 List<String> list = new LinkedList<String>(); //向容器中添加数据 list.add("itheima"); list.add("itcast"); //获取元素 String s = list.get(1); System.out.println(s); }

LinkedList的get方法的源码分析：

public E get(int index) { //判断索引是否越界 checkElementIndex(index); return node(index).item; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { //如果索引不在[0，size),范围内就抛出索引越界异常，其中 size 是集合的长度 return index >= 0 && index < size; } //根据索引从链表中获取节点 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; } }

1.4.4 面试题

1、LinkedList和ArrayList的比较

ArrayList的实现基于数组，LinkedList的实现基于双向链表对于随机访问，ArrayList可以根据下标对元素进行随机访问，但是LinkedList的实现是基于双向链表，对于随机元素的访问必须是从链表的头开始查询直到找到为止，所以查询慢！对于插入和删除操作，LinkedList优于ArrayList，当元素添加到LinkedList的任意位置的时候不用像ArrayList重新计算大小或者是更新索引LinkedList比ArrayList更占用内存，因为LinkedList的节点除了存储数据之外，还存储了两个引用，一个指向前元素，一个指向后元素。

2.反转单链表

//leetcode 编码参考答案： /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; //前指针节点 ListNode curr = head; //当前指针节点 //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移 while (curr != null) { //使用的是头插法 ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移 curr.next = prev; //将当前节点指向它前面的节点 prev = curr; //前指针后移 curr = nextTemp; //当前指针后移 } return prev; } } //c语言实现的反转单链表（头插法） struct ListNode *reverseList(struct ListNode* head) { struct ListNode *newHead = NULL; struct ListNode *node; while (head != NULL) { //1. 对之前的链表做头删 node = head; head = head->next; //2. 对新链表做头插 node->next = newHead; newHead = node; } return newHead; }

1.5 栈

栈是先进后出，后进先出。队列是先进先出，后进后出。

栈的概念：

​ 栈就是一种操作受限的线 性表，只允许在栈的一端进行数据的插入和删除，这两种操作分别叫做入栈和出 栈。当某个数据集合如果只涉及到在其一端进行数据的插入和删除操作，并且满 足先进后出，后进先出的特性时，我们应该首选栈这种数据结构来进行数据的存 储

1.5.1 栈的实现

​ 用数组实现的栈叫顺序栈，用链表实现的栈是链式栈。

1.5.2 基于数组的顺序栈的实现

//不支持动态扩容的顺序栈！！！ public class ArrayStack { // 栈大小 private int size; // 默认栈容量 private int DEFAULT_CAPACITY=10; // 栈数据 private Object[] elements; private int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8; /** * 默认构造创建大小为 10 的栈 */ public ArrayStack(){ elements = new Object[DEFAULT_CAPACITY]; } /** * 通过指定大小创建栈 * @param capacity */ public ArrayStack(int capacity){ elements = new Object[capacity]; } /** * 入栈 * @param element * @return */ public boolean push(Object element){ try { checkCapacity(size+1); elements[size++]=element; return true; }catch (RuntimeException e){ return false;} } /** * 检查栈容量是否还够 */ private void checkCapacity(int minCapacity) { if(elements.length - minCapacity < 0 ){ throw new RuntimeException("栈容量不够!"); } } /** * 出栈 * @return */ public Object pop(){ if(size<=0){ return null;//栈为空则直接返回 null } Object obj = elements[size-1]; elements[--size] = null; return obj; } /** * 获取栈的大小 * @return */ public int size(){ return size; } } //编写好用数组实现的栈之后，我们来编写一个测试类如下： public class ArrayStackTest { public static void main(String[] args) { ArrayStack stack = new ArrayStack(); for (int i=0; i<13; i++) { boolean push = stack.push(i); System.out.println("第"+(i+1)+"次存储数据为:"+i+",存储结果是: "+push); } // stack.push(1); for (int i=0; i<11; i++) { Object pop = stack.pop(); System.out.println(pop); } } }

1.5.3 支持动态扩容的顺序栈

public class ArrayStack { // 栈大小 private int size; // 默认栈容量 private int DEFAULT_CAPACITY=10; // 栈数据 private Object[] elements; private int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8; /** * 默认构造创建大小为 10 的栈 */ public ArrayStack(){ elements = new Object[DEFAULT_CAPACITY]; } /** * 通过指定大小创建栈 * @param capacity */ public ArrayStack(int capacity){ elements = new Object[capacity]; } /** * 入栈 * @param element * @return */ public boolean push(Object element){ try { checkCapacity(size+1); elements[size++]=element; return true; }catch (RuntimeException e){ return false; } } /** * 检查栈容量是否还够 */ private void checkCapacity(int minCapacity) { if(elements.length - minCapacity < 0 ){ //throw new RuntimeException("栈容量不够!"); grow(elements.length); } } /** * 扩容，扩容到原始容量的1.5倍 * @param oldCapacity 原始容量 */ private void grow(int oldCapacity) { int newCapacity = oldCapacity+(oldCapacity>>1); if(newCapacity-oldCapacity<0){ newCapacity = DEFAULT_CAPACITY; } if(newCapacity-MAX_ARRAY_SIZE>0){ newCapacity = hugeCapacity(newCapacity); } elements = Arrays.copyOf(elements,newCapacity); } private int hugeCapacity(int newCapacity) { return (newCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:newCapacity; } /** * 出栈 * @return */ public Object pop(){ if(size<=0){ return null;//栈为空则直接返回 null } Object obj = elements[size-1]; elements[--size] = null; return obj; } /** * 获取栈的大小 * @return */ public int size(){ return size; } } //添加测试代码如下： public class ArrayStackTest { public static void main(String[] args) { ArrayStack stack = new ArrayStack(5); for (int i=0; i<40; i++) { boolean push = stack.push(i); System.out.println("第"+(i+1)+"次存储数据为:"+i+",存储结果是: "+push); } // stack.push(1); for (int i=0; i<11; i++) { Object pop = stack.pop(); System.out.println(pop); } } }

1.5.4 基于链表的链式栈实现

public class Node { //前驱节点 public Node prev; //节点数据 private Object data; //后继节点 public Node next; public Node(Node prev,Object data,Node next){ this.prev = prev; this.data =data; this.next = next; } public Object getData() { return data; } } //接下来实现一个链式栈，提供出栈和入栈的操作： /** * 基于双向链表的链式栈实现 */ public class LinkedListStack { // 栈大小 private int size; //存储链表尾节点 private Node tail; public LinkedListStack(){ this.tail = null; } /** * 入栈---尾插法实现的入栈操作！ * @param data * @return */ public boolean push(Object data){ Node newNode = new Node(tail,data,null); if(size>0){ tail.next = newNode; } tail = newNode; size++; return true; } /** * 出栈 * @return */ public Object pop(){ if((size-1) < 0){ //栈为空 return null; } Object data = tail.getData(); tail = tail.prev; if(tail!=null){ tail.next = null; } size--; return data; } } 从以上的实现我们可以看出，我们采用的是双向链表来实现的链式栈，入栈和出栈 操作虽然都很快速，但是由于双向链表需要额外的存储空间来存储前驱指针，因此 我们这段程序在空间资源的节省上显得力度不够，所以我们想能不能不用双向链表 只用单向链表来解决这个问题呢？答案是肯定的，接下来我们就针对刚刚的代码做 出改造 首先改造我们的节点对象，每个节点对象中只存储数据和 next 指针，并且上面的 实现我们是单独创建的节点对象，那现在我们将节点对象声明为栈的内部类 /** * 基于单链表实现的栈 */ public class StackBasedOnLinkedList { // 存储链表头节点 private Node head; public StackBasedOnLinkedList(){ this.head = null; } /** * 入栈---头插法入栈！ * @param data * @return */ public boolean push(Object data){ Node newNode = new Node(data,head); head = newNode; return true; } /** * 出栈 * @return */ public Object pop(){ if(head==null){ return null; } Node topNode = head; head = topNode.next; topNode.next=null; return topNode.data; } /** * 节点对象 */ private static class Node { //节点数据 private Object data; // next 指针 private Node next; public Node(Object data,Node next){ this.data = data; this.next = next; } public Object getData() { return data; } } } //然后我们编写测试类如下： public class TestStackBasedOnLinkedList { public static void main(String[] args) { StackBasedOnLinkedList stack = new StackBasedOnLinkedList(); for(int i=0;i<6;i++){ stack.push(i+""); System.out.println("第"+(i+1)+"次入栈,入栈的值为:"+i); } for(int i=0;i<8;i++){ Object pop = stack.pop(); System.out.println("取出的结果:"+pop); } } }

1.5.5栈的应用-Stack源码分析

一小段测试代码：

public class JdkStack { public static void main(String[] args) { List list; //创建栈对象 Stack stack = new Stack(); //数据入栈 stack.push("itcast"); stack.push("itheima"); //数据出栈 Object item = stack.pop(); System.out.println(item); } }

1、栈的创建和元素入栈

//栈的构造函数 public class Stack<E> extends Vector<E> { /** * Creates an empty Stack. */ public Stack() { } } //元素入栈 public E push(E item) { addElement(item);//调用父类的 addElement 方法 return item; } //元素出栈 public synchronized E pop() { E obj; int len = size();//调用父类 Vector 的方法 obj = peek(); removeElementAt(len - 1);//调用的是父类的方法 return obj; } public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1);//调用的是父类的方法 } //查看Stack父类Vectory，相关的属性和方法 public class Vector<E> extends AbstractList<E> implements List<E>, Rand omAccess, Cloneable, java.io.Serializable { protected Object[] elementData; protected int elementCount; protected int capacityIncrement; //添加元素到数组 public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1);//确保容量 elementData[elementCount++] = obj; } private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0)//数组长度不够 grow(minCapacity);//扩容----按照原始容量的2倍来扩容的。 } /*在JVM中获取数组的长度是用arraylength这个专门的字节码指令的；在数组的对象头里有一个_length字段，记录数组长度，只需要去读_length字段就可以了*/ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); 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; } }

后续还会持续更新数据结构和算法的相关内容。