JAVA数据结构———链表

单链表 ：

import java.util.Stack;

public class SingleLinkListDemo {

    public static void main(String[] args) {

        HerNode a = new HerNode(1,"333","333");

        HerNode b = new HerNode(2,"333","333");

        HerNode c = new HerNode(3,"333","333");

        HerNode d=  new HerNode(2,"222","222");

        SingleList singleList = new SingleList();

        singleList.orderByAdd(a);

//        singleList.orderByAdd(d);

        singleList.orderByAdd(c);

        singleList.orderByAdd(b);

        System.out.println("原始链表");

        singleList.list();

//        System.out.println("逆向打印链表");
//        SingleList.reversPln(singleList.getHead());

//        System.out.println("反转后的链表");
//
//        singleList.revers(singleList.getHead());
//        singleList.list();

        singleList.update(d);

        System.out.println("修改后的链表");

        singleList.list();
//
//        System.out.println("删除后的链表！");
//        singleList.delete(2);
//        singleList.list();


    }
}

class SingleList{

  private final HerNode head =new HerNode();

    public HerNode getHead() {
        return head;
    }

    //添加
    public  void  add(HerNode herNode){
        HerNode temp = head;

        while (temp.next != null) {

            temp = temp.next;
        }

        temp.next=herNode;
    }

    public void  orderByAdd(HerNode herNode){

//        HerNode current = head.next;
//        HerNode prev = head;
//        boolean res= false;
//
//        if(current!=null){
//            while(current!=null){
//                if(current.getNo()>herNode.getNo()){
//                    herNode.next = current;
//                    prev.next = herNode;
//                    break;
//                }
//                if(current.getNo()<herNode.getNo()){
//                    if(current.next==null){
//                        current.next = herNode;
//                        break;
//                    }
//                    prev = current;
//                    current = current.next;
//                }
//            }
//        }else{
//            prev.next = herNode;
//        }

        HerNode temp = head;
        boolean res=false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.getNo()>herNode.getNo()){
                break;
            }else if (temp.next.getNo()==herNode.getNo()){
                res=true;
                break;
            }
            temp=temp.next;
        }

        if (res){
            System.out.println("需要插入的数据已存在，不能插入数据！");
        }
        else {
            herNode.next=temp.next;
            temp.next=herNode;
        }

    }
//反转链表
    public  void  revers(HerNode head){
        if (head.next==null || head.next.next==null){
            return;
        }
        HerNode cur = head.next;
        HerNode rev = new HerNode();
        HerNode next = null;

        while (cur!=null){
            next = cur.next;
            cur.next=rev.next;
            rev.next=cur;
            cur=next;

        }
        head.next = rev.next;
    }
    //逆向打印
    public static void  reversPln(HerNode head){
        if (head.next==null)return;
        HerNode cur = head.next;
        Stack<HerNode> stack = new Stack<HerNode>();
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }

    //修改
    public  void  update(HerNode herNode){

        if (head.next==null) {
            System.out.println("链表为空！");
            return;
        }

        HerNode temp = head.next;

        boolean res = false;

        while (temp != null) {

            if (temp.getNo()==herNode.getNo()){
                    res=true;
                    break;
                }

            temp = temp.next;

        }

        if (res){
            temp.setName(herNode.getName());
            temp.setnName(herNode.getnName());
        }
    }

    //删除
    public  void  delete(int no){
        if (head.next==null) {
            System.out.println("链表为空！");
            return;
        }

        HerNode temp = head;

        boolean res = false;

        while (temp.next != null) {

            if (temp.next.getNo()==no){
                res=true;
                break;
            }

            temp = temp.next;

        }

        if (res){
            temp.next=temp.next.next;
        }
    }
    //链表显示
    public void  list(){

        if (head.next==null){
            System.out.println("链表为空！");
         return;
        }

        HerNode temp = head;

        while (temp.next != null) {

            temp = temp.next;

            System.out.println(temp);
        }

    }
}
class  HerNode{
    private int no;
    private String name;
    private String nName;
    public HerNode next;

    public HerNode() {

    }

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getnName() {
        return nName;
    }

    public void setnName(String nName) {
        this.nName = nName;
    }

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

双向链表：

public class DoubleSingListDemo {
    public static void main(String[] args) {
        HerNode2  a = new HerNode2(1,"222","2222");
        HerNode2  b = new HerNode2(2,"222","2222");
        HerNode2  c = new HerNode2(3,"222","2222");
        HerNode2  d = new HerNode2(4,"222","2222");

        DoubleSingList doubleSingList = new DoubleSingList();
        doubleSingList.add(a);
        doubleSingList.add(b);
        doubleSingList.add(c);
        doubleSingList.add(d);
        System.out.println("原始链表~~");
        doubleSingList.list();

//        System.out.println("修改后的链表~~");
//        HerNode2 e = new HerNode2(4,"555","2222");
//        doubleSingList.update(e);
//        doubleSingList.list();

        System.out.println("删除后的链表~~");
        doubleSingList.delete(2);
        doubleSingList.list();
    }
}
class DoubleSingList{
   private  HerNode2 head = new HerNode2();

    public HerNode2 getHead() {
        return head;
    }

    //添加
    public  void  add(HerNode2 herNode2){
        HerNode2 temp = head;
        while (temp.next!=null){
            temp=temp.next;
        }
        temp.next=herNode2;
        herNode2.per=temp;
    }
    //修改
    public  void  update(HerNode2 herNode2){
        HerNode2 temp = head.next;
        boolean res = false;
        if (temp==null){
            System.out.println("链表为空，不能修改！");
            return ;
        }
        while (temp != null){
            if (temp.getNo()==herNode2.getNo()){
                res=true;
                break;
            }
            temp=temp.next;
        }
        if (res){
            temp.setName(herNode2.getName());
            temp.setnName(herNode2.getnName());
        }
    }

    public  void  delete(int no){
        HerNode2 temp = head.next;
        boolean res = false;
        if (temp==null){
            System.out.println("链表为空,不能删除");
            return;
        }
        while (temp!=null){
            if (temp.getNo()==no){
                res=true;
                break;
            }
            temp=temp.next;
        }
        if (res){
            temp.per.next=temp.next;
            if (temp.next!=null){
                temp.next.per=temp.per;
            }
        }else {
            System.out.println("所需删除的数据不存在~~");
        }
    }
    public  void  list(){
        HerNode2 temp = head.next;
        if (temp==null){
            System.out.println("链表为空~~");
            return;
        }
        while (temp!=null){
            System.out.println(temp);
            temp=temp.next;
        }
    }
}

class  HerNode2{
    private  int no;
    private  String name;
    private  String nName;
    public HerNode2 next;
    public HerNode2 per;

    public HerNode2() {
    }

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getnName() {
        return nName;
    }

    public void setnName(String nName) {
        this.nName = nName;
    }

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

环形链表在约瑟夫问题中呈现