概念介绍

链表的结构很简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含2部分，数据域，和一个指向下一个节点引用的指针next,具体的更详细的大家可以参考相关资料解释，再说说删除操作，同样需要找到数据所在的位置，然后进行删除，不同的是，删除的时候，链表只需要改变一下前后节点的引用关系即可，就完成了节点的删除，而没有像数组那样触发一次全部数据的移动，从这个描述来看，链表在进行删除的时候，速度比数组快
链表有很多种形式包括单链表，双向链表，循环链表等，本文主要内容是单向链表。

创建节点类

//链表类，并重写了toString方法
class HeroNode{
   public int no;
   public String name;
   public HeroNode next;

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name +"}";
    }

用一个SingleLinkedList类封来表示链表和封装方法

代码全局

public class SingleLinkedlist {

    //头指针
    public HeroNode head =new HeroNode(0,null);

    //在链表尾部加入新元素
    public void add(HeroNode a){}

    //按序号加入序号重复的不加入
    public void addByorder(HeroNode a) throws Exception{} 

    //遍历链表
    public void list(){}

    //链表反转
    public void rollBack(){}

    //从尾到头打印单链表
    public void BackList(){}

     //合并两个有序的单链表最后成一个新的单链表
    public SingleLinkedlist merge(SingleLinkedlist s){}
    }

在链表尾部加入新元素

//在链表尾部加入新元素
public void add(HeroNode a){
    HeroNode temp=head;
    while(temp.next!=null){
        temp=temp.next;
    }
    temp.next=a;
}

按序号加入序号重复的不加入

public void addByorder(HeroNode a) throws Exception {
        HeroNode temp = head;

        while(temp.next!=null && temp.next.no<a.no){

            temp=temp.next;

        }
        if(temp.next==null){
            temp.next=a;
        }else if(temp.next.no==a.no){
            throw new Exception("数据重复");
        }else{
            a.next=temp.next;
            temp.next=a;
        }
    }

遍历链表

public void list(){
    if(head.next==null){
        return;
    }

    HeroNode temp=head;

    while(temp.next!=null){
        System.out.println(temp.next.toString());
        temp=temp.next;
    }
}

链表反转返还一个新的链表

//链表反转
public void rollBack(){
    HeroNode pnode =head.next;
    HeroNode pprior =null;

    while(pnode!=null) {
        HeroNode pnext = pnode.next;
        if (pnext == null) {
            head.next = pnode;
        }
        pnode.next = pprior;
        pprior = pnode;
        pnode = pnext;
    }
}

从尾到头打印单链表

public void BackList(){
    Stack<HeroNode> s=new Stack<>();
    HeroNode temp= head;
    while(temp.next!=null){
        s.push(temp.next);
        temp=temp.next;
    }
    while(!s.isEmpty()){
        HeroNode hn=s.pop();
        System.out.println(hn.toString());
    }
}

合并两个有序的单链表最后成一个新的有序单链表

public SingleLinkedlist merge(SingleLinkedlist s){
    SingleLinkedlist newone = new SingleLinkedlist();
    HeroNode temp =newone.head;
    HeroNode temp1=head.next;
    HeroNode temp2=s.head.next;
    while(temp1!=null||temp2!=null){
        if(temp1==null){
            temp.next=temp2;
            temp2=temp2.next;
        } else if(temp2==null){
            temp.next=temp1;
            temp1=temp1.next;
        }
        if(temp1!=null&&temp2!=null) {
            if(temp1.no>temp2.no){
                temp.next=temp2;
                temp2=temp2.next;
            }
            else if(temp1.no<temp2.no){
                temp.next=temp1;
                temp1=temp1.next;
            }
            else if(temp1.no==temp2.no){
                temp.next=temp1;
                temp1=temp1.next;
                temp2=temp2.next;
            }
        }
        temp=temp.next;
    }
    return newone;
}

创建main类简单测试

public static void main(String[] args) throws Exception {
    SingleLinkedlist hero =new SingleLinkedlist();
    SingleLinkedlist hero2 =new SingleLinkedlist();
    HeroNode a=new HeroNode(1,"蜘蛛侠");
    HeroNode b=new HeroNode(2,"钢铁侠");
    HeroNode c=new HeroNode(3,"绿巨人");
    HeroNode d=new HeroNode(4,"雷神");
    HeroNode e=new HeroNode(5,"黑寡妇");
    HeroNode f=new HeroNode(6,"美国队长");

    hero.addByorder(a);
    hero.addByorder(c);
    hero2.addByorder(b);
    hero2.addByorder(d);
    hero.addByorder(e);
    hero2.addByorder(f);

    SingleLinkedlist newone=hero.merge(hero2);
    newone.list();

java算法笔记-单链表

概念介绍

创建节点类

用一个SingleLinkedList类封来表示链表和封装方法

创建main类简单测试

测试结果