单链表

1、链表介绍

链表是有序的列表，在内存中的存储结构：

小结:
1)链表是以节点的方式来存储,是链式存储
2)每个节点包含 data 域， next 域：指向下一个节点
3)如图：发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定逻辑结构图：

2、单链表的创建，插入，删除，显示

package linkedlist;

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 创建节点
		HeroNode hero1 = new HeroNode(1000, "wd");
		HeroNode hero2 = new HeroNode(1001, "lz");
		HeroNode hero3 = new HeroNode(1002, "lp");
		// 创建链表
		SingleLinkedList heroList = new SingleLinkedList();
		// 添加节点
//		heroList.add(hero1);
//		heroList.add(hero3);
//		heroList.add(hero2);

		heroList.addByOrder(hero3);
		heroList.addByOrder(hero2);
		heroList.addByOrder(hero1);

		// 修改
		HeroNode hero4 = new HeroNode(1002, "ljb");
		heroList.update(hero4);
		
		// 删除
		heroList.delete(1000);
		// 显示
		heroList.list();
	}
}

// 定义HeroNode ,每一个HeroNode 对象就是一个节点
class HeroNode {
	public int id;
	public String name;
	public HeroNode next;// 指向下一个节点

	public HeroNode() {
		super();
	}

	public HeroNode(int id, String name) {
		this.id = id;
		this.name = name;
	}

	@Override
	public String toString() {
		return "HeroNode [id=" + id + ", name=" + name + "]";
	}
}

// 定义SingleLinkedList
class SingleLinkedList {
	// 初始化头节点 不存放具体的数据 表示单链表的头
	private HeroNode head = new HeroNode();

	// 添加节点到单链表
	public void add(HeroNode heroNode) {
		// head节点不能动，需要创建一个临时节点
		HeroNode temp = head;
		// 1.找到当前链表的最后一个节点
		while (true) {
			if (temp.next == null) {
				break;
			}
			// 如果没有找到，将temp后移
			temp = temp.next;
		}
		// 当退出while循环时，temp就指向了链表的最后
		// 2.将最后的这个节点指向新的节点
		temp.next = heroNode;
	}

	// 显示当前链表
	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 = temp.next;
		}
	}

	// 根据排名添加节点到指定位置
	public void addByOrder(HeroNode heroNode) {
		// 1.找到要添加节点的前一个节点
		HeroNode temp = head;
		boolean flag = false; // 标识添加的编号是否 存在
		while (true) {
			if (temp.next == null) {
				break;
			}
			if (temp.next.id > heroNode.id) {
				// 位置找到 就在temp 与 temp.next 之间
				break;
			} else if (temp.next.id == heroNode.id) {
				// 要插入的节点的编号已经存在
				flag = true;
				break;
			}
			// 后移
			temp = temp.next;
		}
		// 判断flag的值
		if (flag) {
			System.out.printf("准备插入的英雄的编号%d已经存在，不能添加！", heroNode.id);
		} else {
			// 2.插入到链表中 
			heroNode.next = temp.next;// 插入节点的next指向原有节点的下一个节点
			temp.next = heroNode;// 原有节点的next指向插入节点
		}
	}

	// 根据编号修改节点信息
	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.id == heroNode.id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.name = heroNode.name;
		} else {
			System.out.printf("没有找到编号为%d的节点！", heroNode.id);
		}
	}

    // 根据编号删除节点信息
	public void delete(int id) {
		if (head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		HeroNode temp = head;
		boolean flag = false;
		while(true) {
			// 1.找到待删除节点的前一个节点
			if(temp.next == null) {
				break;
			}
			if(temp.next.id == id) {
				flag =true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			// 2.使原有节点的next指向  待删除节点(temp.next)  的下一个节点
			temp.next = temp.next.next;
		}else {
			System.out.printf("没有找到编号为%d的节点",id);
		}
	}
}

3、求单链表有效节点个数

public int getLength(HeroNode head) {
	if (head.next == null) {
		return 0;
	}
	int length = 0;
	HeroNode cur = head.next;
	while (cur != null) {
		length++;
		cur = cur.next;
	}
	return length;
}

4、查找倒数第 k 个节点

public HeroNode findLastIndexNode(HeroNode head, int index) {
	// 判断链表是否为空
	if (head.next == null) {
		return null;
	}
	// 获取链表长度
	int length = this.getLength(head);
	// 验证 index 是否合法
	if(index<=0||index>length) {
		return null;
	}
	// for循环定位到倒数第 index 个节点
	HeroNode cur = head.next;
	for (int i = 0; i < length-index; i++) {
		cur = cur.next;
	}
	return cur;
}

5、单链表的反转

public void reverseList(HeroNode head) {
		if (head.next == null || head.next.next == null) {
			System.out.println("链表为空或长度为 1！");
			return;
		}
		HeroNode cur = head.next;
		HeroNode next = null;// 指向当前节点的下一个节点
		HeroNode reverseHead = new HeroNode();
		// 遍历原来的链表
		while (cur != null) {
			next = cur.next;// 先暂时保存当前节点的下一个节点
			cur.next = reverseHead.next;// 使当前节点指向新链表的第一个节点
			reverseHead.next = cur;// 使 新链表的头节点指向当前节点
			cur = next;// 当前节点后移
		}
		
		// 将新链表的第一个节点连接到原来链表的头节点上
		head.next = reverseHead.next;
	}

6、逆序打印单链表

public void reversePrint(HeroNode head) {
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		// 创建一个栈
		Stack<HeroNode> stack = new Stack<HeroNode>();
		// 创建一个指针用于遍历
		HeroNode cur = head.next;
		// 遍历单链表
		while(cur != null) {
			stack.push(cur);// 将遍历的节点入栈
			cur = cur.next;// 后移
		}
		while(stack.size()>0) {
			System.out.println(stack.pop());
		}
}