上周给前端的小伙伴们进行了讲课,想着总结一下,但是直到推到现在,我才开始。上周讲课的内容是 ES6 和链表。我大致把链表的内容总结一下,也算是个回顾。

一、初始链表

  链表定义:使用一组任意的存储单元存储线性表的数据元素(可连续,也可是不连续),它是一种顺序存储。
  也就是说,链表是线性结构,各个元素的存储位置都是随意的,逻辑结构连续,物理结构不连续。链表只能从表头开始依次向后遍历链表,直到找到第 i 个位置上的元素,时间复杂度为 O(n),即取值操作的效率低。
  而与之对应的是数组:他是一种随机存储结构,指定任意一个位置序号 i,都可以在 O(1)时间内直接存储该位置上的元素,即取值操作的效率高。
  因此:
  数组适合----存取元素
  链表适合----插入和删除

二、链表组成

image.png

  每个结点由数据域指针域组成,一个个结点组成了链表,每个链表只有头结点被标记,最后的结点指向空(null)。

三、链表小试

leetcode203 移除链表元素

删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

方法一:考虑头结点

    public ListNode removeElements(ListNode head, int val) {
            while (head != null && head.val == val){
                head = head.next;
            }
            if (head == null){
                return null;
            }
            ListNode prev = head;
            while (prev.next != null){
                if (prev.next.val == val){
                    prev.next = prev.next.next;
                }else{
                    prev = prev.next;
                }
            }
     return head;
    }

方法二:设置虚拟头结点

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while (prev.next != null){
            if (prev.next.val == val){
                prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }

方法三:递归

    public ListNode removeElements(ListNode head, int val){
        if (head == null){
            return null;
        }
        ListNode res = removeElements(head.next,val);
        if (head.val==val){
            return res;
        }else{
            head.next = res;
            return head;
        }
    }

这三种方法,都可以实现,大家可以自行理解。

四、打印测试

  链表跟数组不一样,他没有办法直接在控制台打印出来。可以跟大家提供一下思路:

  可以用数组模拟传入,写一个内部方法,把数组转化成链表,最后再写一个方法,以字符串的形式打印出来。


标题:链表之单链表
作者:JaneChelle
地址:https://xiao.algerfan.cn/articles/2019/09/07/1567855689899.html