链表 - LinkedList

基本概念

链表和数组类似，但相比于数组，链表有动态大小。而且插入和删除的效率很高，只要O(1)的时间。但是链表的遍历效率并不高。
Java中，链表为LinkedList类，每个节点由内置静态类Node实现：

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

这种链表为双向链表，每个节点储存它前面的节点，后面的节点，以及它自身的值。也可以去掉节点的prev属性，变为单向链表。

基本操作

Java中LinkedList类的方法。

LinkedList<Integer> l = new LinkedList<>();
l.size(); // 链表的长度
l.get(); // 返回链表某个位置的元素
l.add(); // 向链表某个位置添加元素
l.addFirst(); // 向链表头添加元素
l.addLast(); // 向链表尾添加元素
l.remove(); // 删除链表某个位置的元素

Lintcode相关题目

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容