链表
链表在内存中存储如下示意图
head头节点的下一个节点地址为150即a1，a1下一个节点地址为110即a2，a2的下一个节点地址是180即a3.... 通过上图我们总结如下： 链表是有序的列表，链表中的数据元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息，可以充分利用碎片内存。 链表还分为带头节点的链表和没带头节点的链表。
单链表
根据上面的示意图，我们来实现一个简易的单向链表。
需求如下：
1.将用户信息保存至链表中，按照添加的顺序保存
2.显示链表中的所有数据
思路分析
根据链表的特性我们知道，链表的节点一般包含data域和next域，data域存放具体的数据，而next则存入下一个节点的地址。
这里最关键的问题是如何创建一个单链表
创建单链表 1.首先我们得有一个头节点，这个头节点我们不会存放任何数据，他的主要作用是用于表示单链表的头部。
2.当我们创建第一个节点的时候就让头节点的next域指向第一个节点，当然这个节点包含data域和next域，data存放这个节点的数据，next默认为null
3.当我们每次向单链表中添加数据时，都要遍历单链表中的数据（因为要拿到next为null的节点），当找到这个next为null的节点后，我们让这个节点的next指向新添加的节点，同时新添加的节点的next被置为null
4.这样一直反复就形成了一个链式存储。
示意图如下：
遍历单链表 1.遍历的时候，我们需要一个临时指针，帮助我们遍历整个单链表。 2.每次循环我们都会将这个临时指针后移，直到临时指针的next为null
单链表代码实现
首先创建一个UserNode的类，每一个UserNode对象就是一个节点
class UserNode {
public int id;
public String name;
public String nickName;
public UserNode next;
public UserNode(int id, String name, String nickName) {
this.id = id;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "UserNode{" +
"id=" + id +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}创建一个单链表类
class SingleLink{
//头节点 标识链表头，固定不动
private UserNode head = new UserNode(0,"","");
/**
* 节点添加
* @param usernode
*/
public void add(UserNode usernode){
//设置一个临时变量存放节点
UserNode temp = head;
while(true){
//已经指向最后一个节点，退出循环
if(temp.next==null){
break;
}
//如果当前节点不是最后一个节点则使temp后移
temp = temp.next;
}
//循环退出后temp已经指向了最后一个节点
//此时将即将添加进链表的节点的地址赋给最后一个节点
temp.next = usernode;
}
/**
* 节点展示
*/
public void showList(){
//首先判断链表是否为空
if(head.next==null){
System.out.println("链表为空");
return;
}
//如果不为空，那么至少有一个节点
UserNode temp = head.next;
while (true){
//最后一个节点，跳出循环
if(temp==null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}测试运行结果
UserNode user1 = new UserNode(1, "张三", "张三");
UserNode user2 = new UserNode(2, "李四", "李四");
UserNode user3 = new UserNode(3, "王二", "王二");
UserNode user4 = new UserNode(4, "李武", "李武");
UserNode user5 = new UserNode(5, "杨六", "杨六");
SingleLink singleLink = new SingleLink();
//添加数据到链表
singleLink.add(user1);
singleLink.add(user2);
singleLink.add(user3);
singleLink.add(user4);
singleLink.add(user5);
//展示链表的数据
singleLink.showList();返回入下
UserNode{id=1, name='张三', nickName='张三'}
UserNode{id=2, name='李四', nickName='李四'}
UserNode{id=3, name='王二', nickName='王二'}
UserNode{id=4, name='李武', nickName='李武'}单链表按顺序插入
我们在原来单链表的基础之上在添加一个需求---要求单链表的节点按照ID编号顺序插入
思路分析
1.在添加节点时，首先我们要找到新添加的节点位置
如下2节点，当他即将被插入时，首先要获取他在链表上的位置。
如下图示2号节点的位置应该在 1号和四号之间
2.得到新添加节点的位置后，我们让新添加的节点的next域指向最右边那个节点（如这里是四号节点）
2.1如何使得新添加的节点的next域指向这里的四号节点？
2.2这里我们可以使用一个临时的指针temp，这个指针表示新添加节点的左边节点（如这里节点2的左边节点是节点1，那么temp就是1号节点）。
3.得到临时指针后，我们让新添加的节点的next域等于temp的next域，并且使temp的next指向新添加的节点
单链表顺序插入代码实现
/**
* 按照id编号顺序添加
* @param userNode
*/
public void addByorder(UserNode userNode){
UserNode temp = head; //初始化temp节点
boolean flag = false; //id是否存在的标识
while (true){
//判断temp是否指向了null,指向null说明是最后一个节点，此时新添加的元素应该在temp的后面
if(temp.next==null){
break;
}
if(temp.next.id > userNode.id){
//已经找到了新添加节点的位置
break;
} else if(temp.next.id == userNode.id){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
System.out.println("错误，用户id发生重复");
}else{
userNode.next = temp.next;
temp.next = userNode;
}
}根据编号修改单链表
需求如下跟id修改单链表中的节点 这里比较简单，直接上代码
/**
* 根据 id 修改节点
* @param newUserNode
*/
public void update(UserNode newUserNode){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空，想啥呢");
return;
}
//临时指针 用于遍历
UserNode temp = head.next;
boolean flag = false; //找到具体的元素标识
while(true){
if(temp == null){
//已经遍历完毕
break;
}
if(temp.id == newUserNode.id){
//已经找到要修改的节点
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = newUserNode.name;
temp.nickName = newUserNode.nickName;
}else{
System.out.println("没有找到相应的节点");
}
}根据编号删除单链表中的节点
思路分析
我们实现删除节点的操作是 后移待删除节点的前一个节点的next域，即将待删除的前一个节点的next域,修改为待删除节点的next域，这样待删除节点就会到达一个“无引用”的效果，从而被垃圾回收机制自动回收 1.首先我们要找到需要删除的这个节点的前一个节点temp 这里为什么找的待删除节点的前一个节点，而不是待删除节点本身
因为这里是单链表，节点之间的连接是通过next域进行的，如果temp表示的是待删除的节点，那么我们将无法删除节点，因为我们不知道待删除节点的前一个节点是什么，从而导致无法后移next域。
2.后移next 即
temp.next = temp.next.next3.被删除的节点将自动被回收
代码实现
public void del(int id){
UserNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){
//遍历到数组末尾
break;
}
if(temp.next.id == id){
//找到要删除的节点
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
}
}以上我们完成了单链表的创建、顺序插入、修改、删除。
双向链表
通过实现单链表，我们发现如下问题
1.单链表的查找方向只能是一个方向，而双向链表可以进行前后查找
2.单链表中的节点不能自我删除，需要靠辅助节点
3.双向链表可以自我删除
双向链表示意图
双向链表实现思路分析
添加
先找到双向链表的最后一个节点(temp)
使temp.next=新添加节点
使新节点的pre指向temp
遍历
遍历与单链表一样，不过双向链表可以向前向后查找
修改
修改与单链表的修改一样
删除
这里与单链表不一样，双向链表可以直接找到要删除的这个节点如temp
使temp.pre.next=temp.next
使temp.next.pre=temp.pre
如下图 “数据5“为删除的节点
代码实现
双向链表的修改与遍历和单向链表一样，这里就不在展示 重写userNode
class UserNode {
public int id;
public String name;
public String nickName;
public UserNode next; //后一个节点
public UserNode pre; //前一个节点
public UserNode(int id, String name, String nickName) {
this.id = id;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "UserNode{" +
"id=" + id +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}添加
class DoubleLink{
//头节点 标识链表头，固定不动
private UserNode head = new UserNode(0,"","");
/**
* 节点添加
* @param usernode
*/
public void add(UserNode usernode){
//设置一个临时变量存放节点
UserNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
/找到最后一个节点，将新节点添加到双向链表末尾
temp.next = usernode;
usernode.pre = temp;
}删除
public void del(int id){
if(head.next == null){
return;
}
UserNode temp = head.next;
boolean flag = false; //是否找到要删除的节点
while (temp!=null){
if(temp.id == id){
//找到要删除的节点
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.pre.next=temp.next;
//不是最后一个节点，才连接pre
if(temp.next !=null){
temp.next.pre=temp.pre;
}
}
}