数据结构 | 单链表 SingleLinkedList

链表

链表是一种链式存储的线性表, 所有元素的内存地址不一定是连续的

实现 LinkedList

底层的 Node 有数据域和指针域，分别用于存储数据元素和下一节点的引用

1. 属性

私有内部类 Node 用于存储数据，size 记录当前已经存入的元素个数，first 指向第一个 Node

public class LinkedList<E> {
    // 当前存储的数据的长度（元素个数）
    private int size;
    // 头结点
    private Node<E> first;
    // 未查询到返回值
    private static final int MINUS_ONE = -1;

    // 私有内部类，存储数据的链表节点
    private static class Node<E> {
        // 存储的元素
        E element;
        // 指向下一个节点
        Node<E> next;
        // Node 的构造器
        Node(E element,Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

2. 构造器

创建链表时不用指定容量，链表元素在内存中并不是连续存储的

// LinkedList 的构造器
public LinkedList() {
    size = 0;
    first = null;
}

3. 获取节点

私有方法，获取指定位置的节点，方便其他方法调用，同时进行了索引越界检查

private Node<E> getNode(int index) {
    checkRange(index);
    Node<E> node = first;
    // 指针向后移动 index 次
    for(int i=0;i<index;i++) {
        node = node.next;
    }
    return node;
}

4. 添加插入元素

要分为插到位置为 0 （没有前驱，调用getNode(index-1)会越界）和位置不为 0 两种情况

// 添加元素至链表尾部
public void add(E ele) {
    add(size,ele);
}
// 添加元素
public void add(int index,E ele) {
    checkRangeForAdd(index);
    if(index==0) {
        // 创建新的Node，其next 指向之前的first，然后引用赋给first
        first = new Node<>(ele,first);
    }else {
        // 获取要插入位置前一个 Node
        Node<E> prev = getNode(index-1);
        // 创建新的Node，其next 指向之前的 prev.next，然后引用赋给 prev.next
        prev.next = new Node<>(ele,prev.next);
    }
    size++;
}

5. 删除元素

同样分为删除第一个元素和删除其他元素，将要删除的 node 的前驱节点的 next 修改为 node 的后继

链表删除元素

public E remove(int index) {
    checkRange(index);
    Node<E> node = first;
    if(index==0) {
        first = first.next;
    }else {
        Node<E> prev = getNode(index-1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

6. 清空元素

只要置空 first，其他节点都会被释放

// 清空元素
public void clear() {
    first = null;
    size = 0;
}

7. 修改元素

// 修改指定索引位置上的元素，并返回旧的元素
public E set(int index,E ele) {
    Node<E> node = getNode(index);
    E old = node.element;
    node.element = ele;
    return old;
}

8. 查找元素

// 返回指定索引位置上的元素
public E get(int index) {
    return getNode(index).element;
}

9. 返回指定元素的索引

遍历链表，LinkedList 允许存储 null 值，所以要特殊处理

 // 返回 target 元素的第一次出现的索引，如果不存在，返回-1
public int indexOf(E target) {
    Node<E> node = first;
    // 看一下 target 是不是 null
    if(target==null) {
        // 注意循环中不能使用查找元素的方法get(index)，否则复杂度急剧上升
        for(int i=0;i<size;i++) {
            if(node.element==null) return i;
            node = node.next;
        }
    }else {
        for(int i=0;i<size;i++) {
            if(target.equals(node.element)) return i;
            node = node.next;
        }
    }
    return MINUS_ONE;
}

10. 链表的长度

// 返回当前LinkedList的长度
public int size() {
    return size;
}

11. 是否为空

// 判断链表是否为空
public boolean isEmpty() {
    return size==0;
}

12. 判断元素是否存在

判断指定元素的索引是否是 -1 即可

public  boolean contain(E target) {
    return indexOf(target)!=MINUS_ONE;
}

13. 打印

重写 toString 方法

@Override
public String toString() {
    StringBuilder str = new StringBuilder();
    str.append("size=").append(size).append(", [");
    Node<E> node = first;
    for(int i=0;i<size;i++) {
        if(i!=0) {
            str.append(", ");
        }
        str.append(node.element);
        node = node.next;
    }
    str.append("]");
    return str.toString();
}

14. 索引检查

private void indexOutOfBounds() {
    throw new IndexOutOfBoundsException("索引越界！");
}

private void checkRange(int index) {
    if(index<0||index>=size) {
        indexOutOfBounds();
    }
}

private void checkRangeForAdd(int index) {
    if(index<0 || index>size) {
        indexOutOfBounds();
    }
}

复杂度

对于 add 和 remove 操作，复杂度来自遍历查找目标 index 的操作，并没有移动数据元素，这是和动态数组不同的地方

操作	最好	最坏	平均
add(int index,E ele)	$O(1)$	$O(N)$	$O(N)$
remove(int index)	$O(1)$	$O(N)$	$O(N)$
set(int index,E ele)	$O(1)$	$O(N)$	$O(N)$
get(int index)	$O(1)$	$O(N)$	$O(N)$

链表