数据结构 单链表SingleLinkedList

链表

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

链表

实现 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 的构造器
Node(E element,Node<E> next) {
this.element = element;
this.next = next;
}
}
}

2. 构造器

创建链表时不用指定容量,链表元素在内存中并不是连续存储的

1
2
3
4
5
// LinkedList 的构造器
public LinkedList() {
size = 0;
first = null;
}

3. 获取节点

私有方法,获取指定位置的节点,方便其他方法调用,同时进行了索引越界检查

1
2
3
4
5
6
7
8
9
private Node<E> getNode(int index) {
checkRange(index);
Node<E> node = first;
// 指针向后移动 index 次
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) {
// 创建新的Node,其next 指向之前的first,然后引用赋给first
first = new Node<>(ele,first);
}else {
// 获取要插入位置前一个 Node
Node<E> prev = getNode(index-1);
// 创建新的Node,其next 指向之前的 prev.next,然后引用赋给 prev.next
prev.next = new Node<>(ele,prev.next);
}
size++;
}

5. 删除元素

同样分为删除第一个元素和删除其他元素,将要删除的 node 的前驱节点的 next 修改为 node 的后继

链表删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
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,其他节点都会被释放

1
2
3
4
5
// 清空元素
public void clear() {
first = null;
size = 0;
}

7. 修改元素

1
2
3
4
5
6
7
// 修改指定索引位置上的元素,并返回旧的元素
public E set(int index,E ele) {
Node<E> node = getNode(index);
E old = node.element;
node.element = ele;
return old;
}

8. 查找元素

1
2
3
4
// 返回指定索引位置上的元素
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
 // 返回 target 元素的第一次出现的索引,如果不存在,返回-1
public int indexOf(E target) {
Node<E> node = first;
// 看一下 target 是不是 null
if(target==null) {
// 注意循环中不能使用查找元素的方法get(index),否则复杂度急剧上升
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. 链表的长度

1
2
3
4
// 返回当前LinkedList的长度
public int size() {
return size;
}

11. 是否为空

1
2
3
4
// 判断链表是否为空
public boolean isEmpty() {
return size==0;
}

12. 判断元素是否存在

判断指定元素的索引是否是 -1 即可

1
2
3
public  boolean contain(E target) {
return indexOf(target)!=MINUS_ONE;
}

13. 打印

重写 toString 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@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. 索引检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)$

参考