什么是链表
- 链表以节点的方式存储, 是链式存储
- 每个节点包含data域, next域, next指向下一个节点, 以此形成一条链
- 链表的各个节点不一定是连续存储的
- 链表分带头节点和不带头节点
- 链表分为单链表和双向链表
单向链表
-
单链表示意图
带头节点的单链表示意图 通过一个例子来认识单链表
如何使用带头单链表实现水浒英雄排行榜管理, 并对英雄任务进行增删改查?
思路分析:
1.先创建一个头节点, 不存放具体数据, 作用就是表示单链表的头
2.每添加一个节点, 直接加到链表的最后
3.删除节点, 需要先找到要删除节点的前一个节点temp, 然后temp.next=temp.next.next即可, 被删除的节点, 没有引用指向它， 会贝垃圾回收机制回收
3.怎么遍历链表? 通过一个辅助变量, 帮助遍历整个链表
/**
* 节点
*/
class HeroNode{
public int no;//英雄排名
public String name;//姓名
public String nickname;//昵称
public HeroNode next; //指向下一个节点
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
/**
* 链表
*/
class SingleLinkedList{
//定义一个头节点
private HeroNode head = new HeroNode(0, "", "");
/**
* 添加节点
* 思路:
* 1. 定义一个辅助变量, 遍历链表到链表的尾部, 让辅助变量指向链表的尾部节点
* 2. 添加节点到链表的尾部的next
* @param heroNode
*/
public void add(HeroNode heroNode){
//定义一个辅助节点
HeroNode temp = head;
//从head开始遍历列表, 一直到链表的尾部
while (true){
if(temp.next == null){
break;
}
temp = temp.next; //temp后移
}
//这时temp就指向了链表的最后
temp.next = heroNode;
}
/**
* 根据编号来修改节点的信息
* 思路:
* 1. 定义一个辅助变量, 遍历链表找到要更新的节点, 让辅助变量指向要更新的节点
* 2. 找到就更新
* @param heroNode
*/
public void update(HeroNode heroNode){
//1. 判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//2. 找到要修改的节点
//2.1 定义一个辅助变量
HeroNode temp = head;
boolean flag = false; //标记下面循环中节点是否找到, 找到设为true
while (true){
if(temp == null){
break; //链表已经遍历到尾部
}
if(temp.no == heroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.println("没有找到");
}
}
/**
* 删除节点
* 思路:
* 1. 定义一个辅助节点变量, 遍历链表, 让辅助变量指向我们要删除的节点的上一个节点
* 2. 然后temp.next = temp.next.next删除节点
* @param no
*/
public void del(int no){
HeroNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){//遍历完毕, 没有找到
return;
}
if(temp.next.no == no){//找到
flag = true;
break;
}
temp = temp.next; // 后移
}
if(flag){
temp.next = temp.next.next;
}else{
System.out.println("没有找到要删除的节点");
}
}
/**
* 遍历链表
*/
public void list(){
if(head.next == null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (true){
if (temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
public class SingleLinkedDemo {
public static void main(String[] args) {
//1. 创建节点
HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode heroNode3 = new HeroNode(3, "吴用", "智多");
HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
//2. 创建链表并添加节点
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(heroNode1);
singleLinkedList.add(heroNode2);
singleLinkedList.add(heroNode3);
singleLinkedList.add(heroNode4);
//3. 更新节点
singleLinkedList.update(new HeroNode(3, "吴用", "智多星"));
//4. 删除节点
singleLinkedList.del(2);
//5.遍历节点
singleLinkedList.list();
}
}
- 常见单链表面试题(代码实现就不写了)
- 求单链表有效节点的个数
思路分析: 定义一个变量count，然后遍历链表, 每遍历一个就count++。 - 求单链表中倒数第k个节点(新浪面试题)
思路分析: 先遍历链表, 得到链表的总长度length，然后再遍历链表, 获取链表的第(length-k)个节点, 就是我们要的节点。 - 单链表反转(腾讯面试题)
思路分析: 先创建一个新的链表，遍历原来的链表, 每遍历到一个就放到新的链表的最前面。 - 从尾到头打印单链表(百度面试题, 要求方式, 1:反向遍历; 2: Stack栈的方式)
思路1: 先反转链表，然后遍历即可。
思路2: 利用栈的数据结构, 将各个节点压入到栈中, 然后利用栈的先进先出的特点, 实现逆序打印的效果。
栈的基本使用(参考)
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
//入栈
stack.add("zhangsan");
stack.add("lisi");
stack.add("王五");
//出栈
while (stack.size() > 0){
System.out.println(stack.pop());
}
}
双向链表
- 单向链表和双向链表的对比
1.单向链表, 只能查找一个方向, 双向链表可以向前或向后查找
2.单项链表不能自我删除, 需要依靠辅助节点, 双向链表可以自我删除 - 实际应用
需求:使用带头双向链表实现水浒英雄排行榜管理, 并对英雄任务进行增删改查。
思路分析:
1.遍历节点, 既可以向前, 也可以向后
2.添加节点, 先找到双向链表的最后这个节点, 最后节点的next指向要添加的新节点, 新节点的pre指向最后节点
3.修改节点, 遍历链表, 找到就修改该节点
4.删除节点, 可以自我删除, 加入要删除的节点是temp, 则temp.pre.next=temp.next; temp.next.pre = temp.pre既可实现自我删除
/**
* 节点
*/
class HeroNode{
public int no;//英雄排名
public String name;//姓名
public String nickname;//昵称
public HeroNode next; //指向下一个节点
public HeroNode pre; //指向上一个节点
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
class DoubleLinkedList{
// 定义一个头节点, 不存放任何数据, 也不要移动
private HeroNode head = new HeroNode(0, "", "");
/**
* 获取头节点
* @return
*/
public HeroNode getHead(){
return head;
}
/**
* 遍历
*/
public void list(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//定义一个辅助变量
HeroNode temp = head.next;
while (true){
if(temp == null){
break;
}
System.out.println(temp);
temp = temp.next; //辅助变量后移
}
}
/**
* 添加一个节点
* @param heroNode
*/
public void add(HeroNode heroNode){
HeroNode temp = head;
while (true){
//链表的尾部
if(temp.next == null){
break;
}
temp = temp.next;
}
//形成一个双向链表
temp.next = heroNode;
heroNode.pre = temp;
}
/**
* 更新节点
* @param heroNode
*/
public void update(HeroNode heroNode){
if(head.next == null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
boolean flag = false; //标记节点是否找到
while (true){
if(temp == null){
break;
}
if(temp.no == heroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.println("没有找到");
}
}
/**
* 删除节点
* @param no
*/
public void del(int no){
if(head.next == null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
boolean flag = false; //标记节点是否找到
while (true){
if(temp == null){
break;
}
if(temp.no == no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.pre.next = temp.next;
//这个地方需要判断一下, 是不是最后一个节点
if(temp.next != null){
temp.next.pre = temp.pre;
}
}else {
System.out.println("没有找到");
}
}
}
环形链表
- 约瑟夫问题
编号为1,2...n的n个人围成一个圈，从编号为k（0<=k<=n）的人从1开始报数，数到m的那个人出列，下一位重新从1开始报数，数到m的那个人出列，依次类推，直到所有人出列为止，由此产生一个编号的序列。
思路分析:
先创建一个有n个节点的单循环链表，然后由k节点从1开始计数，到m时，把对应的节点从链表中删除，然后从删除的节点的下一个节点开始从1开始计数，知道最后一个节点从链表中删除。
class Boy{
//编号
private int no;
//指向下一个节点
private Boy next;
public Boy(int no) {
this.no = no;
}
//省略getter、setter方法
}
class CircleSingleLinkedList{
//创建一个first节点, 没有编号
private Boy first = null;
//创建链表
public void createBoyLinkedList(int nums){
if(nums < 1){
System.out.println("nums is error");
return;
}
Boy curBoy = null; //辅助指针
for(int i=1; i<=nums; i++){
//根据编号创建小孩
Boy boy = new Boy(i);
if(i==1){
first = boy;
first.setNext(first);
curBoy = first;
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
/**
* 遍历链表
*/
public void showBoys(){
if(first == null){
System.out.println("空链");
return;
}
Boy curBoy = first;
while (true){
System.out.println("编号: "+curBoy.getNo());
if(curBoy.getNext() == first){
break;
}
curBoy = curBoy.getNext(); //后移
}
}
/**
* 计算小孩出圈顺序
* @param k 第几个小孩开始
* @param m 数几下
* @param nums 有多少个小孩在圈里
*/
public void countBoy(int k, int m, int nums){
if(first == null || k<1 || k>nums || m<1){
System.out.println("数据有误");
return;
}
Boy helper = first; //辅助指针
//1.辅助变量指向链表的最后这个节点
while (true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();
}
//2.让first和helper移动k-1次
for(int i=0; i<k-1; i++){
first = first.getNext();
helper = helper.getNext();
}
//3.开始报数, first和helper同时移动m-1次, 然后出圈
while (true){
//只有最后一个小孩
if(helper == first){
break;
}
//让first和helper指针同时移动m-1次
for(int j=0; j<m-1; j++){
first = first.getNext();
helper = helper.getNext();
}
System.out.println(first.getNo());
//这个时候first指向的小孩就是要出圈的小孩
first = first.getNext();
helper.setNext(first);
}
System.out.println(first.getNo());
}
}
# 测试
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.createBoyLinkedList(100);
//circleSingleLinkedList.showBoys();
circleSingleLinkedList.countBoy(10, 20, 100);
}
