链表是以节点的方式链式存储的有序列表，链表中的每个节点在内存空间上不一定是连续的，可以利用内存空间中细小的不连续空间，内存使用率高，链表是动态分配内存的扩展灵活。
单向链表在内存中的存储如下：
特点：
每个节点包括 data域 和 next域，next指向下一个节点的地址；
链表中的每个节点在内存空间上不一定是连续的。
链表分为带头节点的和不带头节点的，对于带头节点的链表，头节点不存放数据，只用于表示链表的开始。
带头节点的单向链表逻辑结构如下：
首先创建 head 头节点，之后每次增加节点都是在链表的最后面追加。
1）遍历找到链表的最后一个节点（next指针执行null 的节点）；
2）让最后一个节点的 next 指向待新增的节点；
遍历链表，找到可以增加节点的正确位置，由于是单向链表，每个节点只有指向下一个节点的 next指针，因此需要找到插入位置的前一个节点。
1）遍历链表，找到插入位置的前一个节点；
2）让新增节点的 next 指向插入位置的后一个节点；
3）让插入位置的前一个节点的next 指向新增节点；
找到需要修改的节点，直接修改
找到要删除的节点，由于是单向链表，因此要找到被删除节点的前一个节点。
1）找到删除节点的前一个节点；
2）让删除位置的前一个节点的next 指向 删除节点的后一个节点；
3）被删除的节点不在被引用，会自动被垃圾回收机制回收；
我要评论package linkedlist;
import org.junit.Test;
/**
* 单项链表
* @author
* @create 2020-07-14 8:18 AM
*/
public class SingleLinkedListDemo {
@Test
public void testAdd(){
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(new StudentPo(1,"zs"));
singleLinkedList.add(new StudentPo(4,"zl"));
singleLinkedList.add(new StudentPo(2,"ls"));
singleLinkedList.add(new StudentPo(3,"ww"));
singleLinkedList.showLinkedList();
}
@Test
public void testAddByOrder(){
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(new StudentPo(1,"zs"));
singleLinkedList.addByOrder(new StudentPo(4,"zl"));
singleLinkedList.addByOrder(new StudentPo(2,"ls"));
singleLinkedList.addByOrder(new StudentPo(3,"ww"));
singleLinkedList.showLinkedList();
}
@Test
public void testUpdate(){
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(new StudentPo(1,"zs"));
singleLinkedList.addByOrder(new StudentPo(4,"zl"));
singleLinkedList.addByOrder(new StudentPo(2,"ls"));
singleLinkedList.addByOrder(new StudentPo(3,"ww"));
System.out.println("修改前～～～");
singleLinkedList.showLinkedList();
singleLinkedList.update(new StudentPo(1,"张三"));
System.out.println("修改后～～～");
singleLinkedList.showLinkedList();
}
@Test
public void testDel(){
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(new StudentPo(1,"zs"));
singleLinkedList.addByOrder(new StudentPo(4,"zl"));
singleLinkedList.addByOrder(new StudentPo(2,"ls"));
singleLinkedList.addByOrder(new StudentPo(3,"ww"));
System.out.println("删除前～～～");
singleLinkedList.showLinkedList();
singleLinkedList.del(1);
System.out.println("删除后～～～");
singleLinkedList.showLinkedList();
}
}
class SingleLinkedList{
//创建头节点，头节点不存放任何数据，只用来表示链表的头部.在对链表的操作中，头部节点保持不动
private StudentPo headNode = new StudentPo(0,"");
/**
* 向单向链表中添加元素
* @param student 要添加的节点
*
* 分析：向单项链表中添加元素，就是在链表的尾部追加元素。
* 1.从头开始找，找到链表的最后一个元素；
* 2.让链表的最后一个元素的 next 指向要添加的节点；
*/
public void add(StudentPo student){
StudentPo temp = headNode;
while(true){
if(temp.next==null){
break;
}
temp = temp.next;
}
temp.next=student;
}
/**
* 向单向链表中按顺序添加元素
* @param newStudent 要添加的节点
* 需求：
* 1）向当前单向链表中添加元素，按照sno从小到大的顺序添加
* 2）如果当前链表中已经存在同一个 sno 的学生，则不能添加。
*
* 分析：
* 1）按顺序添加就需要找到当前节点的添加位置
* 2）由于是单项链表，每个节点只有next指针指向后一个元素，因此寻找添加元素的位置时，要找到该位置的前一个元素；
* 3）让前一个元素的 next 指向要添加的 newStudent 节点，再让 newStudent 节点的next 指向该位置的后一个节点；
* 4）由于head 头节点不能动，需要指定一个中间临时变量接收 head 节点，以便往后移动寻找可添加元素的位置
*/
public void addByOrder(StudentPo newStudent){
StudentPo temp = headNode;
boolean flag = false;//表示 当前链表中是否存在同一个 sno 的学生，默认不存在。
while(true){
if(temp.next==null){//开始遍历时，temp（head）的next就是第一个元素，即从第一个元素开始挨个比一遍，直到找到可添加元素的位置
break;
}
if(temp.next.sno>newStudent.sno){
break;
}else if(temp.next.sno == newStudent.sno){
flag=true;
break;
}
temp= temp.next;
}
if(flag){
System.out.println("已经存在相同学号的学生了。。。");
return;
}else{
newStudent.next = temp.next;
temp.next = newStudent;
}
}
/**
* 修改链表中的元素
* @param student 要修改的节点
* 分析：
* 从头开始找，找到要修改的节点，直接赋值修改
*
*/
public void update(StudentPo student){
boolean flag = false;//是否找到了要修改的元素
if(headNode.next==null){
System.out.println("链表为空～～～");
return;
}
StudentPo temp = headNode.next;
while(true){
if(temp==null){//已经遍历到了链表的最后一个元素，没找到要修改的元素
break;
}
if(temp.sno==student.sno){
flag=true;
break;
}
temp=temp.next;
}
if(flag){
temp.sname=student.sname;
}else{
System.out.println("没有找到学号为["+student.sno+"]的节点，不能修改～～～");
}
}
/**
* 删除链表中的元素
* @param sno 要删除的节点的编号（学号）
* 分析：
* 由于是单项链表，只能通过 next 向后查找，因此需要找到待删除节点的前一个节点，让它的 next 指向待删除节点的后一个节点，此时形成一个新的链表。
* 指针重新指向待删除节点的后一个节点后，被删除的节点不在被引用，会被垃圾回收机制自动回收。
*/
public void del(int sno){
if(headNode.next==null){
System.out.println("链表为空～～～");
return;
}
StudentPo temp = headNode;
boolean flag = false;//表示是否找到要删除的节点
while(true){
if(temp.next==null){//一直遍历到最后一个节点了，也没找到要删除的节点
break;
}
if(temp.next.sno==sno){
flag=true;
break;
}
temp = temp.next;
}
if(flag){
temp.next=temp.next.next;
}else{
System.out.println("没有找到学号为["+sno+"]的节点，不能删除～～～");
}
}
/**
* 展示当前链表中的所有元素
*/
public void showLinkedList(){
if(headNode.next==null){
System.out.println("链表为空～～～");
return;
}
StudentPo temp = headNode.next;//从头节点的下一个节点开始遍历
while(true){
if(temp==null){
break;
}
System.out.println("学号："+temp.sno+",姓名："+temp.sname);
temp=temp.next;
}
}
}
class StudentPo{
public int sno;
public String sname;
public StudentPo next;
public StudentPo() {
}
public StudentPo(int sno, String sname) {
this.sno = sno;
this.sname = sname;
}
@Override
public String toString() {
return "StudentPo{" +
"sno=" + sno +
", sname='" + sname + '\'' +
'}';
}
}
/**
* 1.求单向链表中有效节点的个数
* 分析：
* 求有效节点的个数就是从第一个节点开始遍历，直到最后一个（next 指向 null的节点），统计数量
*
* @param headNode
*/
public int getLength(StudentPo headNode){
int length = 0;
if(headNode.next==null){
System.out.println("当前链表为空～～～");
return 0;
}
StudentPo temp = headNode.next;
while (temp!=null){
length++;
temp = temp.next;
}
return length;
}
/**
* 2.查找单链表中倒数第k个节点
* 分析：
* 1）遍历整个链表，得到链表的有效节点个数 size
* 2）要找到倒数第k个节点，即是从链表第一个节点开始遍历，向后移动 size-k 次即可得到。
* @param headNode
* @return
*/
public StudentPo getRecipKNode(StudentPo headNode , int k){
if(headNode.next==null){
System.out.println("当前链表为空～～～");
return null;
}
int size = getLength(headNode);
// 对 k 做校验，倒数滴k个节点，则k的值必须符合：k>0,&& k<size
if(k<=0 || k>size){
System.out.println("K 的值不在 链表范围内");
return null;
}
StudentPo temp = headNode.next;
for(int i=0;i<size-k;i++){
temp = temp.next;
}
return temp;
}
/**
* 3.单链表的反转
* 分析：
* 反转的意思是：让链表中的节点按照相反的顺序连接在 head节点后面。
* 1）创建一个新的头部节点 reverseHead，用于连接反转过来的节点；
* 2）从头开始遍历需要反转的链表，每取出一个节点，都放在 reverseHead 后的第一个位置；
* 3）从原链表中取出所有节点后，head.next = reverseHead.next 让head 节点指向反转后的链表节点
* tips: 由于是单向链表，所以每次从原链表中取出一个节点，都要用 一个变量记下下一个节点，否则就找不到下一个节点了
* @param headNode
*/
public void reverseLinkedList(StudentPo headNode){
StudentPo reverseHead = new StudentPo(0,"");
if(headNode.next==null){
System.out.println("当前链表为空～～～");
return;
}
StudentPo temp = headNode.next;
StudentPo next = null;
while (temp!=null){
//先记录下一个节点
next = temp.next;
//将取下来的节点添加到reverseHead的第一个位置
temp.next = reverseHead.next;
reverseHead.next = temp;
temp = next;
}
headNode.next = reverseHead.next;
}
/**
* 4.从尾到头 反向打印单链表
* 分析：
* 方式一：先将链表反转，再顺序打印出（但是会改变原来的链表）
* 方式二：将链表中的节点顺序遍历，压入栈中，然后再从栈中弹出即可（利用栈的先进后出原理）
* @param headNode
*/
public void printLinkedList(StudentPo headNode){
Stack<StudentPo> stack = new Stack();
StudentPo temp = headNode.next;
while(temp!=null){
stack.push(temp);
temp = temp.next;
}
while(stack.size()>0){
StudentPo obj = stack.pop();
System.out.println(obj);
}
}
/**
* 5.合并两个有序的单链表，合并之后依然有序
* 分析：
* 以 链表l1 为基准，遍历 l2 ，将l2 中的节点挨个添加到 l1 链表中去。
* 1）遍历l2，每次从 l2 中按顺序取出一个节点；
* 2）拿着这个节点，在l1 中寻找合适的位置的前一个节点；
* 3）让新增节点的 next 指向 插入位置的下一个节点；
* 4）让新增位置的前一个节点的 next 指向新增节点；
*
* @param l1
* @param l2
*/
public SingleLinkedList mergeLinkedList(SingleLinkedList l1,SingleLinkedList l2){
StudentPo headNode1 = l1.getHeadNode();
StudentPo headNode2 = l2.getHeadNode();
if(headNode1.next==null){
System.out.println("链表1为空");
return l2;
}
if(headNode2.next==null){
System.out.println("链表2为空");
return l1;
}
StudentPo temp1 = headNode1.next;
StudentPo temp2 = headNode2.next;
StudentPo next = null;
while(true){
if(temp2==null){
break;
}
boolean flag = false; //是否找到了添加的位置
while(true){
if(temp1.next==null){
break;
}
if(temp1.next!=null && temp1.next.sno>temp2.sno || temp1.next.sno==temp2.sno){
flag=true;
break;
}
temp1 = temp1.next;
}
next = temp2.next;
if(flag){
temp2.next = temp1.next;
temp1.next=temp2;
}else{
temp1.next=temp2;
}
temp2 = next;
}
return l1;
}
本文地址：https://blog.csdn.net/zxjdC/article/details/107339771
如对本文有疑问， 点击进行留言回复！！
网友评论