数据结构与算法-单向链表

数据结构与算法-单向链表

package linkedlist;


public class SinglelinkedListDemo {

    public static void main(String[] args) {
        SinglelinkedList linkedList = new SinglelinkedList();
        Node node1 = new Node(1, "宋江", "及时雨");
        Node node2 = new Node(2, "卢俊义", "玉麒麟");
        Node node3 = new Node(3, "吴用", "智多星");
        Node node4 = new Node(4, "林冲", "豹子头");
//        linkedList.add(node1);
//        linkedList.add(node3);
//        linkedList.add(node4);
//        linkedList.add(node2);

        linkedList.addByOrder(node1);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);
        System.out.println("修改前的链表：");
        linkedList.list();

//        linkedList.update(new Node(4, "林冲之", "豹子头"));
//        System.out.println("修改后的链表：");
//        linkedList.list();

//        linkedList.delete(1);
//        linkedList.delete(3);
//        System.out.println("修改后的链表：");
//        linkedList.list();
//
//        System.out.printf("有效的节点数：%d n", linkedList.size());
//
//        System.out.println("获取倒数第1个节点: " + linkedList.getLastIndexNode(1));

        System.out.println("反转后的节点");
        linkedList.reverse();
        linkedList.list();
    }

    static class SinglelinkedList {
        
        private final Node headNode = new Node(0, "", "");

        
        public void add(Node node) {
            Node temp = headNode;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }

        
        public void addByOrder(Node node) {
            Node temp = headNode;
            //是否已经有这个编号
            boolean isExit = false;
            while (true) {
                //空链表或者在链表的最后，直接退出
                if (temp.next == null) {
                    break;
                } else {
                    //位置已经找到，就在temp后面插入
                    if (temp.next.number > node.number) {
                        break;
                    } else if (temp.next.number == node.number) {//编号已经存在
                        isExit = true;
                        break;
                    }
                    temp = temp.next;
                }
            }

            if (isExit) {
                System.out.printf("编号已经存在，待添加的编号为 %d n", node.number);
            } else {
                //添加新的节点到temp和temp.next之间
                node.next = temp.next;
                temp.next = node;
            }
        }

        
        public void update(Node node) {
            Node temp = headNode.next;
            boolean isExit = false;
            while (true) {
                //遍历到最后一个节点了
                if (temp == null) {
                    break;
                } else {
                    //如果找到该节点
                    if (temp.number == node.number) {
                        isExit = true;
                        break;
                    }
                    temp = temp.next;
                }
            }

            if (isExit) {
                temp.name = node.name;
                temp.nickName = node.nickName;
            } else {
                System.out.printf("没有找到编号为 %d 的节点 n", node.number);
            }

        }

        
        public void delete(int index) {
            Node temp = headNode;
            boolean isExit = false;
            while (true) {
                //遍历到最后一个节点了
                if (temp.next == null) {
                    break;
                } else {
                    //如果找到该节点
                    if (temp.next.number == index) {
                        isExit = true;
                        break;
                    }
                    temp = temp.next;
                }
            }

            if (isExit) {
                temp.next = temp.next.next;
            } else {
                System.out.println("没有找到节点");
            }
        }

        
        public void list() {
            if (headNode.next == null) {
                System.out.println("空链表");
                return;
            }
            Node temp = headNode.next;
            while (temp != null) {
                System.out.println(temp);
                temp = temp.next;
            }

        }

        
        public int size() {
            Node temp = headNode;
            if (temp.next == null) {
                return 0;
            }
            int size = 0;
            while (temp.next != null) {
                size++;
                temp = temp.next;
            }
            return size;
        }

        
        public Node getLastIndexNode(int index) {
            Node temp = headNode.next;
            if (temp == null) {
                return null;
            }
            int size = size();
            if (index <= 0 || index > size) {
                return null;
            }
            for (int i = 0; i < size - index; i++) {
                temp = temp.next;
            }
            return temp;
        }

        
        public void reverse() {
            //如果链表为空，或者只有一个节点，无需反转
            if (headNode.next == null || headNode.next.next == null) {
                return;
            }
            //辅助指针（变量），帮助遍历原来的链表
            Node cur = headNode.next;
            //指向 cur 指针的下一个节点
            Node next;
            //反转后的链表头节点
            Node reverseHeadNode = new Node(0, "", "");
            while (cur != null) {
                //暂时保存当前节点的下一个节点
                next = cur.next;
                //构造cur节点，cur节点的next节点指向reverse链表的第一个节点
                cur.next = reverseHeadNode.next;
                //将构造后的cur节点赋给reverse节点的第一个节点
                reverseHeadNode.next = cur;
                //cur节点后移
                cur = next;
            }
            //headNode.next 指向 reverseNode.next , 实现单链表的反转
            headNode.next = reverseHeadNode.next;
        }
    }


    
    static class Node {
        
        public int number;
        
        public String name;
        
        public String nickName;
        
        public Node next;

        public Node(int number, String name, String nickName) {
            this.number = number;
            this.name = name;
            this.nickName = nickName;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "number=" + number +
                    ", name='" + name + ''' +
                    ", nickName='" + nickName + ''' +
                    '}';
        }
    }


}