Java单链表

蔚落 2023-06-08 10:46 15阅读 0赞

首先链表是顺序表，由许多个结点组成，元素在内存中可以不连续，结点中存放的为当前结点的值和指向下一个结点的指针（引用），由于多存储了结点的引用，所以对于数组来说，存储空间变大。

首先定义一个链表结点  
id和name是结点的值，next是指向下一个结点的指针。

class Node { 
        public int id;
        public String name;
        Node next = null;
    
        public Node(int id,String name) { 
            this.id = id;
            this.name=name;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "id=" + id +
                    ", name='" + name + "'"+
                    '}';
        }
    }

定义一个单链表，定义单链表的头结点，值为空或0；

class SingleLinkedList { 
        //定义头节点 head,头节点不能动
        private Node head = new Node(0,"");
    
        public Node getHead() { 
            return head;
        }
    }

在单链表类中写一个尾部添加结点的方法

//尾部添加
        public void add(Node node) { 
            Node temp = head;//定义辅助遍历
            while (true) { 
                if (temp.next != null) { 
                    temp = temp.next;
                } else { 
                    temp.next = node;
                    break;
                }
            }
    
        }

链表删除结点

//删除该id的节点
        public void delete(int id){ 
            Node temp=head;
            boolean flag=false;
            while (true){ 
                if (temp.next==null){ 
                    break;
                }
                if (temp.next.id==id){ 
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){ 
                temp.next=temp.next.next;
            }else { 
                System.out.println("为找到要删除的节点");
            }
    
        }

链表反转

//反转
        public static void reverse(Node head){ 
            if (head.next==null||head.next.next==null){ 
                return;
            }
            Node cur=head.next;
            Node next=null;
            Node newNode=new Node(0,"");
            while (cur!=null){ 
                next=cur.next;
                cur.next=newNode.next;
                newNode.next=cur;
                cur=next;
            }
            head.next=newNode.next;
        }

完整代码

public class SingleLinkedListDemo { 
        public static void main(String[] args) { 
            Node node1 = new Node(3,"张三");
            Node node2 = new Node(4,"李四");
            Node node3 = new Node(5,"王五");
            Node node4 = new Node(6,"赵六");
            Node node5 = new Node(7,"田七");
            Node node6 = new Node(8,"刘八");
    
            SingleLinkedList singleLinkedList = new SingleLinkedList();
            //末尾添加结点
    // singleLinkedList.add(node1);
    // singleLinkedList.add(node2);
    // singleLinkedList.add(node6);
    // singleLinkedList.add(node3);
    // singleLinkedList.add(node4);
    // singleLinkedList.add(node5);
    
    		//根据id排序添加结点
            singleLinkedList.addByOrder(node1);
            singleLinkedList.addByOrder(node2);
            singleLinkedList.addByOrder(node6);
            singleLinkedList.addByOrder(node3);
            singleLinkedList.addByOrder(node4);
            singleLinkedList.addByOrder(node5);
            singleLinkedList.addByOrder(node3);
            singleLinkedList.addByOrder(node5);
            
            //遍历查看结点
            singleLinkedList.show();
            
    // Node qwe = new Node(10, "qwe");
    // singleLinkedList.update(qwe);
    // System.out.println("更新了10号");
    // singleLinkedList.show();
    // singleLinkedList.delete(3);
    // singleLinkedList.delete(8);
    // singleLinkedList.delete(7);
    // System.out.println("删除了5号");
    // singleLinkedList.show();
            SingleLinkedList.reverse(singleLinkedList.getHead());
            System.out.println();
            singleLinkedList.show();
    
    
    
        }
    }
    
    class SingleLinkedList { 
        //定义头节点 head,头节点不能动
        private Node head = new Node(0,"");
    
        public Node getHead() { 
            return head;
        }
    
        //尾部添加
        public void add(Node node) { 
            Node temp = head;//定义辅助遍历
            while (true) { 
                if (temp.next != null) { 
                    temp = temp.next;
                } else { 
                    temp.next = node;
                    break;
                }
            }
    
        }
    
        //根据id顺序添加，找到id大于此node的前一个节点
        public void addByOrder(Node node) { 
            Node temp = head;
            boolean flag = false;
            while (true) { 
                if (temp.next == null) { 
                    break;
                } else if (temp.next.id > node.id) { 
                    break;
                } else if (temp.next.id == node.id) { 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) { 
                System.out.printf("id为:%d的重复\n", node.id);
            }else { 
                node.next = temp.next;
                temp.next = node;
            }
        }
    
        //找到id相等的节点修改值即可
        public void update(Node node){ 
            if (head.next==null){ 
                System.out.println("空链表");
                return;
            }
            Node temp=head.next;
            boolean flag=false;
            while (true){ 
                if (temp==null){ 
                    break;
                }else if (temp.id==node.id){ 
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            //跳出循环证明找到了
            if (flag){ 
                temp.name=node.name;
            }else { 
                System.out.println("链表中不存在此节点"+node);
    
            }
    
    
        }
    
        //删除该id的节点
        public void delete(int id){ 
            Node temp=head;
            boolean flag=false;
            while (true){ 
                if (temp.next==null){ 
                    break;
                }
                if (temp.next.id==id){ 
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){ 
                temp.next=temp.next.next;
            }else { 
                System.out.println("为找到要删除的节点");
            }
    
        }
        
        //反转
        public static void reverse(Node head){ 
            if (head.next==null||head.next.next==null){ 
                return;
            }
            Node cur=head.next;
            Node next=null;
            Node newNode=new Node(0,"");
            while (cur!=null){ 
                next=cur.next;
                cur.next=newNode.next;
                newNode.next=cur;
                cur=next;
            }
            head.next=newNode.next;
        }
    
        //遍历打印
        public void show() { 
            if (head.next == null) { 
                System.out.println("空");
                return;
            }
            Node temp = head.next;
            while (true) { 
                if (temp != null) { 
                    System.out.println(temp);
                    temp = temp.next;
                } else { 
                    break;
                }
            }
    
        }
    
    }
    
    
    class Node { 
        public int id;
        public String name;
        Node next = null;
    
        public Node(int id,String name) { 
            this.id = id;
            this.name=name;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "id=" + id +
                    ", name='" + name + "'"+
                    '}';
        }
    }