学校里我们可能都学过数据结构，面试上数据结构和算法已然是必修课了，看了极客的数据结构，当然要比《算法导论》简单易懂。画个笔记，把数据结构和算法基础知识提炼总结一下。有个概念的认识多是有益的。也推荐大家去学习阅读下极客的数据结构与算法的文稿。
数据结构概念
数据结构就是指一组数据的存储结构。它是组织数据的一种方式。
常见的数据结构
- 数组 (Array)
- 链表 (Linked List)
- 栈 (Stack)
- 队列 (Queue)
- 跳表 (Skip list)
- 散列表 (Hash)
- 树 (Tree)
- 堆 (Heap)
- 图 (Graph)
数组 (Array)
数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，查询效率高，但插入、删除操作也因此变得比较低效。
数组的增删改查类似于现实生活中的插队，一列排好的队伍，突然有一个人进来势必会影响之后的人的队。
//数据机构-最基础
int[] a={2,0,2,1};
链表 (Linked List)
链表并不需要一块连续的内存空间，它通过 “指针” 将一组零散的内存块串联起来使用。
和数组相比，链表更适合插入、删除操作频繁的场景。
//链表结构
public class LinkNode{
//数据
int data;
//下一个节点
LinkNode next;
//上一个节点
LinkNode before;
public LinkNode(){
}
public LinkNode(int data){
this.data=data;
}
}
栈 (Stack)
后进者先出，先进者后出，这就是典型的 “栈” 结构。栈是一种 “操作受限” 的线性表，只允许在一端插入和删除数据。
从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选 “栈” 这种数据结构。
用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
//基于数组的顺序栈结构
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
}
队列 (Queue)
先进者先出，这就是典型的 “队列”。队列跟栈一样，也是一种操作受限的线性表数据结构。
使用广泛：循环队列、阻塞队列、并发队列、Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁。
用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
//基于数组的顺序队列结构
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
}
跳表 (Skip list)
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低。
链表加多级索引的结构，就是跳表。跳表可以减少查询次数的，提高查询效率。
建立跳表数据结构后，查找某个结点，先通过遍历索引层一级级缩小目标访问，再对原始链表进行遍历，遍历的节点减少了，效率自然提升了。
结构定义与链表结构一致。
因为跳表本就是从链表中抽取出来的节点数据组成了索引链表。
下次再总结散列表 (Hash)、树 (Tree)、堆 (Heap)、
图 (Graph) 的基础知识
扫一扫，关注我
