数据结构-单向链表（Java实现）

小灰灰 2023-10-09 12:13 39阅读 0赞

/**
     * 单向链表
     */
    public class LinkedList {
        private Node head;
        private Node tail;
        private int size = 0;
    
        /**
         * 插入节点
         * @param data
         * @param index
         * @throws IndexOutOfBoundsException
         */
        public void insert(int data,int index) throws IndexOutOfBoundsException{
            if (index < 0 || index > size){
                throw new IndexOutOfBoundsException("索引超出最大长度");
            }
            Node insertedNode = new Node(data);
            if (size == 0){
                head = insertedNode;
                tail = insertedNode;
            }else if (index == 0){
                insertedNode.nextNode = head;
                head = insertedNode;
            }else if (index == size){
                tail.nextNode = insertedNode;
                tail = insertedNode;
            }else {
                Node tempNode = get(index - 1);
                insertedNode.nextNode = tempNode.nextNode;
                tempNode.nextNode = insertedNode;
            }
            size ++;
        }
    
        /**
         * 删除节点
         * @param index
         * @return
         * @throws IndexOutOfBoundsException
         */
        public Node remove(int index) throws IndexOutOfBoundsException{
            if (index < 0 || index >= size){
                throw new IndexOutOfBoundsException("索引超出最大长度");
            }
            Node removeNode = null;
            if (index == 0){
                removeNode = head;
                head = removeNode.nextNode;
            }else if (index == size-1){
                Node tailNode = get(index - 1);
                removeNode = tailNode.nextNode;
                tailNode.nextNode = null;
                tail = tailNode;
            }else {
                Node tempNode = get(index - 1);
                Node nextNode = tempNode.nextNode.nextNode;
                removeNode = tempNode.nextNode;
                tempNode.nextNode = nextNode;
            }
            size --;
            return removeNode;
        }
    
        /**
         * 根据索引获取节点
         * @param index
         * @return
         * @throws IndexOutOfBoundsException
         */
        public Node get(int index) throws IndexOutOfBoundsException{
            if (index < 0 || index >= size){
                throw new IndexOutOfBoundsException("索引超出最大长度");
            }
            Node tempNode = head;
            for (int i = 0;i< index;i++){
                tempNode = tempNode.nextNode;
            }
            return tempNode;
        }
    
        /**
         * 打印节点信息
         */
        public void outPutInfo(){
            Node tempNode = head;
            while (tempNode != null){
                System.out.println(tempNode.data);
                tempNode = tempNode.nextNode;
            }
        }
    
        /**
         * 链表节点
         */
        private class Node{
            int data;
            Node nextNode;
            Node(int data){
                this.data = data;
            }
        }
    }

public class Main {
        public static void main(String[] args) {
            LinkedList myLinkedList = new LinkedList();
            myLinkedList.insert(0,0);
            myLinkedList.insert(1,1);
            myLinkedList.insert(2,2);
            myLinkedList.insert(3,3);
            myLinkedList.insert(4,4);
            myLinkedList.insert(5,5);
            myLinkedList.remove(0);
            myLinkedList.outPutInfo();
        }
    }