链表-LinkedList

发表于 | 分类于
字数统计: 320

基本概念

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

1
2
3
4
5
6
7
8
9
10
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类的方法。

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

Lintcode相关题目