如何实现单链表 如何实现单链表？

发表于

如何实现单链表？

这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战

笔者最近在学习《数据结构与算法之美》，正好借着这个机会边练习边记录一下自己学习的知识点。不啰嗦，直接开始。

一、什么是链表

链表和数组一样都是线性的数据结构。

链表由一个一个的结点连接组成，结点又由数据域和指针域两部分组成。数据域存储数据，指针域存储指向下一个结点的指针（或者叫引用）。

正是因为使用指针指向下一个结点，所以链表可以将零散的内存空间串联起来。

常见的链表有：单链表、循环链表、双链表和双向循环链表等等。
链表及常见类型 - 副本.png

二、链表的特点

  • 链表查询时间复杂度 O(n)，删除插入时间复杂度 O(1) ：因为链表使用指针指向下一个结点，所以当想要查询某个结点时，只能从第一个结点依次进行遍历，直到目标结点。但删除和插入只需要将指针指向新结点即可。
  • 链表与数组相比，需要额外的内存空间：因为除了数据存储的空间之外，还存储了指向下一结点指针。

三、单链表实现

单链表的实现有两个难点：一个是插入结点操作，另一个是删除结点操作。

3.1 插入

单链表的插入有三种方式，一个是插入到链表头部、二是插入到链表尾部、三是在链表两个结点直接插入新结点。

插入到链表头部只需要将新结点的指针指向头结点，再将新结点设置为头结点即可。

头插法.png

插入到链表尾部，需要先遍历到链表的尾结点，在将尾结点的指针指向新结点即可。

尾插法.png

链表两个结点直接插入新结点，例如将结点 p 插入到结点 a 和 结点 b之间，先将结点 p.next 指向结点 b，在将结点 a.next 结点 p。

插入两个结点之间.png

3.2 删除

删除链表中的某个结点，例如删除结点 c 。先找到结点 c 的前驱结点 b，将 b.next = b.next.next即可。

删除结点.png

3.3 具体实现

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
java复制代码/**
 * @author xuls
 * @date 2021/11/9 20:49
 * 单链表
 */
public class SingleLinkedList {
	/**
	 * 存储字符串数据的结点类
	 */
	private static class Node{
		private String data;
		private Node next;//指向下一个结点

		public Node(String data, Node next) {
			this.data = data;
			this.next = next;
		}

		@Override
		public String toString() {
			return "Node{" +
					"data='" + data + '\'' +
					'}';
		}
	}

	private Node head;//头结点

	//将数据插入到单链表头部
	public void insertHead(String data){
		Node node = new Node(data, null);
		//如果头结点为 null 则直接插入
		if (head == null){
			head = node;
		}else {
			//将结点的 next 指向 head，再将 node 设置为 head
			node.next = head;
			head = node;
		}
	}

	//将数据插入到单链表尾部
	public void insertTail(String data){
		Node node = new Node(data, null);
		//如果头结点为 null 直接插入
		if (head == null){
			head = node;
		}else {
			Node temp = head;
			//找到指向下一个结点为 null 的结点，这个结点即最后一个结点
			while ( temp.next != null){
				temp = temp.next;
			}
			//将最后一个结点的下一个结点指向新结点
			temp.next = node;
		}
	}

	// 将 data 插入到 node 结点之前
	public void insertBefore(String data,Node node){
		if (node == null){
			return;
		}
		//插入头结点之前
		if (node == head){
			insertHead(data);
			return;
		}

		//找到插入结点的前结点
		Node before = head;
		while (before != null && before.next != node){
			before = before.next;
		}

		if (before == null){
			//说明 node 结点不在单链表中直接返回
			return;
		}

		Node newNode = new Node(data, null);
		newNode.next = node;
		before.next = newNode;
	}

	// 将 data 插入到 node 结点之后
	public void insertAfter(String data,Node node){
		if (node == null){
			return;
		}
		Node newNode = new Node(data, null);
		newNode.next = node.next;
		node.next = newNode;
	}

	//删除结点
	public void delete(Node node){
		if (node == null || head == null){
			return;
		}
		if (node == head){
			head = head.next;
			return;
		}
		//找到删除结点的前结点
		Node before = head;
		while (before != null && before.next != node){
			before = before.next;
		}
		
		if (before == null){
			//删除结点不在链表之中
			return;
		}
		
		before.next = before.next.next;
	}

	//找到 index 位置的结点
	public Node find(int index){
		if (head == null || index < 0){
			return null;
		}
		
		Node node = head;
		int position = 0;
		while (node != null && position != index){
			node = node.next;
			position++;
		}

		return node;
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("SingleLinkedList：");
		if (head == null){
			builder.append("null");
		}else {
			Node node = head;
			while (node != null){
				builder.append(node.data).append("-->");
				node = node.next;
			}
			builder.append("null");
		}
		return builder.toString();
	}
}

四、数组 or 链表

数组和链表是常见的基本数据结构，两者经常放在一起进行比较，同样是线性数据结构我们如何进行选择？

4.1 随机访问、插入、删除时间复杂度

随机访问 删除、插入
数组 O(1) O(n)
链表 O(n) O(1)

4.2 数组存储 vs 链表存储

数组需要连续的内存空间，比如你需要申请 99 M 大小的内存空间，但没有 99 M 的连续内存空间了，数组创建就会失败。

数组连续的内存空间可以利用 CPU 的缓存机制，使得数据访问更快。

数组的大小固定，虽然我们可以实现动态扩容的数组，但是频繁的数据搬移也是非常耗时的。

链表使用指针将不连续的内存空间连接在一起，但这就需要使用额外的内存空间存储指向下一结点的指针。链表频繁的创建对象也可能产生内存碎片。

综上根据你的需要，具体问题具体分析。

传送门：如何实现动态扩容的数组

XDM，动动小手点赞评论，求求了。

catdan.gif

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%