Java教程
手撸代码模拟单向链表--数据结构与算法小结2
正在看文章的你不妨试着回答一下java岗位必问面试题：
1.HashMap的底层数据结构是什么？
2.他的set的过程是怎么样的？
3.hashmap产生哈希冲突了怎么做的？（和问题2有关）
如果你暂时说不清楚的话就试着看下我：
上菜！！！：
本文章脑图：
前言：不知大家有没有在面试中碰到过这样的问题，反正我是碰到过？而且当时面试的还是一家普通的外包公司，所以hashmap的数据结构相关面试题可以说是非常普遍了，所以关于这一块的数据结构非常有必要花时间去钻研一下，有实力和精力的甚至建议去读源码；
一 为什么面试官那么喜欢问HashMap这个板块？
很简单！！！
1.从数据结构的角度：HashMap就涉及到了：数组+链表+红黑树，这对面试者对数据结构的掌握有一定的要求；
2.从面试检验是否技术底层牢固的角度：死记硬背面试题是可以回答出一些内容的，但是如果没有理解透彻的话，面试官稍微换个角度问，马上就露馅了；
二 学习HashMap底层数据结构小tips
首先每个人有每个人的学习方式，对于像我这种半路出家恶补基础的人来说，我的建议是这样的：
1.学习数组+链表的数据结构
2.学习二叉树+红黑树的数据结构
3.尝试手动依次实现这些数据结构（什么语言随你）
4.借助HashMap的实现过程，将以上学习到的内容串在一起；
三 什么是链表？
数组很容易理解，先从链表开始）
3.1 理解链表，建立画面感
官方定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
大白话：
1.玩过老鹰抓小鸡吗？被抓的小鸡们就是一个单向链表，除了第一个人（头节点），余下每个人只专注抓稳一个人，后面不管；
2.看过解放军战士的抗洪一线新闻吗？解放军手拉手站在洪水里，和洪水斗争那英勇的样子就是双向链表；
PS：致敬！！！
3.2 单向链表内部：
内部的各个节点，每一个节点包含：
1.存储的元素（data）
2.指向下一个节点的指针next；
public static class Node<T> {
//存储文件，元素
private T data;
//存储下一个节点
private Node next;
}
整个链表的连接是通过每一个节点内部的next指针指向自己的下一个节点的方式环环相扣，就像老鹰抓小鸡游戏里面的一群小鸡，每一个人只管抓前面一个人，就这样一直保持一个长长的的队伍进行着游戏；
3.3 双向链表内部：
双向链表稍微复杂一些，每一个节点包含：
1.存储的元素（data）
2.指向下一个节点的指针next
3.指向上一个节点的指针previous
PS：
public static class Node<T> {
//存储文件，元素
private T data;
//存储下一个节点
private Node next;
//存储上一个节点
private Node previous;
}
整个链表的连接是通过每一个节点内部的next指针指向自己的下一个节点，previous指向自己的上一个节点，环环相扣，就像解放军战士手拉着手，铸成最坚固的人墙！！！
四 链表的基本API（查-增-改-删）
先瞅瞅原本方法名是啥样：
import java.util.LinkedList;
//可以直接复制过去自己idea瞅瞅
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
//API 新增
linkedList.add("one");
linkedList.add("two");
System.out.println("linkedList.size() = " + linkedList.size());
//在头结点增加和在尾结点增加
linkedList.addFirst("zero");
linkedList.addLast("ten");
//修改指定位置的元素
linkedList.set(1, "changeOne");
//得到指定位置的元素
linkedList.get(1);
//for循环遍历，迭代器使用
for (String message : linkedList) {
System.out.println("循环得到" + message);
}
System.out.println("------------------------");
//删除指定位置的元素
linkedList.remove(1);
for (String message : linkedList) {
System.out.println("循环得到" + message);
}
System.out.println("------------------------");
//删除头结点和尾结点：remove() 和removeFirst()作用一样
//linkedList.remove();
linkedList.removeFirst();
//for循环遍历，迭代器使用
for (String message : linkedList) {
System.out.println("循环得到" + message);
}
linkedList.removeFirst();
linkedList.removeLast();
}
}
也就是要实现下面的这样的方法：
/** * 手动模拟一个单向链表list * 单向链表API：(这里选择一部分进行实现) * 无参构造方法 * list.add(data) * list.add(index,data) * list.addFirst() * list.addLast() * list.remove(index) * list.removeAll() * list.removeFirst() * list.removeLast() * list.set(index,data) * list.setFirst() * list.setLast() * list.get(index) * list.getFirst() * list.getLast() */
4.1 查： 链表的查找
链表的查找操作是比较繁琐的，一句话总结：从头开始一个一个找，直到找到为止，分解如下
第一步：拿到header节点；
//先定一个node作为标记（当前节点）； Node node = header;
第二步: 通过header的next指针找到下一个节点；
第三步：通过第二步拿到的节点，对比当前的index以及目标节点的index，对上了找到然后返回，反之继续获取下一个节点；
//假如index大于等于1，遍历依次将node标记向后移动，一直到index处；
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
第四步：返回node中的data
//获取到对应索引的data
public Object get(int index) {
return getNode(index).data;
}
4.2 增： 链表的指定位置节点的插入（想一下，你想插队老鹰抓小鸡队伍里，你会怎么做？）
有了第一个get的API，这个就方便一些，步骤如下：
第一步：获取到指定index-1 处的node（nodeIndexFront）
第二步：获取到指定index 处的node（indexNode）
第三步：将第一步的nodeIndexFront的下一个节点设置成新插入的节点
第四步：将新插入的节点的下一个节点设置成第二步的indexNode
第五步：链表长度+1
代码上！！！
//在指定位置index处，添加data
public void add(int index, T data) {
//首先判断是否index是否超纲
if (index < 0 || index > length) {
throw new IndexOutOfBoundsException("IndexOutOfBoundsException;index超出数组长度");
}
//拿到在index处的node
Node nodeIndex = getNode(index);
//拿到在index - 1 处的node
Node nodeIndexFront = getNode(index - 1);
//将在index - 1 处的node 下一个节点设置为新增的node（nodeInsert）
Node nodeInsert = new Node(data);
nodeIndexFront.next = nodeInsert;
//将在index处的node（nodeInsert）下一个节点设置为原本index处的node
nodeInsert.next = nodeIndex;
//长度+1
length++;
}
4.3 改： 链表的指定位置节点的更改（可以直接看代码）
到这里，如果你已经理解了前面两个 增+查两个的实现的话，这里就很顺利成章了，步骤如下：
第一步：获取到指定index-1 处的node（nodeIndexFront）
第二步：获取到指定index+1 处的node（nodeIndexBack）
第三步：将第一步的nodeIndexFront下一个节点设置成新插入的节点；
第四步：将新插入的节点的下一个节点设置成第二步的nodeIndexBack
第五步：链表长度+1
撸代码：
//修改在index的data
//思路，将index-1处的next设置为新的node，然后
public void set(int index, T data) {
//首先判断是否超纲（这里可以提取出一个方法，判断index是否越界，越界返回true，否返回false）
if (index < 0 || index > length) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
//拿到在index+1处的node
Node nodeIndexBack = getNode(index + 1);
//拿到在index - 1 处的node
Node nodeIndexFront = getNode(index - 1);
//将在index - 1 处的node 下一个节点设置为新增的node（nodeInsert）
Node nodeInsert = new Node(data);
nodeIndexFront.next = nodeInsert;
//将在index 处的node 下一个节点设置为index+1处的node（nodeIndexBack）
nodeInsert.next = nodeIndexBack;
}
4.4 删：这里留个homework吧，自己手动试着实现一下，因为也不难，嘿嘿，皮这一下很开心
//大家可以试着动手实现一下，注意判断index是否越界
public void remove(int index) {
}
五 手撸单向链表代码（完整有点长）：
public class MyList<T> {
private Node header;
private Node tail;
private int length = 0;
//无参构造，构造出头节点和尾节点，并且将头节点next指针指向尾节点（头节点不储存元素）
public MyList() {
header = new Node<T>();
tail = new Node<T>();
header.next = tail;
}
/**
* 新增
* @param data
*/
public void add(T data) {
//构造函数新增node节点
Node node = new Node(data);
//如果长度为0，直接在头结点加，并设为尾结点
if (length == 0) {
header.next = node;
//将node设为尾结点
tail = node;
length++;
return;
}
//如果长度不为0，将tail的下一个节点设置为node，
tail.next = node;
//将node带上tail的标签，变成尾结点
tail = node;
//别忘记增加长度
length++;
}
//在指定位置index处，添加data
public void add(int index, T data) {
//首先判断是否index是否超纲
if (index < 0 || index > length) {
throw new IndexOutOfBoundsException("IndexOutOfBoundsException;index超出数组长度");
}
//拿到在index处的node
Node nodeIndex = getNode(index);
//拿到在index - 1 处的node
Node nodeIndexFront = getNode(index - 1);
//将在index - 1 处的node 下一个节点设置为新增的node（nodeInsert）
Node nodeInsert = new Node(data);
nodeIndexFront.next = nodeInsert;
//将在index处的node（nodeInsert）下一个节点设置为原本index处的node
nodeInsert.next = nodeIndex;
//长度+1
length++;
}
//获取到对应索引的data
public Object get(int index) {
/*//return getNode(index).data;代码的分步骤
Node node = getNode(index);
Object data = node.data;
return data;*/
return getNode(index).data;
}
//获取对应位置的节点
private Node getNode(int index) {
//首先判断是否超纲
if (index < 0 || index > length) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
//先定一个node作为标记（当前节点）；
Node node = header;
//假如index大于等于1，遍历依次将node标记向后移动，一直到index处；
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
//修改在index的data
//思路，将index-1处的next设置为新的node，然后
public void set(int index, T data) {
//首先判断是否超纲（这里可以提取出一个方法，判断index是否越界，越界返回true，否返回false）
if (index < 0 || index > length) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
//拿到在index+1处的node
Node nodeIndexBack = getNode(index + 1);
//拿到在index - 1 处的node
Node nodeIndexFront = getNode(index - 1);
//将在index - 1 处的node 下一个节点设置为新增的node（nodeInsert）
Node nodeInsert = new Node(data);
nodeIndexFront.next = nodeInsert;
//将在index 处的node 下一个节点设置为index+1处的node（nodeIndexBack）
nodeInsert.next = nodeIndexBack;
}
//拿到length长度
public int size() {
return length;
}
//移除index处的data
//思路就是拿到index - 1和index+1处的node，然后让index+1成为 index-1处的next节点即可
//大家可以试着动手实现一下
public void remove(int index) {
}
/**
* 节点
*/
public static class Node<T> {
//存储文件，元素
private T data;
//存储下一个节点
private Node next;
public Node() {
this.data = null;
}
public Node(T data) {
this.data = data;
}
}
}
六 测试方法测试：
public class MyListTest {
//测试MyList
public static void main(String[] args) {
System.out.println("测试新建单向链表");
MyList<Integer> myList = new MyList<>();
System.out.println("myList.size() = " + myList.size());
//增加元素
System.out.println("测试单向链表增加元素");
myList.add(0);
myList.add(1);
myList.add(2);
System.out.println("测试单向链表size方法是否准确");
System.out.println("myList.size() = " + myList.size());
System.out.println("测试单向链表set方法和get方法是否准确");
myList.set(2, 9);
System.out.println("myList.get(2): " + myList.get(2));
System.out.println("测试单向链表测试指定位置add元素");
myList.add(2,8);
System.out.println("myList.get(2): " + myList.get(2));
System.out.println("myList.get(3): " + myList.get(3));
System.out.println("myList.size() = " + myList.size());
//最后留个位置给大家写remove的测试
//myList.remove();
}
}
END总结：多问为什么？多思考！多敲代码！不图快，只图啃下来！
完活！这次先到这，以后再慢慢手动实现一下二叉树红黑树啥的~
特此感谢<小灰的算法之旅>这本书，给了很多的启发和系统性的讲解！强烈推荐大家作为算法的入门进行学习；
周末快乐，下周再见，不说了，笨鸟要继续肝算法了~
-
MQ底层原理资料详解：新手入门教程11-28
-
MQ项目开发资料详解：新手入门教程11-28
-
MQ项目开发资料详解：入门与初级用户指南11-28
-
MQ消息队列资料入门教程11-28
-
MQ消息队列资料：新手入门详解11-28
-
MQ消息中间件资料详解与应用教程11-28
-
MQ消息中间件资料入门教程11-28
-
MQ源码资料详解与入门教程11-28
-
MQ源码资料入门教程11-28
-
RocketMQ底层原理资料详解11-28
-
RocketMQ项目开发资料入门指南11-28
-
RocketMQ项目开发资料详解：新手入门与初级教程11-28
-
RocketMQ消息中间件资料入门教程11-28
-
RocketMQ源码资料入门教程11-28
-
RocketMQ源码资料入门教程11-28
