单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
接下来通过一个小Demo来全面实践单链表
先来定义结点的属性：假设以《水浒传》中的一位英雄作为一个结点，no代表他的编号，name表示名字，nickname表示昵称，next为堆中指向下一个英雄结点的地址。（请忽略属性权限）
1 class HeroNode { 2 public int no; 3 public String name; 4 public String nickname; 5 public HeroNode next; 6 7 public HeroNode(int hNo, String hName, String hNickname) { 8 this.no = hNo; 9 this.name = hName; 10 this.nickname = hNickname; 11 } 12 13 @Override 14 public String toString() { 15 return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; 16 } 17 }
有了结点类，就可以创建头结点，进而实现一条单链表了
private HeroNode head = new HeroNode(0, "", "");
首先可以以head结点为头结点，来加入结点，添加的方法分为 ：1、 按照编号no顺序添加（即升序，但不能存在相同no） 2、尾插法 3、头插法
1、 按照编号no顺序添加（即升序，但不能存在相同no）
具体操作由两行代码搞定(也是头插法的代码)
heroNode.next = temp.next;
temp.next = heroNode;
具体代码如下：
1 public void addByOrder(HeroNode heroNode) {//传入一个结点 2 HeroNode temp = head;//用一个temp变量代替head，方便遍历 3 boolean flag = false;//标记单链表中是否存在与heroNode节点no相同的结点 4 while (true) {//遍历单链表进行判断 5 if (temp.next == null)//如果头节点指向为空，则直接跳出循环 6 break; 7 if (temp.next.no > heroNode.no)//传入的结点no与单链表中的no比较 8 break; 9 if (temp.next.no == heroNode.no) {//有重复，则标记true 10 flag = true; 11 break; 12 } 13 temp = temp.next;//遍历，指向下一个结点 14 } 15 if (!flag) {//前两个if跳出循环，都会执行，具体看下图 16 heroNode.next = temp.next; 17 temp.next = heroNode; 18 } else { 19 System.out.println("存在" + heroNode.no); 20 } 21 }
2、尾插法
1 public void addEnd(HeroNode heroNode) { 2 // 尾插法需要遍历单链表到最后一个结点的下一个结点为null的上一个结点 3 HeroNode temp = head; 4 while (true) { 5 if (temp.next == null) 6 break; 7 else 8 temp = temp.next; 9 } 10 temp.next = heroNode; 11 }
3、头插法
1 public void addFirst(HeroNode heroNode) { 2 HeroNode temp = head; 3 heroNode.next = temp.next; 4 temp.next = heroNode; 5 }
由于第二个结点在堆内存中没有指向任何结点，而且没有任何节点指向改no为2的结点，于是该对象随后会被GC回收掉
删除结点代码：
1 public void delete(HeroNode heroNode) { 2 HeroNode temp =head; 3 while (true) { 4 if (temp.next == null) { 5 System.out.println("链表为空"); 6 break; 7 } 8 if (temp.next == heroNode) { 9 temp.next = heroNode.next; 10 heroNode.next = null; 11 break; 12 } 13 temp = temp.next; 14 } 15 }
修改结点代码：
1 public void update(HeroNode heroNode, String name) { 2 HeroNode temp = head; 3 while (true) { 4 if (temp.next == null) { 5 System.out.println("链表为空"); 6 break; 7 } 8 if (temp.next == heroNode) { 9 heroNode.name = name; 10 break; 11 } 12 temp = temp.next; 13 } 14 }
借助一个新的头结点来生成反向单链表，最后再由原来的头结点指向这个新的头结点的下一个结点即可，分析图如下：
temp用来代替头结点进行移动操作，next用于保存temp的下一个结点，reverseNode为辅助头结点
得到：
进行头插法
具体反转单链表代码：
1 public void revList() { 2 // 关键就是借助了下面这个辅助头节点 3 HeroNode reverseNode = new HeroNode(0, "", ""); 4 // 下面这个是要保存当前节点的下一个节点的 5 HeroNode next = null; 6 HeroNode temp = head.next;// 将head后的一大串单链表copy一份交给temp管理 7 while (true) { 8 if (temp == null) { 9 break;// 单链表为空 10 } 11 next = temp.next;// 保存下一个节点，比如当前temp->1,那么next就等于temp->2 12 temp.next = reverseNode.next;// 1的next赋值为null，下一次就是2的next赋值为1 13 reverseNode.next = temp;// 这一步就是上面“下一次里的next”赋值为1的操作 14 temp = next;// 到这一步的时候，本次temp已经和原来的单链表断开了，所以需要next提前保存temp.next 15 } 16 head.next = reverseNode.next; 17 }
思路：将按照升序加入结点的两个单链表进行升序合并。
以此规律可得到结果：
具体升序合并单链表代码：
1 public SingleLinkedList merge(SingleLinkedList sl, SingleLinkedList sl2) { 2 SingleLinkedList ss = new SingleLinkedList(); 3 HeroNode temp1 = sl.head.next; 4 HeroNode temp2 = sl2.head.next; 5 HeroNode next = null; 6 while (true) { 7 if (temp1 == null && temp2 == null) {//当两个链表都遍历完时 8 break; 9 } 10 if (temp1 == null && temp2 != null) {//当其中一个链表还有结点,但是另一个已经遍历完，则将此链表剩余部分依次加入新链表ss 11 next=temp2.next; 12 ss.addByOrder(temp2); 13 temp2 = next; 14 } else if (temp2 == null && temp1 != null) {//同上 15 next=temp1.next; 16 ss.addByOrder(temp1); 17 temp1 = next; 18 } 19 if (temp1 != null && temp2 != null) {//都没有遍历完 20 if (temp1.no < temp2.no) {//把no小的加入新链表 21 next = temp1.next;//保存下一节点 22 ss.addByOrder(temp1);//这一步会导致temp1指向改变，导致链表丢失 23 temp1 = next;//所以需要恢复到temp1得下一个 24 } else { 25 next = temp2.next; 26 ss.addByOrder(temp2); 27 temp2 = next; 28 } 29 } 30 } 31 return ss; 32 }
所有随笔，皆为复习巩固。如有错误，欢迎指正。
数据结构之单链表（合并两个单链表有序化、单链表反转、头插尾插，CRUD）
原文：https://www.cnblogs.com/taichiman/p/12829185.html