关于算法:看动画学算法之linkedList

3次阅读

共计 1915 个字符，预计需要花费 5 分钟才能阅读完成。

linkedList 应该是一种十分非常简单的数据结构了。节点一个一个的连接起来，就成了 linkedList。明天咱们应用动画的办法一起来看看 linkedList 是怎么插入和删除的。

linkedList 是由一个一个的节点形成的。而每个节点只须要存储要保留的数据和下一个节点的援用即可。

linkedList 自身须要一个 head 节点，所以咱们的 linkedList 能够这样构建：

public class LinkedList {

    Node head; // head 节点

    //Node 示意的是 Linked list 中的节点，蕴含一个 data 数据和下一个节点的援用
    class Node {
        int data;
        Node next;
        //Node 的构造函数
        Node(int d) {data = d;}
    }
}

先看一下 linkedList 怎么插入数据，插入数据有三种形式，头部插入，尾部插入，两头插入。

先看一个头部插入的例子：

头部插入的逻辑是什么呢？

新插入的节点作为 head 节点，而后将原来的 head 节点指向以后 head 节点的 next 援用即可。

    // 插入到 linkedList 的头部
    public void push(int newData) {
        // 构建要插入的节点
        Node newNode = new Node(newData);
        // 新节点的 next 指向当初的 head 节点
        newNode.next = head;
        // 现有的 head 节点指向新的节点
        head = newNode;
    }

再看一下尾部插入的例子：

插入的逻辑是什么呢？

找到最初一个节点，而后将最初一个节点的 next 指向新插入的节点。

// 新节点插入到 list 最初面
    public void append(int newData) {
        // 创立新节点
        Node newNode = new Node(newData);
        // 如果 list 是空，则新节点作为 head 节点
        if (head == null) {
            head = newNode;
            return;
        }

        newNode.next = null;
        // 找到最初一个节点
        Node last = head;
        while (last.next != null) {last = last.next;}
        // 插入
        last.next = newNode;
        return;
    }

再看一下两头插入的例子：

这个例子中，咱们在第三个节点的地位插入了一个 93。

插入逻辑就是先找到第二个节点，将第二个节点的 next 指向新节点，而后将新节点的 next 指向原先的第三个节点。

看下 java 代码如何实现：

// 插入在第几个元素之后
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {if (prevNode == null) {System.out.println("输出的 index 有误，请从新输出");
                return;
            }
            prevNode = prevNode.next;
        }
        // 创立新的节点
        Node newNode = new Node(newData);
        // 新节点的 next 指向 prevNode 的下一个节点
        newNode.next = prevNode.next;
        // 将新节点插入在 prevNode 之后
        prevNode.next = newNode;
    }

再看一下怎么删除某个地位的节点：

下面的例子中，咱们要删除第 5 个节点。

删除的逻辑就是找到第 4 个节点和第 6 个节点。而后将第四个节点的 next 指向第 6 个节点即可。

看下相应的 java 代码如下：

    // 删除特定地位的节点
    void deleteNode(int index)
    {
        // 如果是空的，间接返回
        if (head == null)
            return;

        // head 节点
        Node temp = head;

        // 如果是删除 head 节点
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // 找到要删除节点的前一个节点
        for (int i=1; temp!=null && i<index-1; i++)
            temp = temp.next;

        // 如果超出范围
        if (temp == null || temp.next == null)
            return;

        // temp->next 是要删除的节点，删除节点
        Node next = temp.next.next;
        temp.next = next;
    }

本文的代码地址：

learn-algorithm