单链表常用方法代码实现

发表评论
2,399次阅读

A+

什么是单链表？

n个节点链结成一个链表，即为线性表(a1,a2,……,an)的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单链表。

单链表是通过每一个节点的指针域将线性表的数据元素按逻辑次序链接在一起，而形成单链表。如下图：
单链表常用方法代码实现
可以看到每一个next指针，指向下一个节点的数据元素，直到尾节点。

上图的节点信息我们用代码怎么实现呢？如下代码

Node节点

package link.singlelink;

/**
 * @Description 链表节点
 * @Author lmx.zh
 * @date 2019-06-14 16:39
 * @Copyright 2019 Alibaba.com All right reserved.
 */
public class Node {
    /**
     * 链表元素
     */
    Object data;
    /**
     * 链表后续节点
     */
    Node next;

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

运用面向对象的思想，将节点定义为一个Node对象，对象中包含元素数据(data)和指针域(next)。后续对链表进行增删查时对Node节点进行操作即可。

链表中还需要有一些必要的变量需要定义，如下：

   /**
     * 头节点
     */
    Node head;

    /**
     * 链表大小
     */
    int size;

    /**
     * 链表中的尾元素
     */
    Node last;

增加节点

链表增加节点不同于数组，在增加节点元素后要将next指针域指向下个节点地址，具体细节实现如下代码：

   /**
     * 增加元素
     */
    public void addItem(Object item) {
        //临时性的最后节点
        Node tmp = last;
        //创建新节点
        Node newNode = new Node(item, null);
        //设置最后的节点
        last = newNode;
        //判断最后的节点如果为空，说明链表内无节点，则为头节点
        if (tmp == null) {
            //创建头节点
            head = newNode;
        } else {
            //如果节点不为空，则将该节点的next指针指向新的节点
            tmp.next = newNode;
        }
        ++size;
    }

设置临时节点，可以看做是当前节点
创建新节点，并将链表中的尾节点设置为新节点
判断临时节点是否为空，空则创建头节点，非空则当前节点的next指针域指向新节点
链表大小自增

删除节点

其实删除节点很简单，就是将被删除节点的前一个节点的next指针，指向被删除节点的后一个节点，具体代码实现如下：

   /**
     * 删除元素
     *
     * @param item
     */
    public boolean removeItem(Object item) {

        boolean isRemove = false;
        //头节点
        Node p = head;
        //需要删除的节点
        Node r = head.next;
        //如果节点后继节点不为空，一直循环
        while (r != null) {
            //如果匹配到需要删除的节点，将布尔值设置为true
            if (item.equals(r.data)) {
                isRemove = true;
                break;
            }
            //如果未匹配继续循环节点
            p = r;
            r = r.next;
        }
        //如果遇到需要删除的节点，则更换节点
        if (isRemove) {
            p.next = r.next;
            r.next = null;
            r = null;
            --size;
        }
        return isRemove;
    }

设置从第一个节点依次循环链表
判断节点中是否存在需要删除的数据元素，如果存在则跳出循环
删除元素，将删除元素的上一个节点的next指针域指向删除元素的next指针，即 p.next = r.next，删除节点的数据元素和指针域设置为null
链表大小递减

查询元素

查询链表元素依次循环节点信息，取出节点中的data元素，并将元素保存至Object数组中返回即可。如下代码：

   /**
     * 循环查找单链表元素
     *
     * @return
     */
    public Object[] queryItem() {
        Object[] o = new Object[size];

        if (size > 0) {
            //前驱节点
            Node p = head;
            //哨兵节点
            Node s = head.next;
            //循环下标
            int i = 1;
            //设置头节点元素
            Object item = head.data;
            o[0] = item;
            while (s != null) {
                //如果节点不为空，依次设置链表中的元素
                o[i] = s.data;
                //下标累加
                ++i;
                //设置p节点为下一个节点
                p = s;
                //设置s节点为下下一个节点
                s = s.next;
            }
        }
        return o;
    }

链表中存在元素时，从第一个节点开始，依次循环链表
取出各个节点中的data元素，存放至数组中返回

总结

单链表操作其实就是对节点中的指针域进行各种引用，在写代码之前可以先将需要实现的方法用图表现出来，这样更直观一点，也不至于在写代码时无法确认指针的位置而导致找不到指针域。

ps:上面几个链表的操作，这里并没有设置头节点，而是把头节点(head)直接当做成链表的第一个节点。有时，为了更加方便的操作单链表，会在单链表中设置一个头节点，头节点的数据域可以不存储任何信息，也可以存储一个固定的数值，这样的话，如果有了头节点，在操作单链表时就不用对链表的头节点进行特殊处理了。从另一方面也简化了代码。