链表介绍(linked list)
链表是有序的列表，但它在内存中是如下存储的：
1.png
小结：
- 链表是以节点的方式来存储，是链式存储
- 每个节点包含data域，next域：指向下一个节点.
- 如图：发现链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单链表(带头节点)逻辑结构如下：
2.png
单链表应用实例
使用带head头的单向链表实现-水浒英雄排行榜管理，完成对英雄人物的增删改查操作.
- 第一种方法在添加英雄时，直接添加到链表的尾部
3.png
- 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
4.png
-
修改节点功能
修改节点信息，根据no来修改，即no不能改 temp是要修改的节点
-
删除节点功能
删除节点，根据no来删除 temp是要删除节点的前一个节点
5.png
- 代码实现：
package com.atguigu.linkedlist;
import java.util.Stack;
public class SingleLinkedListDemo {
public static void main(String[] args) {
// 先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
HeroNode hero5 = new HeroNode(5, "李逵", "黑旋风");
// 创建一个单链表
// SingleLinkedList singleLinkedList = new SingleLinkedList();
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
// 按照编号顺序添加
// singleLinkedList.addByOrder(hero1);
// singleLinkedList.addByOrder(hero4);
// singleLinkedList.addByOrder(hero3);
// singleLinkedList.addByOrder(hero2);
// singleLinkedList.addByOrder(hero5);
// 修改节点信息
// singleLinkedList.update(2, "小卢", "小麒麟");
// 删除节点
// singleLinkedList.delete(1);
// singleLinkedList.delete(5);
// singleLinkedList.show();
// 单链表的大小
// System.out.println(singleLinkedList.size());
// 查找单链表中倒数第k个节点
// System.out.println(singleLinkedList.findNode(1));
// System.out.println(singleLinkedList.findNode(3));
// System.out.println(singleLinkedList.findNode(5));
// 反向遍历
// singleLinkedList.lastToFirst();
// 单链表的反转
// singleLinkedList.reverse();
// 合并两个有序链表
SingleLinkedList singleLinkedList1 = new SingleLinkedList();
singleLinkedList1.addByOrder(hero1);
singleLinkedList1.addByOrder(hero3);
singleLinkedList1.addByOrder(hero5);
SingleLinkedList singleLinkedList2 = new SingleLinkedList();
singleLinkedList2.addByOrder(hero2);
singleLinkedList2.addByOrder(hero4);
merge(singleLinkedList1, singleLinkedList2).show();
}
/**
* 单链表的反转，原理是头插法
*
* @param singleLinkedList
*/
public static void reverse(SingleLinkedList s) {
// 如果当前链表为空，或者只有一个节点，无需反转，直接返回
if (s.head.next == null || s.head.next.next == null) {
return;
}
HeroNode cur = s.head.next;
HeroNode next = null;// 指向当前节点[cur]的下一个节点
HeroNode newHead = new HeroNode();
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表newHead的最前端
while (cur != null) {
next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
cur.next = newHead.next;// 将cur放在新链表的最前端
newHead.next = cur;
cur = next;// cur后移
}
// 将head.next指向newHead.next，实现单链表的反转
s.head.next = newHead.next;
}
/**
* 从尾到头打印单链表，利用栈
*
* @param s
*/
public static void lastToFirst(SingleLinkedList s) {
if (s.head.next == null) {// 空链表
return;
}
// 创建一个栈，将各个节点压入栈
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = s.head.next;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 出栈
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
/**
* 合并两个有序的单链表，合并之后的链表依然有序，原理是尾插法
*
* @param s1 有序链表1
* @param s2 有序链表2
*/
public static SingleLinkedList merge(SingleLinkedList s1, SingleLinkedList s2) {
SingleLinkedList newSingleLinkedList = new SingleLinkedList();
HeroNode tail = newSingleLinkedList.head;// 链表尾
HeroNode cur1 = s1.head.next, cur2 = s2.head.next;
// 当cur1与cur2同时都有值时才继续移动，一旦有一段为空了，说明另一段剩下的都比它大，直接接到新list上就可以了，减少循环浪费
while (cur1 != null && cur2 != null) {
if (cur1.no < cur2.no) { // 将cur1节点插入到newHead链表的尾部
tail.next = cur1;
cur1 = cur1.next;
} else { // 将cur2节点插入到newHead链表的尾部
tail.next = cur2;
cur2 = cur2.next;
}
tail = tail.next;// 移动tail，指向最后一个节点
}
// 上述循环结束后，一定有cur1或者cur2是空的，那么判断并将另一段直接接入到tail后边
if (cur1 == null) {
tail.next = cur2;
}
if (cur2 == null) {
tail.next = cur1;
}
return newSingleLinkedList;
}
}
//定义SingleLinkedList，管理链表
class SingleLinkedList {
// 先初始化一个头节点，头节点不要动，不存放具体的数据
public HeroNode head = new HeroNode();
/**
* 添加节点，当不考虑编号顺序时：
* <p>
* 1.找到当前链表的最后节点 2.将最后节点的next指向新节点
*
* @param heroNode 新节点
*/
public void add(HeroNode heroNode) {
// 1.找到当前链表的最后节点
HeroNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
// 此时temp是链表最后一个节点，将其next指向新节点
cur.next = heroNode;
}
/**
* 按照编号顺序添加，如果编号已存在，则添加失败，并给出提示
*
* @param heroNode 新节点
*/
public void addByOrder(HeroNode heroNode) {
HeroNode cur = head;
while (cur.next != null) {
if (cur.next.no > heroNode.no) {
// 此时新节点的位置就是temp的后面
heroNode.next = cur.next;
cur.next = heroNode;
return;
}
if (cur.next.no == heroNode.no) {
System.out.println("编号" + heroNode.no + "已存在");
return;
}
// 一定要记住temp后移
cur = cur.next;
}
// 如果temp是最后节点，还没有return，则新节点插入到最后
cur.next = heroNode;
}
/**
* 修改节点信息，根据no来修改，即no不能改 cur是要修改的节点
*
* @param no 编号
* @param name 新name
* @param nickname 新nickname
*/
public void update(int no, String name, String nickname) {
HeroNode cur = head.next;
while (cur != null) {
if (cur.no == no) {
cur.name = name;
cur.nickname = nickname;
return;
}
cur = cur.next;
}
System.out.println("没有找到编号为" + no + "的节点");
}
/**
* 删除节点，根据no来删除 cur是要删除节点的前一个节点
*
* @param no 编号
*/
public void delete(int no) {
HeroNode cur = head;
while (cur.next != null) {
if (cur.next.no == no) {
// 将要删除的节点的前一个节点指向要删除节点的后一个节点
cur.next = cur.next.next;
return;
}
cur = cur.next;
}
System.out.println("没有找到编号为" + no + "的节点");
}
// 显示链表，遍历
public void show() {
if (head.next == null) {
System.out.println("链表为空");
} else {
HeroNode cur = head.next;
while (cur != null) {
System.out.println(cur);
cur = cur.next;
}
}
}
/**
* 求单链表中有效节点的个数，不统计头节点
*
* @return
*/
public int size() {
HeroNode cur = head.next;
int sum = 0;
while (cur != null) {
sum++;
cur = cur.next;
}
return sum;
}
/**
* 查找单链表中倒数第k个节点，并返回
*
* @param k 倒数
* @return
*/
public HeroNode findLastKNode(int k) {
int count = size() + 1;
HeroNode cur = head.next;
while (cur != null) {
// 每找到一个节点，count--，如果count=k，则即为倒数第k个节点
if (--count == k) {
return cur;
}
cur = cur.next;
}
return null;
}
}
//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
int no;
String name;
String nickname;
HeroNode next;// 指向下一个节点
public HeroNode() {
}
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 + "]";
}
}
