一 定义
链表是有序的列表，但是它在内存中是存储如下：
image.png
小结:
- 链表是以
节点的方式来存储,是链式存储 - 每个节点包含
data 域，next 域：指向下一个节点. - 如图：发现链表的各个节点
不一定是连续存储. - 链表分
带头节点的链表和没有头节点的链表，根据实际的需求来确定
逻辑结构
image.png
二 单向链表-水浒英雄排名
需求
使用带head头的单向链表实现 –水浒英雄排行榜管理
- 完成对英雄人物的增删改查操作
- 第一种方法在添加英雄时，直接添加到链表的尾部
- 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
head头
- 不存放具体的数据
- 指向第一个节点
思路分析
- 添加到末尾没什么好说的
- 按排名顺序添加。我们在添加时队列就是
升序的，我们只要找到第一个比当前插入节点大的节点，插到它前面即可
代码
链表
public class SingleLinkedList {
private HeroNode head = new HeroNode();//头节点，指向第一个节点
private HeroNode last = null;//尾节点，就是最后一个节点
private int length;
/**
* 增加到最后
* @param node
*/
public void add(HeroNode node){
if(head.getNext() ==null){
head.setNext(node);
last = node;
}else{
last.setNext(node);
last = node;
}
}
public void show(){
HeroNode next = head.getNext();
while(next != null){
System.out.println(next);
next = next.getNext();
}
}
public void addByNoAsc(HeroNode node){
if(head.getNext() ==null){
head.setNext(node);
last = node;
}else{
HeroNode preNode = head;//头元素
HeroNode next = head.getNext();//第一个元素
while(next != null){
if(next.getNo() == node.getNo()){
throw new RuntimeException("no异常");
}else if(next.getNo() > node.getNo()){
//结束,插前面
node.setNext(next);
preNode.setNext(node);
return;
}else{
//继续往下找
preNode = next;
next = next.getNext();
continue;
}
}
//上面遍历完了还没找到比当前节点大的，就插入到最后
last.setNext(node);
last = node;
}
}
}
节点
class HeroNode{
private String name;
private String nickname;
private int no;
private HeroNode next;
public HeroNode() {
}
public HeroNode(int no, String name, String nickname) {
this.name = name;
this.nickname = nickname;
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getNickname() {
return nickname;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public HeroNode getNext() {
return next;
}
public void setNext(HeroNode next) {
this.next = next;
}
@Override
public String toString() {
return "HeroNode{" +
"name='" + name + '\'' +
", nickname='" + nickname + '\'' +
", no=" + no +
'}';
}
}
测试
@Test
public void testSingleLinkedList1(){
HeroNode node1 = new HeroNode(1,"宋江","呼保义");
HeroNode node7 = new HeroNode(7,"秦明"," 霹雳火");
HeroNode node4 = new HeroNode(4,"公孙胜","入云龙");
HeroNode node3 = new HeroNode(3,"吴用","智多星");
HeroNode node2 = new HeroNode(2,"卢俊义"," 玉麒麟");
HeroNode node5 = new HeroNode(5,"关胜"," 大刀");
HeroNode node6 = new HeroNode(6,"林冲"," 豹子头");
HeroNode node8 = new HeroNode(8,"呼延灼"," 双鞭");
SingleLinkedList list = new SingleLinkedList();
list.addByNoAsc(node1);
list.add(node7);
list.addByNoAsc(node5);
list.addByNoAsc(node2);
list.addByNoAsc(node3);
list.add(node8);
list.addByNoAsc(node6);
list.addByNoAsc(node4);
list.show();
}
单链表反转
反转就是遍历原始链表时采用头插法
public void reverse(){
if(last == null){
return;
}
HeroNode newHead = new HeroNode();
HeroNode oldFirstHead;
HeroNode next;
/*
开始遍历
*/
HeroNode cur = head.getNext();//第一个元素
while(cur != null){
next = cur.getNext();
if(newHead.getNext()==null){
newHead.setNext(cur);
last = cur;
cur.setNext(null);
}else{
oldFirstHead = newHead.getNext();///指向原来的第一个元素
newHead.setNext(cur);
cur.setNext(oldFirstHead);
}
cur = next;
}
head = newHead;
}
合并两个有序的单链表
可以直接调用addByNoAsc的：缺点每次都从头开始比（其实前面比过的已经不需要再比了）.所以新写了方法
代码
public HeroNode get(){
if(head.getNext() == null){
return null;
}else{
HeroNode temp = head.getNext();
head.setNext(temp.getNext());
temp.setNext(null);
return temp;
}
}
/**
* 有序合并
* @param list
*/
public void mergeByAsc(SingleLinkedList list){
HeroNode node = list.get();
HeroNode cur = head.getNext();
HeroNode pre = head;
while(node != null){
/**
* 一样的道理
* 在原始链表中找到比自己大的
* 直接调用addByNoAsc的：缺点每次都从头开始比
*/
if(cur == null){
if(head.getNext() == null){
head.setNext(node);
}else{
last.setNext(node);//先指向
}
/**
* 结束了，后面都好了(因为node已经清掉了next，所以还需要处理)
*/
last = node;//后调整last
node = list.get();
}else{
while(cur != null){
if(cur.getNo() >= node.getNo()){//找到位置
pre.setNext(node);
node.setNext(cur);
pre= node;
node = list.get();
break;//下一个node
}else{//继续找
pre = cur;
cur = cur.getNext();
}
}
//找完了
}
}
}
测试
@Test
public void testSingleLinkedList1(){
HeroNode node1 = new HeroNode(1,"宋江","呼保义");
HeroNode node11 = new HeroNode(1,"宋江","呼保义（神）");
HeroNode node7 = new HeroNode(7,"秦明"," 霹雳火");
HeroNode node4 = new HeroNode(4,"公孙胜","入云龙");
HeroNode node3 = new HeroNode(3,"吴用","智多星");
HeroNode node31 = new HeroNode(3,"吴用","智多星（神）");
HeroNode node2 = new HeroNode(2,"卢俊义"," 玉麒麟");
HeroNode node5 = new HeroNode(5,"关胜"," 大刀");
HeroNode node6 = new HeroNode(6,"林冲"," 豹子头");
HeroNode node8 = new HeroNode(8,"呼延灼"," 双鞭");
HeroNode node9 = new HeroNode(9,"花荣"," 小李广");
SingleLinkedList list = new SingleLinkedList();
SingleLinkedList list2 = new SingleLinkedList();
// list.addByNoAsc(node1);
// list.addByNoAsc(node7);
// list.addByNoAsc(node5);
// list.addByNoAsc(node3);
list2.addByNoAsc(node8);
list2.addByNoAsc(node2);
list2.addByNoAsc(node6);
list2.addByNoAsc(node4);
list2.addByNoAsc(node31);
list2.addByNoAsc(node11);
list2.addByNoAsc(node9);
list.show();
System.out.println("---------");
list2.show();
System.out.println("---------");
list.mergeByAsc(list2);
list.show();
}
三 双向链表
- 单向链表，查找的方向
只能是一个方向，而双向链�表可以向前或者向后查找。 - 单向链表
不能自我删除，需要靠辅助节点 ，而双向�链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点
image.png
本质没上面区别，就不行写了，只是加了个pre属性。指向前一个元素
四 单向环形链表（约瑟夫）
Josephu 问题为： 设编号为 1， 2， … n 的 n 个人围坐一圈， 约定编号为 k（1<=k<=n） 的人从 1 开始报数， 数
到m的那个人出列， 它的下一位又从 1开始报数， 数到 m 的那个人又出列， 依次类推， 直到所有人出列为止， 由
此产生一个出队编号的序列
思路分析
用一个不带头结点的循环链表来处理 Josephu 问题： 先构成一个有 n 个结点的单循环链表， 然后由k 结 点起从 1 开始计数， 计到m 时， 对应结点从链表中删除， 然后再从被删除结点的下一个结点又从 1 开始计数， 直
到最后一个结点从链表中删除算法结束。
代码实现
public void sequence(int n,int k,int m){
//TODO: 参数校验省略...
Node first = null;//
Node head = null;//初始化时，指向node1
Node pre = null;//前一次初始化的节点
//初始化
for(int i= 1;i<=n;i++){
Node node = new Node(i);
if(i == 1){
head = node;
pre = node;
}else if(i == n){
pre.setNext(node);
node.setPre(pre);
node.setNext(head);
head.setPre(node);
}else{
pre.setNext(node);
node.setPre(pre);
pre = node;
}
if(i == k){
first = node;
}
}
/**
* 开始依次出队
*/
int index = 1;
while(first != null){
if(index == m){
//出队
System.out.println(first);
Node preNode = first.getPre();
if(preNode == first)//自己连自己
return;//最后一个元素了，结束了
first = first.getNext();
preNode.setNext(first);
first.setPre(preNode);
index = 1;//重置
}else{
first = first.getNext();
index++;
}
}
}
测试
@Test
public void test(){
sequence(5,2,3);
}
