所谓数据结构，就是数据组合在一起并进行管理的方式，这些方式有表、栈和队列、树、图等。数据结构除了储存数据还管理着数据。
算法呢，就是以某种方式得出所需要的一个数据或一组数据。实现方式可能是计算，或者遍历等。
*以上仅为个人理解，有误请指出。
一、线性表
概念：线性表是最基本、最简单、也是最常用的一种数据结构。其中数据元素的排列方式是线性的。
分类：按照元素储存结构可分为顺序表和链式表。
1.1 顺序表
元素的存储空间是连续的。比如数组。
2.2 链表：
元素的存储空间是离散的、单独的，元素之间的逻辑顺序是通过链表中的指针链接次序实现。链表也分为很多种，有单链表、双链表、循环链表，本文暂时分析单链表。
单链表中的数据是以结点来表示，每个结点的构成：元素（数据）+指针（指示后继元素的存储位置），下面来实现单链表。
2.2.1 单链表的创建和遍历
public class LinkList {
// 2.头结点和当前结点
public Node<String> head;
public Node<String> current;
/**
* 3.添加新结点
* @param data 要添加的结点的数据
*/
public void add(String data){
if(head == null){// 头结点为null，说明链表中没有元素
// 创建结点并把新结点赋值给当前结点
head = new Node<String>(data);
current = head;
} else {
// 创建新节点赋值给当前结点的下一个结点，让表连起来
current.next = new Node<String>(data);
// 当指针向后移动一位，保证当前结点指向最新的结点
// 这样再有新数据就一直向后链接
current = current.next;
}
}
/**
* 4.打印单链表中所有结点数据
* @param node 从该结点开始打印
*/
public void printLinkList(Node node){
if(node == null){
return;
}
current = node;
while (current != null){
System.out.print(current.data);
current = current.next;
}
}
// 1.包含两部分 data（数据），next（下一个结点指针）
class Node<E>{
E data;
Node<E> next;
public Node(E data) {
this.data = data;
}
}
}
- 创建结点。LinkList 表示单链表类，内部类 Node 表示单链表的元素。提供构造函数以便创建结点。
- 在单链表中创建变量头结点和当前结点，头结点主要用于记录首个结点信息，当前结点用于继续创建后续结点。
- 创建结点的函数：
如果单链表中没有结点，则创建结点传入数据并赋值给头结点。这里头结点作为链表是否为空的重要属性，以及作为遍历单链表所有结点的起始结点。
如果不为空链表，则创建新结点并赋值给当前的结点的下一个结点，作为连接用。然后将指针向后移动一位指向最新的结点，这样当再添加结点会赋值给最新的结点的 next 保证链接。 - 单链表的遍历：遍历的话需要传递某个结点作为参数，并赋值给当前结点，如果链表存在该结点则循环打印结点数据即可。如果想要遍历所有结点数据，就用到变量头结点 head 了，因为它是作为链表的第一个结点存在的，传入 head 就可以遍历所有的结点了。
测试：
public class Test {
public static void main(String[] args){
LinkList linkList = new LinkList();
// 创建 LinkList 并添加数据
// 这时链表为空，第一个元素会作为 head 保存。
for (int i = 0; i < 10; i++){
linkList.add("data"+i+"\n");
}
// 这时 head 已经有数据了，执行循环遍历即可
linkList.printLinkList(linkList.head);
}
}
结果：
遍历单链表
有关单链表的问题还有很多，参考：
相关问题简单实现：
- 获取单链表长度：遍历之...
/**
* @return 获取链表长度
*/
public int getLinkListLength(){
if(head == null){
return 0;
}
int length = 0;
Node node = head;
while (node != null){
length++;
node = node.next;
}
return length;
}
- 反转一个单链表
/**
* 反转链表，循环不会栈溢出
* @param node
* @return
*/
public Node reverseList(Node node){
if(node == null || node.next == null){
return node;
}
Node current = node;
Node next = null;
Node reverseHead = null;
while (current != null){
// 1.记录当前结点的下一个结点用于指针后移
next = current.next;
// 4.下一轮循环时，旧的表的下一结点链接到新表头
current.next = reverseHead;
// 2.将当前结点赋值给新表头
reverseHead = current;
// 3.指针后移
current = next;
}
return reverseHead;
}
这里的思路首先是循环，然后分别记录当前结点、下一个结点和反转后新链表的表头，接着就是循环的赋值：
- 记录当前结点的下一个结点，用于赋值给 current 实现指针后移。
- 将当前结点赋值给新表头，循环赋值不断替换，这样保证旧链表的最后一个结点是反转后链表的头结点。
- 指针后移，因为现在的 next 已经是刚才 current 的下一结点了。
- 下一轮循环时，旧的表的下一结点链接到新表头：因为第一轮循环 reverseHead 是 null，所以不用理会。到第二个循环时，这时的 reverseHead 经过第 1 步已经有值且值是初始结点，将 current.next 也就是第三个结点指向初始结点，然后再循环处理到最后实现反转。
-
查找单链表中间结点
一种思路是遍历获取链表长度再拿中间，这里记录不允许遍历的情况：
/**
* 查找单链表中间
* @param head
* @return
*/
public Node findMidNode(Node head){
if(head == null){
return null;
}
// 定义两个
Node first = head;
Node second = head;
// 两个同时移动，但是一个走一步另一个走两步
while (second != null && second.next != null){
first = first.next;
second = second.next.next;
}
return first;
}
思路是定义两个结点，起点一样，循环一个走一步一个走两步，这样当走的最快的走不下去时第一个就是中间结点了。
-
合并两个有序链表，合并后依然有序
例如：
链表1：1 > 2 > 3 > 4
链表2：2 > 3 > 4 > 5
合并后：1 > 2 > 2 > 3 > 3 > 4 > 4 > 5
/**
* 合并两个有序链表
* @param head1 链表1 表头
* @param head2 链表2 表头
* @return
*/
public Node mergeList(Node head1,Node head2){
// 如果两个链表都为 null 返回 null
if(head1 == null && head2 == null){
return null;
}
// 如果其中一个为 null，返回不为 null 的就是要的表头了
if(head1 == null){
return head2;
}
if(head2 == null){
return head1;
}
Node head = null;
Node current = null;
// 判断首位，确认新表头
if((int)head1.data < (int)head2.data ){
head = head1;
current = head1;
head1 = head1.next;
} else {
head = head2;
current = head2;
head2 = head2.next;
}
while (head1 != null && head2 != null){
if((int)head1.data < (int)head2.data){
current.next = head1; // 循环比较，把较小的值链接到新表后
current = current.next;// 指针后移
head1 = head1.next;
} else {
current.next = head2;
current = current.next;
head2 = head2.next;
}
}
// 经过上面循环，head1 还有值说明 head2 循环完毕
if(head1 != null){
// 后面是有序的，所以只要链接到当前结点即可
current.next = head1;
}
// 同理，head1 循环完毕
if(head2 != null){
current.next = head2;
}
return head;
}
自行理会吧...233333.
二、栈
特点：先进后出（后进先出）。也就是说，保存在栈中的元素会像摞书本一样一个一个压在栈中，取出来的时候会一本一本拿。
栈模型（图片来源网络）
Java Stack 类：
Java Stack
-
push(): 往栈中添加数据 -
pop(): 返回栈顶的值并删除 -
peek(): 返回栈顶的值，但不删除 -
search(Object o): 返回元素 o 最后出现下标
一个简单的基于数组的实现：
public class Stack {
// 记录栈顶坐标，同时也可依据该值获取栈顶元素
private int top = -1;
private Object[] data;
public Stack(int capacity) throws Exception {
if(capacity < 0){
throw new Exception("Illegal capacity:"+capacity);
}
data = new Object[capacity];
}
public Object push(Object o) throws Exception {
if(top == data.length - 1){
throw new Exception("Stack is full!");
}
return data[++top] = o;
}
public Object pop() throws Exception {
if(top == -1){
throw new Exception("Stack is empty!");
}
return data[top--];
}
public void print(){
System.out.print("bottom -> top: | ");
for(int i = 0 ; i <= top ; i++){
System.out.print(data[i]+" | ");
}
System.out.print("\n");
}
}
一个简单的基于链表的实现：
public class LinkedStack {
private LinkedList linkedList = new LinkedList();
public void push(Object o){
linkedList.addFirst(o);
}
public Object pop(){
return linkedList.removeFirst();
}
}
三、队列
特点：先进先出 即最先放入的元素最先被取出。元素存放时类似栈，按顺序排列。元素存储时从队尾放入，取出时则先从队头出队。
Queue示意图（Copy）
队列的创建：
一般情况下，队列创建的方式有两种：
- 基于数组创建（顺序队列）
- 基于链表创建（链式队列）
一个简单的队列的实现：
public class Queue {
public Node head;
public Node current;
/**
* 与链表添加数据方式类似
* @param data 数据
*/
public void addNode(int data){
if(head == null){
head = new Node(data);
current = head;
} else {
current = new Node(data);
current = current.next;
}
}
/**
* 出队列永远都是队头的数据
* @return head 的数据
* @throws Exception
*/
public int pop() throws Exception {
if(head == null){
throw new Exception("队列为空");
}
Node node = head; //要出队的Node
head = node.next; //指针后移，因为头已经出队
return node.data;
}
class Node{
Node next;
int data;
public Node(int data){
this.data = data;
}
}
}
四、树（多数资料来自百度百科）
树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；
定义：
树（tree）是包含n（n>0）个结点的有穷集，其中：
(1) 每个元素称为结点（node）；
(2) 有一个特定的结点被称为根结点或树根（root）。
(3) 除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树
相关概念：
- 树的高度/深度，结点的层次（Level）：从根开始定义起，根为第一层，根的子结点为第二层。依次类推，如上图的树深度/高度为 4。
- 森林：m（m>=0）棵互不相交的树的集合。
种类：
- 无序树：树中任意节点的子结点之间没有顺序关系，可以互换，这种树称为无序树,也称为自由树;
- 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
- 二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树
- 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
各种树
- 哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
二叉树
二叉树的结点：
class TreeNode<E>{
E data;
TreeNode left;
TreeNode right;
public TreeNode(E data){
this.data = data;
}
}
二叉树的创建：
private List<TreeNode> datas;//存储所有的节点
public TreeNode root;//根节点
public BinaryTree(){
}
public void createTree(Object[] objs){
datas = new ArrayList<>();
for (Object object : objs) {
datas.add(new TreeNode(object));
}
root=datas.get(0);//将第一个元素作为根节点
for(int i = 0; i < objs.length/2; i++){
datas.get(i).left = datas.get(i*2+1);
if(i*2+2 < datas.size()){// 避免下标越界
datas.get(i).right = datas.get(i*2+2);
}
}
}
二叉树的遍历：
二叉树的遍历方式有很多，如果限制了从左到右的方式，主要可以分为四种：
-
前序/先序遍历
先访问根结点，然后前序遍历左子树，再前序遍历右子树。
//前序/先序遍历
public void preorder(TreeNode<E> root){
if(root == null){
return;
}
System.out.print(root.data+"");
preorder(root.left);
preorder(root.right);
}
- 中序遍历
//中序遍历
public void inorder(TreeNode<E> root){
if(root == null){
return;
}
inorder(root.left);
System.out.print(root.data+"");
inorder(root.right);
}
- 后序遍历
//后序遍历
public void postorder(TreeNode<E> root) {
if (root == null){
return;
}
postorder(root.left);
postorder(root.right);
System.out.println(root.data + " ");
}
三种遍历方式都用到了递归，从代码上看区别就是打印数据的位置。
二叉树的高度：
同样是利用递归以及左右子结点判断逐渐增加高度。
public int height(TreeNode root) {
if (root == null)
return 0;// 递归结束：空树高度为0
else {
int i = height(root.left);
int j = height(root.right);
return (i < j) ? (j + 1) : (i + 1);
}
}
二叉树的结点数量：
public int size(TreeNode root) {
if (root == null) {
return 0;
} else {
return 1 + size(root.left) + size(root.right);
}
}
二叉树的结点插入：
public String insert(int value) {
String error = null;
TreeNode node = new TreeNode(value);
if (root == null) {
root = node;
root.left = null;
root.right = null;
} else {
TreeNode current = root;
TreeNode parent = null;
while (true) {
if (value < (int)current.data) {
parent = current;
current = current.left;
if (current == null) {
parent.left = node;
break;
}
} else if (value > (int)current.data) {
parent = current;
current = current.right;
if (current == null) {
parent.right = node;
break;
}
} else {
error = "having same value in binary tree";
System.out.print(error);
}
} // end of while
}
return error;
}
二叉树的结点删除：
/**
* 删除结点
* @param value
* @return
*/
public boolean delete(int value) {
TreeNode current = root; //需要删除的节点
TreeNode parent = null; //需要删除的节点的父节点
boolean isLeftChild = true; //需要删除的节点是否父节点的左子树
while (true) {
if (value == (int)current.data) {
break;
} else if (value < (int)current.data) {
isLeftChild = true;
parent = current;
current = current.left;
} else {
isLeftChild = false;
parent = current;
current = current.right;
}
//找不到需要删除的节点，直接返回
if (current == null)
return false;
}
//分情况考虑
//1、需要删除的节点为叶子节点
if (current.left == null && current.right == null) {
//如果该叶节点为根节点，将根节点置为null
if (current == root) {
root = null;
} else {
//如果该叶节点是父节点的左子节点，将父节点的左子节点置为null
if (isLeftChild) {
parent.left = null;
} else { //如果该叶节点是父节点的右子节点，将父节点的右子节点置为null
parent.right = null;
}
}
}
//2、需要删除的节点有一个子节点，且该子节点为左子节点
else if (current.right == null) {
//如果该节点为根节点，将根节点的左子节点变为根节点
if (current == root) {
root = current.left;
} else {
//如果该节点是父节点的左子节点，将该节点的左子节点变为父节点的左子节点
if (isLeftChild) {
parent.left = current.left;
} else { //如果该节点是父节点的右子节点，将该节点的左子节点变为父节点的右子节点
parent.right = current.left;
}
}
}
//2、需要删除的节点有一个子节点，且该子节点为右子节点
else if (current.left == null) {
//如果该节点为根节点，将根节点的右子节点变为根节点
if (current == root) {
root = current.right;
} else {
//如果该节点是父节点的左子节点，将该节点的右子节点变为父节点的左子节点
if (isLeftChild) {
parent.left = current.right;
} else { //如果该节点是父节点的右子节点，将该节点的右子节点变为父节点的右子节点
parent.right = current.right;
}
}
}
//3、需要删除的节点有两个子节点，需要寻找该节点的后续节点替代删除节点
else {
TreeNode successor = getSuccessor(current);
//如果该节点为根节点，将后继节点变为根节点，并将根节点的左子节点变为后继节点的左子节点
if (current == root) {
root = successor;
} else {
//如果该节点是父节点的左子节点，将该节点的后继节点变为父节点的左子节点
if (isLeftChild) {
parent.left = successor;
} else { //如果该节点是父节点的右子节点，将该节点的后继节点变为父节点的右子节点
parent.right = successor;
}
}
}
current = null;
return true;
}
/**
*
* 得到后继节点，即删除节点的左后代
*/
private TreeNode getSuccessor(TreeNode delNode) {
TreeNode successor = delNode;
TreeNode successorParent = null;
TreeNode current = delNode.right;
while (current != null) {
successorParent = successor;
successor = current;
current = current.left;
}
//如果后继节点不是删除节点的右子节点时，
if (successor != delNode.right) {
//要将后继节点的右子节点指向后继结点父节点的左子节点，
successorParent.left = successor.right;
//并将删除节点的右子节点指向后继结点的右子节点
successor.right = delNode.right;
}
//任何情况下，都需要将删除节点的左子节点指向后继节点的左子节点
successor.left = delNode.left;
return successor;
}
测试：
public static void main(String[] args){
BinaryTree binTree=new BinaryTree();
Object[] objs={0,1,2,3,4,5,6,7,8,9};
binTree.createTree(objs);
binTree.insert(10);
binTree.preorder(binTree.root);
// binTree.inorder(binTree.root);
// binTree.postorder(binTree.root);
// System.out.print(binTree.height(binTree.root)+" ");
}
关于二叉树更多资料：
五、图
暂时还没有用到图，等到用到的时候再来复习。
六、排序
有空记得自己实现。
其它比较好的文章：
Android程序员面试会遇到的算法(part 1 关于二叉树的那点事) 附Offer情况
那些年，我们被问到的数据结构
网友评论