An Example Post

nisdfaisdfasdfa

• anidf
• andif

手写一个简单的单链表的增删改查, 本文不注重代码的严谨格式等, 仅仅是探究其实现的思想

假如我们需要添加一个数据

代码中数据结构是这样的

class Node {
    // 存储下一个节点
    Node next;
    String mes;
    public Node(String mes) {
        this.mes = mes;
    }
}

插入

public static void insert(Node n) {
        Node current = rootNode;

        if (current == null) {
            // 第一次插入
            rootNode = n;
            return;
        }

        Node next;
        while ((next = current.getNext()) != null) {
            current = next; // 移动指针
        }
        current.setNext(n);
    }

删除

 public static void delete(String mes) {
        Node current = rootNode;

        Node next;
        // 1， 2， 3， 4， 5
        // 假如是要删除3， 则需要2的指针链上4
        // 因为单链表找不到前驱节点， 所以需要先找到2所在的当前节点， 然后删除3，找到3所在的节点的下一个节点指向2
        while ((next = current.getNext()) != null) {

            if (mes.equals(next.getMes())) {
                // 删除节点， 指针位置发生改变
                current.setNext(next.getNext());  // 2 = 4
                next.setNext(null); // 3 // 原本3的指向移除掉
                return;
            }
            current = next;
        }
    }

修改

 public static void modify(String oldMes, String newMes) {
        Node current = rootNode;

        Node next;
        // 1， 2， 3， 4， 5
        // 假如要修改的是3，改为 6

        while ((next = current.getNext()) != null) {
            if (oldMes.equals(current.getMes())) {
                current.setMes(newMes);
                return;
            }
            current = next;
        }
    }

获取

    public static void getAll() {
        Node current = rootNode;
        Node next;
        while ((next = current.getNext()) != null) {
            System.out.println(current.getMes());
            current = next;
        }
        System.out.println(current.getMes());
    }

完整代码如下

public class MyTest {

    private static Node rootNode = null;

    public static void insert(Node n) {
        Node current = rootNode;

        if (current == null) {
            // 第一次插入
            rootNode = n;
            return;
        }

        Node next;
        while ((next = current.getNext()) != null) {
            current = next; // 移动指针
        }
        current.setNext(n);
    }

    public static void delete(String mes) {
        Node current = rootNode;

        Node next;
        // 1， 2， 3， 4， 5
        // 假如是要删除3， 则需要2的指针链上4
        // 因为单链表找不到前驱节点， 所以需要先找到2所在的当前节点， 然后删除3，找到3所在的节点的下一个节点指向2
        while ((next = current.getNext()) != null) {

            if (mes.equals(next.getMes())) {
                // 删除节点， 指针位置发生改变
                current.setNext(next.getNext());  // 2 = 4
                next.setNext(null); // 3 // 原本3的指向移除掉
                return;
            }
            current = next;
        }
    }

    public static void modify(String oldMes, String newMes) {
        Node current = rootNode;

        Node next;
        // 1， 2， 3， 4， 5
        // 假如要修改的是3，改为 6

        while ((next = current.getNext()) != null) {
            if (oldMes.equals(current.getMes())) {
                current.setMes(newMes);
            }
            current = next;
        }
    }

    public static void getAll() {
        Node current = rootNode;

        Node next;
        while ((next = current.getNext()) != null) {
            System.out.println(current.getMes());
            current = next;
        }
        System.out.println(current.getMes());
    }

    public static void main(String[] args) {

        Node node = new Node("1");
        Node node1 = new Node("2");
        Node node2 = new Node("3");
        Node node3 = new Node("4");
        Node node4 = new Node("5");

        insert(node);
        insert(node1);
        insert(node2);
        insert(node3);
        insert(node4);

        delete("3");
        modify("3", "6");

        getAll();

    }

}

class Node {
    // 存储下一个节点
    private Node next;

    private String mes;

    public Node(String mes) {
        this.mes = mes;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public String getMes() {
        return mes;
    }

    public void setMes(String mes) {
        this.mes = mes;
    }
}

好了, 增删改查的代码大致就是这些了, 在 ArrayList源码分析 中我们了解到其内部使用的是数组的结构, 或者叫顺序表的方式, 那么他们两个到底有什么区别呢 ? 或者是在使用场景上有什么区别呢 ?

首先针对数据的增删改查来说, 顺序表的内存地址是连续的, 他可以基于下标快速访问到元素,这是优点, 删除元素需要一直遍历查找到元素为止, 然后一个一个到挪动元素的位置, 消耗时间

相对于顺序表, 单链表的优点是, 内存地址是不连续的, 当前节点存在着下一个节点的引用, 直接修改节点引用即可, 复杂度相对于顺序表简单

所以查找到使用顺序表结构, 修改多使用链表的形式