链表在内存中存储如下示意图
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.next
3.被删除的节点将自动被回收
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;
}
}
}