数据结构指相互之间存在一种或多种特定关系的数据元素的集合,包括逻辑结构、存储结构和对数据的运算
数据的逻辑结构是对数据之间关系的描述,它与数据的存储结构无关,同一种逻辑结构可以有多种存储结构,主要有线性结构和非线性结构
线性结构的特点是数据元素之间存在一对一的线性关系
线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表),顺序表中存储的元素是连续的,链表中存储的元素不一定是连续的
常见的线性结构有数组、队列、链表和栈
常见的非线性结构有二维数组、多维数组、广义表、树和图
数组是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素
特点:下标从0开始,内存中顺序存储
数据结构的操作通常有增、删、改、查
由于数组在内存中顺序存储,所以只需给出一个数组下标,就可以读取到对应的数组元素。像这种根据下标读取元素的方式叫作随机读取,下标必须在数组的长度范围内,否则会出现数组越界
int[] array = new int[]{3,4,7,1,8};
System.out.println(array[3]);
直接利用数组下标,就可以把新值赋给该元素
int[] array = new int[]{3,4,7,1,8};
array[3] = 12;
System.out.println(array[3]);
数组读取元素和更新元素时间复杂度为O(1)
数组的实际元素数量有可能小于数组的长度,插入元素时,有三种情况,分别是尾部插入、中间插入和超范围插入
尾部插入,直接把插入的元素放在数组尾部的空闲位置,等同于更新元素操作
中间插入,先把插入位置及后面元素向后移动,再把要插入的元素放到对应的数组位置
超范围插入,创建一个新数组,长度是原来的2倍,再把旧数组中的元素复制过去
删除元素位于数组中间,其后的元素都需要向前挪动1位
插入元素和删除元素时间复杂度都是O(n)
优点:高效的随机访问能力
缺点:插入、删除元素会导致大量元素被迫移动,影响效率
数组适合多读少写的场景
链表(linked list)是一种在物理上非连续、非顺序的数据结构,由多个节点(node)组成。单向链表每个节点包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next
链表的第一个节点称为头节点,最后一个节点称为尾节点,尾节点的next指针指向空
双向链表:每一个节点拥有data和next指针,还拥有指向前置节点的prev指针
链表的每个节点分布在内存的不同位置,依靠next指针关联起来,这样可以灵活有效利用零散的碎片空间
从头节点开始向后一个个节点逐一查找,最差的时间复杂度是O(n)
如果不考虑查找节点的过程,直接把旧数据替换成新数据即可
包括尾部插入、头部插入和中间插入
尾部插入只需把最后一个节点的next指针指向新插入的节点即可
头部插入需要两步
中间插入需要两步
注意:只要内存空间允许,不需要像数组考虑扩容
链表删除包括尾部删除、头部删除和中间删除
尾部删除:把倒数第二个节点的next指针指向空
头部删除:把链表的头节点设为原先头节点的next指针
中间删除:把要删除节点的前置节点的next指针,指向要删除元素的下一个节点
完整代码实现如下:
public class MyLinkedList {
//头节点指针
private Node head;
//尾节点指针
private Node last;
//链表实际长度
private int size;
/**
* 链表插入元素
* @param data 插入元素
* @param index 插入位置
* @throws Exception
*/
public void insert(int data, int index) throws Exception {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围!");
}
Node insertedNode = new Node(data);
if (size == 0) {
head = insertedNode;
last = insertedNode;
} else if (index == 0) {
//插入头部
insertedNode.next = head;
head = insertedNode;
} else if (size == index) {
//插入尾部
last.next = insertedNode;
last = insertedNode;
} else {
//插入中间
Node prevNode = get(index - 1);
insertedNode.next = prevNode.next;
prevNode.next = insertedNode;
}
size++;
}
/**
* 链表删除元素
* @param index 删除的位置
* @return
* @throws Exception
*/
public Node remove(int index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围!");
}
Node removedNode = null;
if (index == 0) {
//删除头节点
removedNode = head;
head = head.next;
} else if (index == size - 1) {
//删除尾节点
Node prevNode = get(index - 1);
removedNode = prevNode.next;
prevNode.next = null;
last = prevNode;
} else {
//删除中间节点
Node prevNode = get(index - 1);
Node nextNode = prevNode.next.next;
removedNode = prevNode.next;
prevNode.next = nextNode;
}
size--;
return removedNode;
}
/**
* 链表查找元素
* @param index 查找位置
* @return
* @throws Exception
*/
private Node get(int index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围!");
}
Node tmp = head;
for (int i = 0; i < index; i++) {
tmp = tmp.next;
}
return tmp;
}
/**
* 输出链表
*/
public void output() {
Node tmp = head;
while (tmp != null) {
System.out.println(tmp.data);
tmp = tmp.next;
}
}
/**
* 链表节点
*/
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) throws Exception {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.insert(3, 0);
myLinkedList.insert(7, 1);
myLinkedList.remove(0);
myLinkedList.output();;
}
}
类型 | 查找 | 更新 | 插入 | 删除 |
---|---|---|---|---|
数组 | O(1) | O(1) | O(n) | O(n) |
链表 | O(n) | O(1) | O(1) | O(1) |
数组适用于多读少写,链表适用于插入和删除
一种线性数据结构,栈中的元素只能先进后出(First In Last Out,FILO),最早进入的元素存放的位置叫栈底,最后进入的元素存放位置叫栈顶,既可以用数组实现,也可以用链表实现
入栈(push)
将新元素添加进栈中,只允许从栈顶一侧放入元素,新元素的位置将会成为新的栈顶
出栈(pop)
将栈中的元素弹出,只有栈顶元素才允许出栈,出栈元素的前一个元素将会成为新栈顶
一种线性数据结构,队列中元素只能先进先出(First In First Out,FIFO),队列的出口端叫队头(front),队列的入口端叫队尾(rear)
入队(enqueue)
将新元素放入队列,只允许在队尾的位置放入元素,新元素的下一个位置将会成为新的队尾
出队(dequeue)
将元素移除队列,只允许在队头移除元素,出队元素的后一个元素将会成为新的队头
散列表又叫哈希表(hash table),提供键(key)和值(value)的映射关系,根据key就可以高效查找所匹配的value,时间复杂度接近于O(1),通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫散列函数,存放记录的数组叫散列表
在Java中每个对象都有属于自己的hashcode,这个hashcode是区分不同对象的重要标识,hashcode转化成数组的下标是按照数组长度进行取模运算index = HashCode(Key)%Array.length
写操作(put)
写操作就是在散列表中插入新的键值对
步骤如下:
由于数组长度有限,当插入的Entry越来越多,不同的key通过哈希函数获得的下标有可能相同,这种情况叫哈希冲突,解决办法有两种,一是开放寻址法,二是链表法
开放寻址法的原理是当一个key通过哈希函数获得对应的数组下标已被占用时,可以寻找下一个空挡位置,如Java中的ThreadLocal就是使用此方法
Java中的HashMap使用了链表法解决哈希冲突,HashMap数组的每个元素既是一个Entry对象,又是一个链表的头节点,每个Entry对象通过next指针指向它的下一个Entry节点,当新来的Entry映射到与之冲突的数组位置时,只需要插入到对应的链表中
读操作(get)
具体步骤如下:
扩容(resize)
当散列表达到一定饱和度时,key映射位置发生冲突的概率会逐渐提高,大量元素在相同的数组下标位置,形成很长的链表,对后续插入操作和查询操作的性能都有很大的影响,此时散列表就需要扩展其长度
HashMap中影响其扩容的因素有两个
扩容的条件是HashMap.size >= Capacity * LoadFacotr
扩容步骤如下:
JDK8开始,当多个Entry被Hash到同一个数组下标位置时,为了提升插入和查找的效率,HashMap会把Entry的链表转化为红黑树
树是n(n>=0)个节点的有限集,当n=0时,称为空树
非空树有如下两个特点:
二叉树(binary tree):每个节点最多有两个孩子节点,可以只有一个,或者没有孩子节点
二叉树节点有两个孩子节点,一个称为左孩子(left child),一个称为右孩子(right child),两个子节点顺序是固定的
二叉树有两种特殊形式,一是满二叉树,二是完全二叉树
满二叉树:所有非叶子节点都存在左右孩子,且所有叶子节点都在同一层级上
完全二叉树:对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树
满二叉树要求所有分支都是满的,完全二叉树只需保证最后一个节点之前的节点都齐全即可
二叉树既可以用链表实现,也可以用数组实现
链表实现二叉树时,每个节点包含三部分,存储数据的data变量、指向左孩子的left指针和指向右孩子的right指针
数组实现二叉树时,按照层级顺序把二叉树的节点放到数组中对应的位置,如果某个节点的左孩子或右孩子空缺,则数组相应位置也空出来。假设父节点下标为n,左孩子下标为2n + 1,右孩子下标为2n + 2,假设左孩子下标是m,其父节点下标是(m - 1)/2,通常情况二叉堆使用数组实现
主要应用包括进行查找操作和维持相对顺序
二叉查找树
对于一个节点分布相对均衡的二叉查找树来说,如果节点总数是n,那么搜索节点的时间复杂度就是O(logn),和树的深度是一样的
二叉查找树要求左子树小于父节点,右子树大于父节点,正是这样保证了二叉树的有序性,二叉查找树又称为二叉排序树(binary sort tree)
从节点之间位置关系划分
前序遍历、中序遍历、后序遍历、层序遍历
从宏观角度划分
深度优先遍历(前序遍历、中序遍历、后序遍历)
广度优先遍历(程序遍历)
输出顺序是根节点、左子树、右子树
输出顺序是左子树、根节点、右子树
输出顺序是左子树、右子树、根节点
public class BinaryTree {
/**
* 构建二叉树
* @param inputList
* @return
*/
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
TreeNode node = null;
if (inputList == null || inputList.isEmpty()) {
return null;
}
Integer data = inputList.removeFirst();
if (data != null) {
node = new TreeNode(data);
node.leftChild = createBinaryTree(inputList);
node.rightChild = createBinaryTree(inputList);
}
return node;
}
/**
* 二叉树前序遍历
* @param node
*/
public static void preOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
preOrderTraveral(node.leftChild);
preOrderTraveral(node.rightChild);
}
/**
* 二叉树中序遍历
* @param node
*/
public static void inOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
inOrderTraveral(node.leftChild);
System.out.println(node.data);
inOrderTraveral(node.rightChild);
}
/**
* 二叉树后序遍历
* @param node
*/
public static void postOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
postOrderTraveral(node.leftChild);
postOrderTraveral(node.rightChild);
System.out.println(node.data);
}
/**
* 二叉树节点
*/
private static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[] {3, 2, 9, null, null, 10, null, null, 8, null, 4}));
TreeNode treeNode = createBinaryTree(inputList);
System.out.println("前序遍历:");
preOrderTraveral(treeNode);
System.out.println("中序遍历");
inOrderTraveral(treeNode);
System.out.println("后序遍历");
postOrderTraveral(treeNode);
}
}
按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点
代码实现如下:
public static void preOrderTraveralWithStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
//迭代访问节点左孩子,并入栈
while (treeNode != null) {
System.out.println(treeNode.data);
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
本质是一种完全二叉树,分为最大堆和最小堆
最大堆:任意父节点的值,都大于或等于其左、右孩子节点的值,堆顶是最大元素
最小堆:任何一个父节点的值,都小于或等于其左、右孩子节点的值,堆顶是最小元素
插入节点
当二叉堆插入节点时,插入位置是完全二叉树的最后一个位置,新节点与其父节点相比较,如果比其大(小),就让新节点上浮,和父节点交换位置,依次比较、上浮,直到找到合适的位置
删除节点
删除的是处于堆顶的节点,将堆的最后一个节点临时补到原本堆顶的位置,暂处堆顶位置的节点与其左、右孩子进行比较,如果左、右孩子节点中最小的一个比父节点小,那么父节点下沉
构建二叉堆
让所有非叶子节点依次下沉,先从最后一个非叶子节点开始,与其左、右孩子节点中最小的一个比较,若比它大就下沉,依次再比较其他非叶子节点
二叉堆插入和删除操作时间复杂度为O(logn),构建操作时间复杂度是O(n)
二叉堆的节点存储在数组中
public class BinaryHeap {
/**
* 上浮
* @param array
*/
public static void upAdjust(int[] array) {
int childIndex = array.length - 1;
int parentIndex = (childIndex - 1) / 2;
int tmp = array[childIndex];
while (childIndex > 0 && tmp < array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
array[childIndex] = tmp;
}
/**
* 下沉
* @param array 待调整的堆
* @param parentIndex 需要下沉的父节点
* @param length 堆有效大小
*/
public static void downAdjust(int[] array, int parentIndex, int length) {
int tmp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
//如果父节点小于任何一个子节点,直接跳出
if (tmp <= array[childIndex]) {
break;
}
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = tmp;
}
/**
* 构建堆
* @param array 待调整的堆
*/
public static void buildHeap(int[] array) {
for (int i = (array.length - 2) / 2; i >= 0 ; i--) {
downAdjust(array, i, array.length);
}
}
public static void main(String[] args) {
int[] array = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
upAdjust(array);
System.out.println(Arrays.toString(array));
array = new int[] {7, 1, 3, 10, 5, 2, 8, 9, 6};
buildHeap(array);
System.out.println(Arrays.toString(array));
}
}
最大优先队列:当前最大元素优先出队
最小优先队列:当前最小元素优先出队
入队操作
插入新节点,新节点上浮找到合适的位置
出队操作
让原堆顶节点出队,把最后一个节点替换到堆顶位置,节点下沉,新的最大值节点成为新堆顶
代码实现如下:
public class PriorityQueue {
private int[] array;
private int size;
private PriorityQueue() {
array = new int[32];
}
/**
* 入队
* @param key 入队元素
*/
public void enQueue(int key) {
//对象长度超过范围,扩容
if (size >= array.length) {
resize();
}
array[size++] = key;
upAdjust();
}
/**
* 出队
* @return
* @throws Exception
*/
public int deQueue() throws Exception {
if (size <= 0) {
throw new Exception("the queue is empty!");
}
//获取堆顶元素
int head = array[0];
//最后一个元素移动到堆顶
array[0] = array[--size];
downAdjust();
return head;
}
/**
* 上浮
*/
private void upAdjust() {
int childIndex = size - 1;
int parentIndex = (childIndex - 1) / 2;
int tmp = array[childIndex];
while (childIndex > 0 && tmp > array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = parentIndex / 2;
}
array[childIndex] = tmp;
}
/**
* 下沉
*/
private void downAdjust() {
int parentIndex = 0;
int tmp = array[parentIndex];
int childIndex = 1;
while (childIndex < size) {
if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
if (tmp >= array[childIndex]) {
break;
}
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = tmp;
}
/**
* 队列扩容
*/
private void resize() {
int newSize = this.size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}
public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);
System.out.println("出队元素为:" + priorityQueue.deQueue());
}
}