单链表的基础操作

发表于

概述

我们知道，线性表分为顺序表和链式表。顺序表是基于数组的存储表示，其特点是用物理位置上的邻接关系来表示结点间的逻辑关系。但是基于数组的顺序表的缺点也非常明显，比如说插入/删除的效率低下（平均需要移动一半元素）、需要预先进行存储分配等。

为了克服顺序表的缺点，可以采用链接方式来存储线性表，通常将链接方式的线性表称为链表。链表适用于插入/删除频繁，存储空间不确定的场景。单链表的特点是长度可以很方便地进行扩充，其数据元素的顺序与其链表表示中节点的物理顺序可能不一致，一般通过单链表的指针将各个数据元素按照线性表的逻辑顺序连接起来，如下图：
单链表示意图

由于链表的每个节点带有指针域(引用)，因而在存储空间上比顺序表要付出较大的代价。

创建

创建单链表主要有前插和后插两种方法，建立的方式不同，最终得到的链表也不相同。

前插法建立单链表

前插法是指每次插入新节点总是在表的前端进行，这样插入的结果是链表中各节点中数据的逻辑顺序与输入顺序是正好相反的。其主要步骤如下：

  1. 生成新节点newNode，将读入数据存放到newNode的data域中；
  2. 将newNode插入到链表的前端；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 建立链表
private static Node buildList(int size) {
	Node first = null;
	Node newNode = null;
	// 头插入法
	for (int i = 0; i < size; i++) {
		newNode = new Node(i);
		newNode.next = first;
		first = newNode;
	}
    return first;
}

后插法建立单链表

后插法是指每次newNode总是插入到链表的尾端，这样插入的结果，链表中各个节点的逻辑顺序和输入数据的顺序是完全一致的。这个方法需要设置一个尾指针last，总是指向新链表中最后一个节点，新节点连接到它所指链尾的后面。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static Node buildListLast(int size) {
	Node first = null;
	Node last = null;
	Node now = null;
	// 后插法
	for(int i = 0; i < size; i++) {
		now = new Node(i);
		now.next = null;
		if(first == null) {				
			first = now;
		} else {
			last.next = now;				
		}
		last = now;
	}
	return first;
}

插入

利用单链表来表示线性表，将使得插入和删除变得非常方便，只要修改链中节点指针或引用的值，无需移动表中的元素，就能高效地实现插入和删除操作。

对于插入，我们希望在单链表（a1，a2，a3，…an）的包含数据ai的节点之后插入一个newNode，那么可能会出现3种情况：

  1. 插入到链表头部。这个时候newNode应插入在第一个节点之前，如下图a所示。这时必须修改头指针first。插入操作为：

    1
    2
    newNode.next = first；
    first = newNode;

  2. 插入到链表中间。此时，首先让一个检测指针current指向ai所在节点，再将新节点插入到ai之后，如下图b所示。插入操作为：

    1
    2
    newNode.next = current.next;
    current.next = newNode;

  3. 插入到链表尾端。新节点追加到表尾，如下图c所示。这时，应先令检测指针current指向最后一个节点an，再执行：

    1
    2
    newNode.next = current.next;
    current.next = newNode;

链表插入的示例

从上面可以看出，2和3情形的操作一致，所以这2中情况可以合并考虑。综上，最后可得单链表的插入算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 将新元素插入到第index个节点之后。index从1开始，index = 0表示插入到第一个节点之前
private static Node insert(Node first, Node newNode, int index) {
	// ①如果链表为空，或者插入的索引为0，则插入到前端
	if(first == null || index == 0) {
		newNode.next = first;
		first = newNode;
	} else {
		Node current = first;
		for(int k = 1; k < index; k++) {
			if(current == null) {
				break;
			} else {
				current = current.next;
			}
		}
		if(current == null) {
			System.out.println("无效的插入位置");
		} else { //  ②插入中间或尾部
			newNode.next = current.next;
			current.next = newNode;
		}
	}
	return first;
}

删除

单链表的删除算法比较简单，但也分为2种情况：

  1. 删除头部。这时需要用一个del引用先保存头部节点，再将表头引用指向下一个节点，使其成为新链表的头部，最后删除del保存的节点。如下图a所示。删除操作为：

    1
    2
    3
    Node del = first;
    first = first.next;
    del = null;

  2. 删除中间节点或尾部。设删除链表中的第i个节点，首先用引用del保存第i个节点，再让第i-1个节点的next引用指向第i+1个节点，通过重新拉链，把第i个节点从链表中分离出来，最后删除del引用的节点。如下图b所示。删除操作为：

    1
    2
    3
    Node del = current.next;
    current.next = del.next;
    del = null;

在单链表中删除ai节点

由此可得单链表的删除算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 将链表的第index个元素删除，index从1开始
private static Node delete(Node first, int index) {
	Node del = null;
	Node current = null;
	if(index < 1) { // ①删除头结点
		del = first;
		first = first.next;
		del = null; // 让GC回收
	} else {
		current = first;
		for(int k = 1; k < index - 1; k++) {
			if(current == null) {
				break;
			} else {
				current = current.next;
			}
		}
		if(current == null || current.next == null) {
			System.out.println("无效的删除位置");
		} else { // ②删除中间节点或尾部节点
			del = current.next;
			current.next = del.next;
			del = null;
		}
	}
	return first;
}

遍历

遍历应该是最简单的了，直接看代码：

1
2
3
4
5
6
7
8
9
// 遍历链表
private static void traveling(Node first) {
	Node h = first;   
    while (h != null) {   
        System.out.print(h.value + " ");   
        h = h.next;   
    }   
}

总结

本文主要介绍了链表的相关基础操作：创建、插入、删除、遍历。链表本身很灵活，所以很考察编程功底，所以掌握基础至关重要，接下来还会再写一篇，记录下其他链表的其他进一步的运用。

参考文档