数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的，被清楚指定的简单指令的集合。

数组 - 图1

数组

数组属性

constructor 返回创建数组对象的原型
length 设置或者返回数组元素的个数
prototype 允许向数组对象添加属性和方法

数组方法

concat() 连接两个或多个数组，返回结果 array1.concat(array2, array3, array4, … arrayX);
copyWithin() 从数组的指定位置拷贝元素到数组的另一个指定位置 array.copyWithin(*target, start,end)
entries() 返回数据的迭代对象，包括数组的键值对 array.entries();
every() 检测数值元素的每个元素是否都符合条件 array.every(function(*currentValue, index, arr), thisValue)
fill() 使用一个固定值填充数组 array.fill(*value, start, end)
filter() 检测数值元素，并返回符合条件的所有元素数组 array.filter(function(*currentValue, index, arr), thisValue)
find() 返回符合传入条件的数组元素 array.find(function(*currentValue, index, arr), thisValue)
findIndex() 返回符合传入条件的数组元素的索引 array.findIndex(function(*currentValue, index, arr), thisValue)
forEach() 数组每个元素都执行一次回调函数 array.forEach(function(*currentValue, index, arr), thisValue)
from() 通过给定的对象中创建一个数组 Array.from(*object, mapFunction, thisValue)
includes() 判断一个数组是否包含一个指定的值 array.includes(*searchElement, fromIndex)
indexOf() 搜索数组中的元素，并返回它所在的位置 array.indexOf(*item, start)
isArray() 判断对象是否为数组 Array.isArray(obj)
join() 把数组的所有元素放入一个字符串中 array.join(separator)
keys() 返回数组的可迭代对象，包含原始数组的键(key) array.keys()
lastIndexOf() 搜索数组中的元素，并返回它最后出现的位置 array.lastIndexOf(*item, start)
map() 通过指定函数处理数组的每个元素，并返回处理后的数组 array.map(function(currentValue, index, arr), thisValue)
pop() 删除数组的最后一个元素并返回删除的元素 array.pop()
push() 向数组的末尾添加一个或者多个元素，并返回新长度 array.push(item1, item2, item3, ….., itemX)
reduce() 将数组元素计算为一个值（从左到右） array.reduce(function(total, currentValue, currentIndex, arr), initialValue)
reduceRight() 将数组元素计算为一个值（从右向左） array.reduceRight(function(total, currentValue, currentIndex, arr), initalValue)
reverse() 反转数组的元素顺序 array.reverse()
shift() 删除并返回数组的第一个元素 array.shift()
slice() 选取数组的一部分，并返回一个新数组 array.slice(start, end)
some() 检测数组元素中是否有元素符合指定条件 array.some(function(*currentValue, index, arr), thisValue)
sort() 对数组的元素进行排序 array.sort(sortfunction)
splice() 从数组中添加或者删除元素 array.splice(index, howmany, item1, item2, …, itemX)
toString() 把数组转换为字符串，并返回结果 array.toString()
unshift() 向数组的开头添加一个或者多个元素，并返回新的长度 array.unshift(item1, item2, …, itemX)
valueOf() 返回数组对象的原始值 array.valueOf()

数组 - 图2

链表

链表(Linked List)也是线性结构，它与数组看起来非常像，但是它们的内存分配方式、内部结构和插入删除操作方式都不一样。

链表是一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针。链表头指针指向第一个节点，如果链表为空，则头指针为空或者为 null。

链表可以用来实现文件系统、哈希表和邻接表。

下图展示了一个链表，它有 3 个节点：

数组 - 图3

链表分为 2 种：

  • 单向链表
  • 双向链表

链表的基本操作

  • InsertAtEnd —  在链表结尾插入元素
  • InsertAtHead —  在链表开头插入元素
  • Delete —  删除链表的指定元素
  • DeleteAtHead —  删除链表第一个元素
  • Search —  在链表中查询指定元素
  • isEmpty —  查询链表是否为空
  1. // 定义一个链表
  2. class Node<E> {
  4.     E item;
  5.     Node<E> next;
  7.     //构造函数
  8.     Node(E element) {
  9.        this.item = element;
  10.        this.next = null;
  11.    }
  12. }
  13. ////////////////////////////////////////
  14. //头节点和尾节点都为空 链表为空
  15. Node<E> head = null;
  16. Node<E> tail = null;
  18. ///////////////////////////////////////
  19. //创建一个新的节点 并让head指向此节点
  20. head = new Node("nodedata1");
  22. //让尾节点也指向此节点
  23. tail = head;
  25. ///////////////////////////////////////
  26. //创建新节点 同时和最后一个节点连接起来
  27. tail.next = new Node("node1data2");
  29. //尾节点指向新的节点
  30. tail = tail.next;
  32. //////////////////////////////////////
  33. // 顺序遍历链表
  34. Node<String> current = head;
  35. while (current != null) {
  36.     System.out.println(current.item);
  37.     current = current.next;
  38. }
  40. // 倒序遍历链表
  41. static void printListRev(Node<String> head) {
  42. //倒序遍历链表主要用了递归的思想
  43.     if (head != null) {
  44.         printListRev(head.next);
  45.         System.out.println(head.item);
  46.     }
  47. }

栈

栈和队列也是比较常见的数据结构，它们是比较特殊的线性表，因为对于栈来说，访问、插入和删除元素只能在栈顶进行，对于队列来说，元素只能从队列尾插入，从队列头访问和删除。

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈顶，对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表，即后进先出。

数组 - 图4

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

数组 - 图5

  1. public class MyQueue<E> {
  3.     private LinkedList<E> list = new LinkedList<>();
  5.     // 入队
  6.     public void enqueue(E e) {
  7.         list.addLast(e);
  8.     }
  10.     // 出队
  11.     public E dequeue() {
  12.         return list.removeFirst();
  13.     }
  14. }

数组 - 图6

树与二叉树

树型结构是一类非常重要的非线性数据结构，其中以树和二叉树最为常用。

树 是由n（n>=1）个有限节点组成一个具有层次关系的集合。它具有以下特点：每个节点有零个或多个子节点；没有父节点的节点称为 根 节点；每一个非根节点有且只有一个 父节点 ；除了根节点外，每个子节点可以分为多个不相交的子树。

数组 - 图7

二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

数组 - 图8

  • 二叉树的每个结点至多只有2棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒

  • 二叉树的第i层至多有2(i-1)个结点，深度为K的二叉树最多有2k-1个结点

  • 一棵深度为k，且有2k-1 节点的二叉树称之为 满二叉树

  • 深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为 完全二叉树

树和二叉树的区别

(1) 二叉树每个节点最多有2个子节点，树则无限制。

(2) 二叉树中节点的子树分为左子树和右子树，即使某节点只有一棵子树，也要指明该子树是左子树还是右子树，即二叉树是有序的。

(3) 树决不能为空，它至少有一个节点，而一棵二叉树可以是空的。

图

图是一种较线性表和树更为复杂的数据结构，在线性表中，数据元素之间仅有线性关系，在树形结构中，数据元素之间有着明显的层次关系，而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。图的应用相当广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。