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

实现 LinkedList
底层的 Node 有数据域和指针域,分别用于存储数据元素和下一节点的引用
1. 属性
私有内部类 Node 用于存储数据,size 记录当前已经存入的元素个数,first 指向第一个 Node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| 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(E element,Node<E> next) { this.element = element; this.next = next; } } }
|
2. 构造器
创建链表时不用指定容量,链表元素在内存中并不是连续存储的
| public LinkedList() { size = 0; first = null; }
|
3. 获取节点
私有方法,获取指定位置的节点,方便其他方法调用,同时进行了索引越界检查
| private Node<E> getNode(int index) { checkRange(index); Node<E> node = first; for(int i=0;i<index;i++) { node = node.next; } return node; }
|
4. 添加插入元素
要分为插到位置为 0 (没有前驱,调用getNode(index-1)会越界)和位置不为 0 两种情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public void add(E ele) { add(size,ele); }
public void add(int index,E ele) { checkRangeForAdd(index); if(index==0) { first = new Node<>(ele,first); }else { Node<E> prev = getNode(index-1); 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 值,所以要特殊处理
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public int indexOf(E target) { Node<E> node = first; if(target==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(target.equals(node.element)) return i; node = node.next; } } return MINUS_ONE; }
|
10. 链表的长度
| 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)$ |
参考