[数据结构与算法]数据结构之双向链表与单向环形链表

双向链表

双向链表数据结构

class Node {

    public int no;
    public String name;
    public String nickname;
    public Node next;  // 指向后一个节点的指针
    public Node pre;   // 指向前一个节点的指针

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

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

双向链表的操作

1. 双向链表的遍历（同单向链表遍历一样）

   // 遍历双向链表
   public void list() {
       if (head.next == null) {
           System.out.println("链表为空");
           return;
       }
   
       Node temp = head.next;
       while (temp != null) {
           System.out.println(temp);
           temp = temp.next;
       }
   }
   

2. 向链表中添加元素

   // 向链表中添加元素
   public void add(Node node) {
       Node temp = head;
       while (temp.next != null) {
           temp = temp.next;
       }
   
       temp.next = node;
       node.pre = temp;
   }
   

3. 修改链表中的元素

   // 修改链表 与 单向链表的修改是一样的
   public void updateHero(Node newHero) {
   
       Node temp = head.next;
       if (temp == null) {
           System.out.println("链表为空，没有要修改的元素");
           return ;
       }
       boolean find = false;
       while (temp != null) {
           if (temp.no == newHero.no) {
               find = true;
               break;
           }
           temp = temp.next;
       }
       if (find) {
           temp.name = newHero.name;
           temp.nickname = newHero.nickname;
       } else {
           System.out.printf("没有找到编号为%d的英雄\n", newHero.no);
       }
   }
   

4. 删除链表中的元素

   public void del(int no) {
       Node temp = head.next;
       boolean find = false;
       while (temp != null) {
           if (temp.no == no) {
               // 找到了要删除的节点
               find = true;
               break;
           }
           temp = temp.next;
       }
   
       if (find) {
           temp.pre.next = temp.next;
           if (temp.next != null) { // 这里在判断是否是最后一个节点
               temp.next.pre = temp.pre;
           }
       } else {
           System.out.printf("要删除的节点%d不存在", no);
       }
   }
   

单向环形链表

public class SingleCircleLinkedListDemo {

    public static void main(String[] args) {

        SingleCircleLinkeList singleCircleLinkeList = new SingleCircleLinkeList();

        for(int i = 1; i <= 5; ++i) {
            BoyNode boyNode = new BoyNode(i);
            singleCircleLinkeList.add(boyNode);
        }

        singleCircleLinkeList.countBoy(1, 2, 5);
//        singleCircleLinkeList.show();
//        singleCircleLinkeList.delete(1);
//        System.out.println("删除元素后的单循环链表");
//        singleCircleLinkeList.show();

        System.out.println("循环链表的第一个元素");
        System.out.println(singleCircleLinkeList.getFirst());
        System.out.println("循环链表的最后一个元素");
        System.out.println(singleCircleLinkeList.getLastNode());
    }
}

class SingleCircleLinkeList {

    BoyNode first, lastNode;

    public BoyNode getFirst() {
        return first;
    }

    public BoyNode getLastNode() {
        return lastNode;
    }
    // 向单向循环链表中添加元素
    public void add(BoyNode boyNode) {
        if (first == null) {// 添加第一个元素
            first = boyNode;
            lastNode = boyNode;
            return;
        }
        lastNode.next = boyNode;
        boyNode.next = first;
        lastNode = boyNode;
    }

    /**
     * 约瑟夫环
     * @param startNo  从编号startNo开始数
     * @param seqCn　　数到seqCn的元素，从链表中删除
     * @param allCnt　 链表中总共的元素
     */
    public void countBoy(int startNo, int seqCn, int allCnt) {

        if (first == null || startNo <=0 || startNo > allCnt) {
            System.out.println("队列为空或输入参数有误");
            return;
        }
        // 先将first指针定位到startNo位置
        while (first.no != startNo) {
            first = first.next;
            lastNode = lastNode.next;
        }

        while (true) {
            if (first == lastNode) {
                break;
            }
            for (int i = 1; i <= seqCn -1; ++i) {
                first = first.next;
                lastNode = lastNode.next;
            }
            System.out.printf("出圈的孩子%d\n", first.no);
            first = first.next;   // 删除地seqCn个元素
            lastNode.next = first;
        }
        System.out.printf("出圈的孩子%d\n", first.no);
    }

    public void delete(int no) {
        // 当前链表为空
        if (first == null) {
            System.out.println("当前链表为空");
            return ;
        }
        // 当前链表中只有一个元素
        if (first == lastNode) {
            if (first.no == no) {
                first = null;
                lastNode = null;
            } else {
                System.out.println("要找的节点不存在");
            }
            return ;
        }
        // 链表中的元素多于一个
        BoyNode currNode = first, preCurrNode = lastNode;

        do {
            if (currNode.no == no) {
                preCurrNode.next = currNode.next; 
                if (currNode == first) { // 如果删除的元素是链表中第一元素，要修改first的值
                    first = currNode.next;
                }
                if (currNode == lastNode) { // 要删除的元素是链表中的最后一个元素，要修改last的值
                    lastNode = preCurrNode;
                }
                break;
            }
            currNode = currNode.next;
            preCurrNode = preCurrNode.next;
        }while (currNode != first);
    }

    public void show() {

        if (first == null) {
            System.out.println("当前链表为空");
            return ;
        }

        BoyNode temp = first;
        do {
            System.out.println(temp);
            temp = temp.next;
        } while (temp != first);
    }
}

class BoyNode {

    int no;
    BoyNode next;

    // 每个构建出来的节点，都指向自己
    public BoyNode(int no) {  
        this.no = no;
        this.next = this;
    }

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