链表（Linked List）介绍

链表是有序的列表，它在内存中存储如下：

  1. 链表是以节点的方式来存储，是链式存储
  2. 每个节点包含data域和指针域
  3. 如图：链表的各个节点不一定是连续存储
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

带头结点的单向链表示意图如下：

带头结点的双向链表示意图如下：

单向链表的应用实例

使用带头结点的单向链表，实现水浒英雄排行榜对英雄人物的增删改查操作。

创建Hero对象，每一个对象就是一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class HeroNode {
    // data域
	public int no;
	public String name;
	public String nickname;
    // next域
	public HeroNode next;

	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}

}

添加英雄时，直接添加到链表尾部

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList {
	// 初始化一个头节点
	private HeroNode head = new HeroNode(0, "", "");

	// 返回头节点
	public HeroNode getHead() {
		return head;
	}

	// 添加节点到单向链表
	// 思路，当不考虑编号顺序时
	// 1. 找到当前链表的最后节点
	// 2. 将最后这个节点的next 指向 新的节点
	public void add(HeroNode heroNode) {

	    // 因为head节点不能动，因此我们需要一个辅助节点temp，用于遍历
        // 使它指向链表的头结点，相当于C语言的指针
		HeroNode temp = head;
		// 遍历链表，找到最后一个节点
		while (true) {
			// 判断temp指向的节点是否为最后一个节点
			if (temp.next == null) {//
				break;
			}
			// 如果没有找到最后节点, 将temp往后移
			temp = temp.next;
		}
		// 当退出while循环时，temp就指向了链表的最后一个节点
		// 将最后这个节点的next 指向 新的节点
		temp.next = heroNode;
	}

	// 显示链表[遍历]
	public void list() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		while (true) {
			// 输出节点的信息
			System.out.println(temp);
			if (temp.next == null) {
				break;
			}
			// 将temp后移
			temp = temp.next;
		}
	}
}

添加英雄时，根据英雄排名添加到指定位置

如果有这个排名，则添加失败，并给出提示。如图，s为新节点，只需s->next = p->next;p->next = s;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class SingleLinkedList { //具体实现方法，与上面同一个类
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;
		while (true) {
			if (temp.next == null || temp.next.no > heroNode.no) {
				heroNode.next = temp.next;
				temp.next = heroNode;
				break;
			}else if(temp.next.no == heroNode.no){
				System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
			}
			temp = temp.next;
		}
		
	}
}

根据no编号修改英雄信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class SingleLinkedList {//具体实现方法，与上面同一个类
	public void update(HeroNode newHeroNode) {
		HeroNode temp = head;
		while (true) {
			if (temp.next == null) {
				System.out.println("修改失败，没有找到该节点！");
				break;
			}else if (temp.next.no == newHeroNode.no) {
				temp.next.name = newHeroNode.name;
				temp.next.nickname = newHeroNode.nickname;
				System.out.println("修改成功：" + temp.next);
				break;
			} 
			temp = temp.next;
		}
	}
}

根据no编号删除英雄信息

如图，p->next为要删除的节点，只需p->next = p->next->next;。被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class SingleLinkedList {
	public void del(int no) {
		HeroNode temp = head;
		while(true) {
			if (temp.next == null) {
				System.out.println("找不到该节点，无法删除！");
				break;
			}else if (temp.next.no == no) {
				temp.next= temp.next.next;
				System.out.printf("编号为 %d 的英雄删除成功!\n",no);
				break;
			}
			temp = temp.next;
		}
	}
}

注意：在执行修改和删除操作时必须先判断temp.next为不为空，否则容易出现异常。

测试

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
31
32
33
34
35
36
37
package com.nanzx.linkedlist;

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		// 先创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

		// 创建管理链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();

		// 链表尾部加入
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero4);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);

		// 按编号的顺序加入
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero3);

		// 测试修改节点的代码
//		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
//		singleLinkedList.update(newHeroNode);

		// 测试删除节点的代码
//		singleLinkedList.del(1);
//		singleLinkedList.del(4);
		
 		singleLinkedList.list();
	}
}

单向链表面试题

获取到单向链表节点的个数

要求：如果是带头节点的链表，不统计头节点

1
2
3
4
5
6
7
8
9
10
   // 方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
public static int getLenth(HeroNode head) {
	int length = 0;
	HeroNode cur = head.next;
	while (cur != null) {
		length++;
		cur = cur.next;
	}
	return length;
}

查找单向链表中的倒数第k个结点 【新浪面试题】

思路：

  1. 编写一个方法，接收head节点，同时接收一个index
  2. index 表示是倒数第index个节点
  3. 先把链表从头到尾遍历，得到链表的总的长度 size=getLenth
  4. 得到size 后，我们从链表的第一个非头结点开始遍历 (size-index)个
  5. 如果找到了，则返回该节点，否则返回nulll
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static HeroNode findLastIndexNode(HeroNode head, int index) {
		if (head.next == null) {
			return null;
		}
		int size = getLenth(head);
		// 先做一个index的校验
		if (index <= 0 || index > size) {
			return null;
		}
		// 定义给辅助变量， for 循环定位到倒数的index
		HeroNode cur = head.next;  
    	// 例如：size4-index2=2，cur只需移动2步就可以得到结果
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;
	}

实现单向链表的反转【腾讯面试题】

方法：头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void reversetList(HeroNode head) {
	// 如果当前链表为空，或者只有一个节点，无需反转，直接返回
	if (head.next == null || head.next.next == null) {
		return;
	}
	HeroNode cur = head.next;
	HeroNode next = null;// 指向当前节点[cur]的下一个节点
	HeroNode reverseHead = new HeroNode(0, "", "");
	// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
	while (cur != null) {
		next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
		cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
		reverseHead.next = cur; // 将cur 连接到新的链表上
		cur = next;// 让cur后移
	}
	// 将head.next 指向 reverseHead.next , 实现单链表的反转
	head.next = reverseHead.next;
}

从尾到头打印单向链表【百度面试题】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
	public static void reversePrint(HeroNode head) {
		if (head.next == null) {
			return;// 空链表，不能打印
		}
		// 创建要给一个栈，将各个节点压入栈
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		// 将链表的所有节点压入栈
		while (cur != null) {
			stack.push(cur);
			cur = cur.next; // cur后移，这样就可以压入下一个节点
		}
		// 将栈中的节点进行打印,pop 出栈
		while (stack.size() > 0) {
			System.out.println(stack.pop()); // stack的特点是先进后出
		}
	}

双向链表的应用实例

使用带头结点的双向链表，实现水浒英雄排行榜对英雄人物的增删改查操作。

管理单向链表的缺点分析：

  1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

  2. 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单向链表删除时节点，总是找到temp，temp是待删除节点的前一个节点。

分析双向链表的遍历，添加，修改，删除的操作思路:

  1. 遍历方法和单向链表一样，只是可以向前，也可以向后查找。

  2. 添加（默认添加到双向链表的最后）：

  • 先找到双向链表的最后这个节点
  • temp.next=newHeroNode；
  • newHeroNode.pre=temp；

  1. 修改思路和原来的单向链表一样。

  2. 删除：

  • 因为是双向链表，因此，我们可以实现自我删除某个节点

  • 直接找到要删除的这个节点，比如temp

  • temp.pre.next=temp.next；

  • temp.next.pre=temp.pre；

代码实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package com.nanzx.linkedlist;

public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 进行测试
		// 先创建节点
		HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
		HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
		HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
		HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");

		// 创建管理链表
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

		// 最后加入
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero4);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);

		// 测试修改节点的代码
//		HeroNode2 newHeroNode = new HeroNode2(1, "小卢", "玉麒麟~~");
//		doubleLinkedList.update(newHeroNode);

		// 测试删除节点的代码
		doubleLinkedList.del(2);
//		doubleLinkedList.del(4);

		doubleLinkedList.list();
	}

}

class DoubleLinkedList {
	private HeroNode2 head = new HeroNode2(0, "", "");

	public HeroNode2 getHead() {
		return head;
	}

	public void add(HeroNode2 heroNode) {
		HeroNode2 temp = head;
		while (true) {
			if (temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		temp.next = heroNode;
		heroNode.pre = temp;
	}

	public void update(HeroNode2 newHeroNode) {
		HeroNode2 temp = head.next;
		while (true) {
			if (temp == null) {
				System.out.println("修改失败，没有找到该节点！");
				break;
			} else if (temp.no == newHeroNode.no) {
				temp.name = newHeroNode.name;
				temp.nickname = newHeroNode.nickname;
				System.out.println("修改成功：" + temp);
				break;
			}
			temp = temp.next;
		}
	}

	public void del(int no) {
		HeroNode2 temp = head.next;
		while (true) {
			if (temp == null) {
				System.out.println("找不到该节点，无法删除！");
				break;
			} else if (temp.no == no) {
				// 判断temp是否为最后一个节点
				if (temp.next != null) {
					temp.next.pre = temp.pre;
				}
				temp.pre.next = temp.next;
				System.out.printf("编号为 %d 的英雄删除成功!\n", no);
				break;
			}
			temp = temp.next;
		}
	}

	public void list() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode2 temp = head.next;
		while (true) {
			// 输出节点的信息
			System.out.println(temp);
			if (temp.next == null) {
				break;
			}
			// 将temp后移
			temp = temp.next;
		}
	}
}

class HeroNode2 {
	// data域
	public int no;
	public String name;
	public String nickname;
	// next域
	public HeroNode2 next;
	// pre域
	public HeroNode2 pre;

	public HeroNode2(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	@Override
	public String toString() {
		return "HeroNode2 [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}