链表

链表和数组都是线性结构。不同的是，数组需要一块连续的内存空间来存储数据，而链表则对空间是否连续没有要求。所以这一点差异体现了两种数据结构的不同特性。数组支持随机访问，效率高；而添加、删除操作效率低，因为每一次添加、删除都会造成数据的搬动。链表通过指针指向下一个节点，所以不支持随机访问，只能从头结点遍历；而添加、删除操作比数组效率高，因为不会有数据的搬动。

链表有很多种，单向链表、双向链表、循环链表等。

在Java中，提供了双向链表的实现LinkedList。接下来我们实现一个单链表。能够熟练的实现了之后，剩下的几种形式也就没什么难度了。

public class LinkedList<E> {
    // 定义单链表的节点
    private class Node {
        private E e; // 存储的数据
        private Node next; // 指向下一个节点的引用
        public Node() {
            this(null, null);
        }
        public Node(E e) {
            this(e, null);
        }
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        @Override
        public String toString() {
            return e.toString();
        }
    }
    
    private int size; // 链表中节点数量
    private Node dummyHead; // 指向头结点的引用
  
    public LinkedList() {
        this.size = 0;
        this.dummyHead = new Node(); // 虚拟头结点，不存储任何数据
    }
}

为什么要有一个不存储数据的头结点？在添加、删除方法的实现上，使用不存储数据的头结点能使代码更加的简洁。有兴趣的可以自己实现一个存储数据的头结点，体会一下添加、删除方法的实现。

add() 方法

public void add(E e, int index) {
    if (index < 0 || index > size)
        throw new IllegalArgumentException("illegal index: " + index);
    Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }
    /*
        prev.next = new Node(e, prev.next); 相当于 
        Node node = new Node(e, null);
        node.next = prev.next;
        prev.next = node;
    */
    prev.next = new Node(e, prev.next);
    size++; // 维护变量size
}
public void addFirst(E e) {
    add(e, 0);
}
public void addLast(E e) {
    add(e, size);
}

get() 方法

public Node get(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("illegal index: " + index);
    Node cur = dummyHead.next; // 因为头结点不存储数据，所以从 dummyHead.next 开始
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    return cur;
}
public Node getFirst() {
    return get(0);
}
public Node getLast() {
    return get(size - 1);
}

remove() 方法

// 删除指定位置的节点
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("illegal index: " + index);
    Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }
    Node delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;
    size --;
    return delNode.e;
}
public E removeFirst() {
    return remove(0);
}
public E removeLast() {
    return remove(size - 1);
}
// 删除链表中值为 e 的第一个节点
public void removeElement(E e) {
    Node prev = dummyHead;
    // 找到待删除节点的前驱节点
    for (int i = 0; i < size; i++) {
        if (prev.next.e.equals(e))
            break;
        prev = prev.next;
    }
    // 判断是否为空（当 e 在链表中不存在，会出现为空的情况）
    if (prev.next != null) {
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
    }
}

链表和数组一样，都是基础的数据结构，队列、栈都是基于数组或者链表来实现的。关于链表的面试题目也有很多，就比如单链表翻转、检测链表中是否有环等，可以作为练习。