链表

概念介绍

　　有同学想认识链表，今天它来！它存储数据不需要连续的内存空间，它扩展方便，大小可变，它于百万军中取敌将首级如探囊取物，也被称为“灵活一号”！

　　链表家族的成员有3类，分别是单向链表，双向链表和循环链表。说一千，道一万，不如上图直接看。

　　单向链表：

     

 　　每个节点除了要存储自身数据外，还要存储下一节点的指向，通过每个节点的指向，把N个节点连成一个链表。单向链表大家可以记为：我中有你，你中无我。

class Node {
    // 存储的数据
    public Object data;
    // 下一节点
    public Node next;
}

　　双向链表：

　　

 　　相对于单向链表的节点，双向链表的节点，需要多存储上一节点的指向。双链表就是名副其实的：我中有你，你中有我。

class Node {
    // 存储的数据
    public Object data;
    // 下一节点
    public Node next;
    // 上一节点
    public Node pre;
}

　　循环链表：

　　

　　最大的特点就是最后一个结点的指针指向头结点，整个链表形成一个环。

代码实现

　　在这里，我们实现的是双向链表，其实只要会一种，其他的都很好理解。我们只完成删除和添加节点的操作，修改就不实现了。

　　我们先把节点定义出来，简单的定义，每个节点存储的是自己的名称。

class Node {
    // 当前节点名称
    public String name;
    // 上一节点
    public Node next;
    // 下一节点
    public Node previous;

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

　　在节点尾部添加节点代码实现说明：A-B-C三个节点，如果我们想在链表的末端添加D，那么我们需要做的事情有2件：

　　一、遍历链表，找到链表的最后一个节点。

　　二、对最后一个节点进行操作，把C的下一个节点指向新添加的节点D并且把D的上一个节点指向C

    public void add(Node addNode) {
        // 在这里，我们使用curNode来帮助我们记录当前遍历到的元素
        Node curNode = head;
        // 如果链表为空，则添加的元素变为头结点
        if (curNode == null) {
            head = addNode;
            return;
        }
        // 如果不为空，我们的目的是走到链表的末端，所以这里使用while循环
        // 当退出while循环时，curNode则为链表的最末端
        while (true) {
            // 只有链表最末端节点的next为null
            if (curNode.next == null) {
                break;
            }
            // 如果没有找到最后, 将将temp后移
            curNode = curNode.next;
        }
        // 这里对链表的最后一个节点进行操作
        curNode.next = addNode;
        addNode.previous = curNode;
    }

　　在节点尾部添加节点代码实现说明：A-B-C三个节点，如果我们想把B节点删除掉，那么我们需要做的事情有3件：

　　一、遍历链表，找到B节点。

　　二、对B的上一个节点A节点进行操作，操作的动作为，将A的下一节点指向C。

　　三、对B的下一个节点C节点进行操作，操作的动作为，将C的上一节点指向A。

    public void delete(Node delNode) {
        // 判断当前链表是否为空,如果为空，肯定无法杀出
        if (head == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        // 同样的，在这里，我们使用curNode来帮助我们记录当前遍历到的元素
        Node curNode = head;
        // 标志是否找到待删除的节点
        boolean flag = false;
        while (true) {
            // 已经到链表的最后，这是退出while循环的一种情况
            if (curNode == null) {
                break;
            }
            // 已经找到待删除的节点目标，可以退出while循环了
            if (curNode.name.equals(delNode.name)) {
                flag = true;
                break;
            }
            curNode = curNode.next;
        }
        // 如果找到删除的目标节点，则进行以下操作
        if (flag) {
            // 所谓的删除，就是把找到的节点的前置节点的后置节点变为删除节点的后置节点
            // 如果待删除的节点为第一节点
            if(curNode.previous == null){
                if(curNode.next!=null){
                    curNode.next.previous = null;
                    head = curNode.next;
                }else {
                    head = null;
                }
                return;
            }
            curNode.previous.next = curNode.next;
            // 如果删除的目标节点是最后一个，则没有这步操作
            if (curNode.next != null) {
                curNode.next.previous = curNode.previous;
            }
            return;
        }
        System.out.printf("要删除的 %s 节点不存在
", delNode.name);
    }

　　　　至此，代码编写完成，如果大家顺着思路去写下来，理解之后，那么再去看LinkedList的源码，会轻松不少，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于data-structure工程下的linkedList目录，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为你揭秘更多数据结构!