数据结构-单向链表

单向链表的结构

单向链表.png

Node节点

static class Node<E> {
    E element;
    Node<E> next;
    public Node(E element, Node<E> next) {
        this.element = element;
        this.next = next;
    }
}

根据index获取节点

private Node<E> node(int index) {
    rangeCheckFor(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

添加

public void add(int index, E element) {
    rangeCheckForAdd(index);
    if (index == 0) {
       first = new Node<>(element, first);
    } else {
        Node<E> node = node(index - 1);
        node.next = new Node<>(element, node.next);
    }
    size++;
}

删除

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

获取index位置的元素

public int indexOf(E element) {
    Node<E> node = first;
    if (element == null) {
        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 (element.equals(node.element)) { return i; }
           node = node.next;
       }
    }
    return ELEMENT_NOT_FOUND;
}

清空

 public void clear() {
    first = null;
    size = 0;
}

虚拟头节点的单向链表

• 观察代码我们发现很多时候我们都需要针对头节点做单独处理
• 为了减少代码的复杂度 我们可以加一个虚拟头节点
• 添加 删除逻辑会简化不少

public SingleLinkedList() {
    first = new Node<>(null, null);
}