1. 链表概述

1.1 链表构成

① 链表是由节点构成的列表

② 链表是一种线性数据结构

1.2 dummy节点引入

在实现链表时，可以在第1个有效节点之前增加dummy节点，

① 当链表为空时，dummy节点指向null

② 当链表非空时，dummy节点指向链表的第0个节点（从0开始计数）

1.3 dummy节点作用

增加dummy节点后，链表中的所有有效节点就都有了前驱节点，进而可以用统一的方法处理所有有效节点，而dummy引用无需修改

e.g. 在第0个节点之前插入节点 / 删除第0个节点

说明：作为对比，如果没有dummy节点，只有head引用，

① 当链表为空时，head引用为null

② 当链表非空时，head引用指向第0个节点

那么在遍历链表 / 增加节点 / 删除节点时，均需要判断head引用的状态，针对不同的情况进程处理

2. 链表基础实现

说明：基础实现并不完备，仅为示例，并未考虑异常处理

2.1 节点类型

class ListNode {    public int val;    public ListNode next;    public ListNode(int value) {        val = value;    }}

说明：以示例中的构造函数新建ListNode对象时，节点的next引用默认值为null

2.2 链表类型与构造函数

public class LinkedList {    // dummy节点    private ListNode dummy;    public LinkedList() {        // dummy节点的值此处并无实际用途，可任意设置        dummy = new ListNode(-1);        // dummmy.next初始值为null，表示空链表    }}

2.3 add方法实现

// location：要插入的链表位置（从0开始）// val：要插入的链表值public void add(int location, int val) {    // 我们实现为插入location节点之前，即新加入的节点占据location位序    // 所以要找到location的前驱节点    ListNode pre = dummy;     // 在有dummy节点的情况下，从dummy节点开始，     // 向后移动location个位置，pre即指向location的前驱节点    for (int i = 0; i < location; ++i) {        pre = pre.next;    }    // 生成并插入新节点    ListNode node = new ListNode(val);    node.next = pre.next;    pre.next = node;}

说明：在插入新节点的过程中，如果location为0，则会改变dummy节点的next域，但是不会改变dummy引用的值，这也正是引入dummy节点的意义

2.4 remove方法实现

// location：要删除的节点位序（从0开始）public void remove(int location) {    // 删除location节点也要查找location的前驱节点    ListNode pre = dummy;    // 在有dummy节点的情况下，从dummy节点开始，    // 向后移动location个位置，pre即指向location的前驱节点    for (int i = 0; i < location; ++i) {        pre = pre.next;    }    // 删除location节点    // Java有垃圾回收机制，不用专门释放被删除的节点    pre.next = pre.next.next;}

说明：在删除节点的过程中，如果location为0，也会改变dummy节点的next域，但是不会改变dummy引用的值，这也正是引入dummy节点的意义

2.5 get方法实现

// location：要获取的节点位序（从0开始）public int get(int location) {    // cur指向第0个节点（如果存在的话）    // dummy.next就是head引用    ListNode cur = dummy.next;    for (int i = 0; i < location; ++i) {        cur = cur.next;    }    return cur.val;}

2.6 contain方法实现

// val：要判断是否在链表中存在的链表值public boolean contain(int val) {    // cur指向第0个节点（如果存在的话）    // dummy.next就是head引用    ListNode cur = dummy.next;        // 遍历链表    while (cur != null) {        if (cur.val == val) {            return true;        }        cur = cur.next;    }    return false;}

2.7 print方法实现

public void print() {    // cur指向第0个节点（如果存在的话）    // dummy.next就是head引用    ListNode cur = dummy.next;        // 遍历链表    while (cur != null) {        System.out.print(cur.val + "->");        cur = cur.next;    }    System.out.println("null");}

2.8 测试用例

public static void main(String[] args) {    LinkedList list = new LinkedList();    list.add(0, 10);    list.add(1, 20);    list.add(2, 40);    list.remove(1);    list.print();    System.out.println(list.get(0));    System.out.println(list.get(1));    System.out.println(list.contain(50));    System.out.println(list.contain(40));}

测试结果如下图所示，

3. ArrayList & LinkedList算法时间复杂度对比

补充：LeetCode背后的工作

LeetCode中的解题环境一般如下图所示，

环境中会定义一个Solution类，并定义题解函数，解题过程就是填充这些函数

LeetCode会以如下方式执行代码，现以求解两数之和进行模拟

public class Solution {    // 题解函数    public int aplusb(int a, int b) {        // 题解过程        return a + b;    }        // 环境提供的构造函数    public Solution() {        // 构造函数体    }        // 以测试用例为参数，运行题解函数    public static void main(String[] args) {        Solution solution = new Solution();        System.out.println(solution.aplusb(10, 20));    }}

转载地址：http://ahwx.baihongyu.com/

你可能感兴趣的文章