Github issues:https://github.com/littlejoyo/Blog/issues/

个人博客：https://littlejoyo.github.io/

微信公众号：Joyo说

链表是基本的数据结构，笔试或者面试的时候也是常常考察的内容，所以实现一个简单的单链表以及对链表的基本操作要学会信手拈来，面试的时候才能临危不惧吧，加油。

单链表的结构

单链表结构

上面展示的是一个单链表的存储原理图，简单易懂，head为头节点，他不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个next引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，其中的next指向null。

代码实现单链表

链表节点的定义

链表是由一个个节点连接形成的，所以要先定义好节点类，节点类主要分为两块内容就是数据和next指针，定义可以参看下面代码：

public class LinkListDemo {

    //节点类
    private class ListNode {
        private Object data;
        private ListNode next = null;

        ListNode() {
            data = null;
        }

        ListNode(Object data) {
            this.data = data;
        }
    }

    private ListNode head;//头节点
    private ListNode temp;//临时节点


    //初始化链表，生成一个无数据的头节点
    LinkListDemo() {
        head = new ListNode();
    }
}

给链表添加节点

/* ================以下方法是对链表的操作===================*/

    /**
     * 增加节点
     *
     * @param data
     */
    public void addNode(Object data) {
        ListNode node = new ListNode(data);
        temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;

    }

对于插入节点常用的思想主要有头插法 和 尾插法，使用尾插法的话需要再定义一个尾指针来区分。下面可以通过对比讨论他们的不同：

头插法和尾插法的对比

返回链表的长度

/**
     * 返回链表的长度
     * @return
     */
    public int getLength()
    {
        temp = head;
        int length = 0;
        while (temp.next!=null)
        {
            length++;
            temp = temp.next;
        }
        return length;
    }

增加节点到链表指定的位置

对于传入的index需要先判断是否合法，然后通过while循环的遍历寻找index的位置来进行节点的插入。

/**
     * 增加节点到指定的位置
     *
     * @param index
     * @param data
     */
    public void addNodeByIndex(int index, Object data) {
        if (index < 1 || index > getLength() + 1) {
            System.out.println("插入的位置不合法。");
            return;
        }
        int count = 1; //记录遍历的位置
        ListNode node = new ListNode(data);
        temp = head;
        while (temp.next != null) {
            if (index == count++) {
                node.next = temp.next;
                temp.next = node;
                return;
            }
            temp = temp.next;
        }

    }

删除链表指定位置的节点

实现的思路和上面的相似，只是增删节点的处理过程不相同。

 /**
     * 删除指定位置的节点
     *
     * @param index
     */
    public void deleteByIndex(int index) {
        if (index < 1 || index > getLength()) {
            System.out.println("插入的位置不合法。");
            return;
        }

        int count = 1;//记录位置
        temp = head;
        while (temp.next != null) {
            if (index == count++) {
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }

    }

从头到尾打印链表的数据

/**
     * 从头到尾打印节点
     */
    public void printListFromHead() {
        temp = head;
        while (temp.next != null) {
            System.out.print("{" + temp.next.data + "}");
            temp = temp.next;
        }
        System.out.println();

    }

从尾到头打印链表的数据

这里可以利用栈的后进先出的存储特点来实现。

/**
     * 从头到尾打印节点
     */
    public void printListFromHead() {
        temp = head;
        while (temp.next != null) {
            System.out.print("{" + temp.next.data + "}");
            temp = temp.next;
        }
        System.out.println();

    }

测试链表是否能成功建立以及各个方法能否实现

 public static void main(String[] args)
    {
        LinkListDemo list = new LinkListDemo();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4);
        list.addNode(5);
        list.printListFromHead();
        list.addNodeByIndex(3,2.8);
        list.printListFromHead();
        list.deleteByIndex(3);
        list.printListFromHead();
        list.printFromTail();
        System.out.println(list.getLength());
    }

输出结果：

{1}{2}{3}{4}{5}
{1}{2}{2.8}{3}{4}{5}
{1}{2}{3}{4}{5}
{5}{4}{3}{2}{1}
5

微信公众号

扫一扫关注Joyo说公众号，共同学习和研究开发技术。

关注我