单向链表不同位置的新增，删除节点操作

比眉伴天荒 2023-03-13 15:21 24阅读 0赞

### 1.什么是链表？ ###

一种线性的数据存储方式的数据结构，由若干个节点组成，物理上，非连续，非顺序的存储方式  
**物理存储方式**：随机存储  
**数据访问方式**：顺序访问

### 2.链表分类：单向链表，双向链表 ###

单向链表：每个节点包含两部分：一部分存数据，一部分存指向下一个节点的地址值  
双向链表：每个节点在单链表基础上，还存储了上一个节点的地址值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center 1]

### 3.对比链表和数组的内存分配方式： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center 2]

### 4.编码实现单向链表的基本增删改查操作 ###

public class MyLinkedList { 
    
        //链表头节点
        private Node head;
    
        //链表实际长度
        private int size;
    
        private Node endNode;
    
        /** * 在链表指定位置插入数据 * * @param index 指定插入位置 * @param data 插入的值 */
        //分别在一个空链表/链表头部/链表尾部/链表中间插入一个节点
        private void insertNode(int index, int data) throws Exception { 
            if (index < 0 || index > size) { 
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
    
            Node node = new Node(data);
            //空链表
            if (size == 0) { 
                head = node;
                endNode = node;
            } else if (index == 0) { 
                //插入头节点
                head = node;
                node.next = head;
            } else if (index == size) { 
                //插入尾部
                endNode.next = node;
                endNode = node;
            } else { 
                //中间插入
                Node prevNode = get(index - 1);
                node.next = prevNode.next;
                prevNode.next = node;
            }
            size++;
        }
    
        /** * 删除指定为位置节点 * @param index */
        public void deleteNode(int index) throws Exception { 
            if(index<0 || index>size){ 
                throw new NullPointerException("超出当前链表范围");
            }
            Node temp = null;
            //删除头部节点
            if(index == 0){ 
                temp = head;
                head  = head.next;
            }else if(index == size-1){ 
                //删除尾节点
                endNode  = null;
                Node prevNode = get(index-1);
                prevNode.next = null;
                endNode = prevNode;
            }else { 
                //删除中间指定位置节点
                Node prevNode = get(index-1);
                Node nextNode = prevNode.next.next;
                prevNode.next = null;
                prevNode.next = nextNode;
    
            }
            size--;
        }
        
    
        /** * 获取指定位置节点 * * @param index 指定位置 * @return 链表指定位置节点 */
        public Node get(int index) throws Exception { 
            if (index < 0 || index > size) { 
                throw new IndexOutOfBoundsException("超出链表范围");
            }
            Node temp = head;
    
            for (int i = 0; i < index; i++) { 
                temp = temp.next;
            }
            return temp;
        }
    
    
        /** * 遍历整个链表输出节点的值 */
        private void output() { 
            Node temp = head;
            while (null != temp) { 
                System.out.print(temp.datas + ",");
                temp = temp.next;
            }
    
    
        }
    
    
        public static void main(String[] args) throws Exception { 
    // //尾部插入节点
            MyLinkedList endNodeLinkedList = new MyLinkedList();
            endNodeLinkedList.insertNode(0, 5);
            endNodeLinkedList.insertNode(1, 6);
            endNodeLinkedList.insertNode(2, 2);
            endNodeLinkedList.insertNode(3, 9);
            endNodeLinkedList.output();
            endNodeLinkedList.get(0);
            System.out.println("值是："+endNodeLinkedList.get(0).datas);
    
            //空链表插入节点
            MyLinkedList emptyLinkedList = new MyLinkedList();
            emptyLinkedList.insertNode(0, 1);
            emptyLinkedList.output();
    
            //已知链表中间插入一个节点
            MyLinkedList midLinkedList = new MyLinkedList();
            midLinkedList.insertNode(0, 3);
            midLinkedList.insertNode(1, 4);
            midLinkedList.insertNode(2, 5);
            midLinkedList.insertNode(3, 6);
            midLinkedList.insertNode(2, 9);
            midLinkedList.output();
    
            //删除指定位置节点
    
            MyLinkedList delteLinkedList  = new MyLinkedList();
            delteLinkedList.insertNode(0,1);
            delteLinkedList.insertNode(1,5);
            delteLinkedList.insertNode(2,6);
            delteLinkedList.insertNode(3,7);
            delteLinkedList.insertNode(4,8);
            delteLinkedList.insertNode(5,9);
            delteLinkedList.insertNode(6,10);
    
            //删除头节点
            delteLinkedList.deleteNode(0);
            delteLinkedList.output();
            //删除尾部节点
            delteLinkedList.deleteNode(delteLinkedList.size-1);
            delteLinkedList.output();
    // //删除中间指定位置节点
            delteLinkedList.deleteNode(3);
            delteLinkedList.output();
        }

参考书籍：《漫画算法》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/927a138a90eb4988afd700708f8ebd85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230312/6c53ee93304d4544b24b73276d901b95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x5bm5lWm9l_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230312/64575c32ceda4142a7e35a1492f900e3.png