[数据结构与算法]链表的基本操作——增删改查，使用数组或链表的建议

链表

链表如果不计查找算法的时间来说，其余操作时间复杂为O(1)

链表节点

Node.java

package SuanFa.链表;
/**
 * 单向链表节点
 */
public class Node {
    int val;
    Node next;
    public Node(){
    }
    public Node(int val){
        this.val = val;
    }
}

链表的增删改查

MyLinkedList.java

public class MyLinkedList {
    //头结点
    private Node head;
    //尾结点
    private Node last;
    //记录链表的长度
    private int size;

    /**
     * 查找节点
     * @param index 通过下标来找位置
     * @return Node 返回该节点
     */
    public Node get(int index){
        //判断输入的下标是否超出链表范围
        //即：当有一个元素时 索引不能为1 且不能小于0
        if(index<0 || index>=size){
            System.out.println("===下标超出链表范围===");
            return null;
        }else {
            //遍历链表节点
            //临时节点等于带头结点 每次调用该方法都重新遍历
            Node temp = head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;//等于下一个节点
            }
            return temp;
        }
    }
    /**
     * 插入元素
     * @param index     插入位置（下标）
     * @param val      插入元素
     * @return
     */
    public void insert(int index,int val){
        //判断输入的下标是否超出链表范围
        //即：当有1个元素时 索引不能为2 且不能小于0
        if(index<0 || index>size){
            System.out.println("===下标超出链表范围===");
        }else {
            Node newNode = new Node(val);
            //判断索引在哪
            if (size == 0) {
                //当为空链表时
                head = newNode;
                last = newNode;
            } else if (index == 0) {
                //插入头
                newNode.next = head;//既然是插入头肯定是指向头指针
                head = newNode;//变更头指针
            } else if (index == size) {
                //插入尾
                last.next = newNode;
                last = newNode;
            } else {
                //插入中间
                //1  3  插入2  获取1.next 2.next = 1.next  1.next = 2.next
                //首先是要找到索引位置
                //Node insertIndex = get(index);//插入位置的索引
                Node prevIndex = get(index - 1);//插入位置的索引 没有前置指针单向列表只有next 所以要减1 获取当前插入位置的前置指针
                newNode.next = prevIndex.next;
                prevIndex.next = newNode;
            }
            //长度加1
            size++;
        }
    }
    /**
     * 删除元素
     * @param index 删除的下标
     * @return 并返回这个元素给你看
     */
    public Node delete(int index){
        //同样的 有一个元素 删除的索引不可以是1
        if(index<0 || index>=size){
            System.out.println("===下标超出链表范围===");
            return null;
        }else{
            //获取删除节点
            Node deleteNode = new Node();//默认为空
            if(index == 0){
                //删除第一个
                deleteNode = head;
                head = head.next;
            }else if(index == size-1){
                Node prevNode = get(index-1);//获取前一个节点
                deleteNode = prevNode.next;//获取删除节点
                prevNode.next = null;
                last = prevNode;//改变尾指针
            }else{
                //删除中间的节点
                Node prevNode = get(index-1);//获取前一个节点
                deleteNode = prevNode.next;//获取删除节点
                prevNode.next = prevNode.next.next;//这波叫直接跳过这个节点 会被Java自动回收
            }
            return deleteNode;
        }
    }
    /**
     * 修改操作
     * @param index 要修改的索引
     * @param upVal 修改后的值
     * @return boolean
     */
    public boolean update(int index,int upVal){
        //同样的 有一个元素 修改的索引不可以是1
        if(index<0 || index>=size){
            System.out.println("===下标超出链表范围===");
            return false;
        }else{
            if(index == 0){
                //修改头结点
                head.val = upVal;
            }else if(index == size-1){
                //修改尾节点
                last.val = upVal;
            }else{
                //修改中间的节点
                Node updateNode = get(index);//获取修改节点
                updateNode.val = upVal;
            }
        }
        return true;
    }

    /**
     * 输出链表元素
     * @return 输出链表的元素
     */
    public void print(){
        Node temp = head;
        //为空说明是最后一个元素了
        while(temp!=null){
            System.out.print(temp.val+" ");
            temp = temp.next;
        }
    }
}

链表测试类

MyLinkedListDemo.java

public class MyLinkedListDemo {
    public static void main(String[] args) {
        MyLinkedList mll = new MyLinkedList();
        Node node = mll.get(0);//没有元素得到节点 null
        System.out.println(node);

        mll.insert(0,2);// 2
        mll.insert(1,3);// 2 3
        mll.insert(2,4);// 2 3 4
        mll.insert(1,6);// 2 6 3 4

        System.out.println(mll.get(2).val);//返回的是节点 通过节点的val 获取值 3
        mll.print();
        //删除测试
        System.out.println();
        System.out.println(mll.delete(2).val);//返回的是节点 通过节点的val 获取值
        mll.print();
        //修改测试
        System.out.println();
        mll.update(1,5);//把6 修改成5
        mll.print();

    }
}

链表和数组的区别

各有春秋，主要看运用环境，如果需要读操作多，写（增删改）操作少的话建议用数组；相反则用链表比较灵活