前言
HaspMap的使用频率非常高，相信在每一个Java项目都能见到HashMap的身影。HashMap的重要性也成为了Java面试中必问的>数据结构，因此我们很有必要了解HashMap的原理结构。
HashMap可以看做为数组和链表组合而的数据结构，看下图：
HashMap结构
想要弄清楚HashMap，首先数组和链表有一定的了解，相信大家都十分了解数组，那么下面重点实现一下单向链表的增，删，改，查功能。
单向链表
百度的解释：
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点。
上面的解释可能有点懵，我们通过代码来了解一下大概意思。
public class MyLinkedList<T>{
/*
* 链表头节点,作为链表的第一个节点
*/
private Entry<T> head;
/*
* 链表长度
*/
private int size;
/*
* 节点
*/
static final class Entry<T>{
private T t;//元素
Entry<T> next;//当前节点的下一个节点
public Entry(T t) {
// TODO Auto-generated constructor stub
this.t= t;
}
}
}
1.首先我们记录一个Entry<T> head链表头结点。
2.在Entry<T>内部类中定义一个next指向下一个节点。
Add方法:
public void add(T t) {
//根据传入的t参数创建一个新节点
Entry<T> entry = new Entry<T>(t);
if(size == 0) {
head = entry;
}else {
//新节点entry的next指向当前记录的head，
//然后新节点entry赋值为当前的head
entry.next = head;
head = entry;
}
//链表长度+1
size++;
}
下面通过一张图了解add函数执行的过程:
添加过程
通过上图我们了解到，
1.节点之间是一环扣一环的.
2.每个节点会跟相邻的两个节点产生关联。
3.插入节点只需要通知相邻节点就可以，不需要遍历整个链表，也说明类似
Delete方法：
public T delete(T t) {
if(head== null) {
return null;
}
//记录前一个节点和后一个节点
Entry<T> current = head;
Entry<T> pervious = head;
//循环查找需要删除的节点
while(!current.t.equals(t)) {
//如果没有到达链表尾部且没有找到删除节点
//循环移动节点指针
if(current.next != null) {
pervious = current;
current = current.next;
}else {
//到达尾部且没找到元素返回空
return null;
}
}
//节点已找到
//如果只有一个节点，则直接删除
if(current.equals(pervious)) {
if(current.next != null) {
head = current.next;
}else {
head = null;
}
}else {
//如果有多个节点，则清除current节点，
//并把current.next改为previous.next
if(current.next != null) {
pervious.next = current.next;
current = null;
}
}
//链表长度-1
size--;
return t;
}
下面通过一张图了解delete方法执行的过程:
删除过程
通过上图我们了解到，只要移动指针找到要删除的节点后，改变指针指向即可实现节点的删除。
Update，Find方法
public void update(T t,T a) {
if(head == null) {
return;
}
Entry<T> current = head;
//循环查找需要更新的节点
while(!current.t.equals(t)) {
//循环移动节点指针
if(current.next != null) {
current = current.next;
}else {
return;
}
}
//找到元素后直接替换
current.t = a;
}
public String find() {
if(head == null) {
return null;
}
Entry<T> current = head;
StringBuilder builder = new StringBuilder();
while(current.next != null) {
current = current.next;
builder.append(current.t.toString());
}
return builder.toString();
}
update,find方法跟delete方法实现的原理都是移动指针。
拓展
通过上述代码简单实现Queue功能
add方法每一次都将节点放在了链表的头部，只需要修改delete方法，见代码：
public void delete() {
//删除链表第一个节点
head = head.next;
//链表长度-1
size--;
}
这样就能够实现后进先出的功能了，非常简单。
