单向链表

链表(Linked List)介绍

链表在内存中的存储

特点

  • 链表是以节点的方式来存储,是链式存储
  • 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
  • 链表的各个节点不一定是连续存储的
  • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

带头结点的单列表逻辑示意图

单向链表的优缺点

和普通的线性结构（如数组）相比，链表结构有以下特点：
（1）单个结点创建非常灵活，普通的线性内存通常在创建的时候就需要设定数据的大小
（2）结点的删除、插入非常方便，不需要像线性结构那样移动剩下的数据
（3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

实现思路(实现链表的增删改查)

创建（添加）

  • 先创建一个Head头节点，表示单链表的头
  • 后面我们每添加一个节点，就放在链表的最后

遍历

通过一个辅助变量，来遍历整个链表

有序插入

  • 先遍历链表，找到应该插入的位置
  • 要插入的节点的next指向插入位置的后一个节点
  • 插入位置的前一个节点的next指向要插入节点
    • 插入前要判断是否在队尾插入

根据某个属性节点修改值

  • 先遍历节点，找到修改的位置
    • 如果未找到修改节点，则不修改

删除某个节点

  • 先遍历节点，找到要删除节点的前一个节点
  • 进行删除操作

求倒数第n个节点的信息

  • 遍历链表，求出链表的有效长度length（不算头结点）
  • 遍历链表到第length-n的节点

翻转链表

  • 创建一个新的头结点，作为新链表的头

  • 从头遍历旧链表，将遍历到的节点插入新链表的头结点之后

  • 注意需要用到

    两个暂存节点

    • 一个用来保存正在遍历的节点
    • 一个用来保存正在遍历节点的下一个节点

img

img

img

img

逆序打印

  • 遍历链表，将遍历到的节点入栈
  • 遍历完后，进行出栈操作，同时打印出栈元素

代码

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
public class Demo1 {
	public static void main(String[] args) {
		LinkedList linkedList = new LinkedList();
		linkedList.traverseNode();
		System.out.println();
		//创建学生节点，并插入链表
		StudentNode student1 = new StudentNode(1, "Nyima");
		StudentNode student3 = new StudentNode(3, "Lulu");
		linkedList.addNode(student1);
		linkedList.addNode(student3);
		linkedList.traverseNode();
		System.out.println();

		//按id大小插入
		System.out.println("有序插入");
		StudentNode student2 = new StudentNode(0, "Wenwen");
		linkedList.addByOrder(student2);
		linkedList.traverseNode();
		System.out.println();

		//按id修改学生信息
		System.out.println("修改学生信息");
		student2 = new StudentNode(1, "Hulu");
		linkedList.changeNode(student2);
		linkedList.traverseNode();
		System.out.println();

		//根据id删除学生信息
		System.out.println("删除学生信息");
		student2 = new StudentNode(1, "Hulu");
		linkedList.deleteNode(student2);
		linkedList.traverseNode();
		System.out.println();

		//获得倒数第几个节点
		System.out.println("获得倒数节点");
		System.out.println(linkedList.getStuByRec(2));
		System.out.println();

		//翻转链表
		System.out.println("翻转链表");
		LinkedList newLinkedList = linkedList.reverseList();
		newLinkedList.traverseNode();
		System.out.println();

		//倒叙遍历链表
		System.out.println("倒序遍历链表");
		newLinkedList.reverseTraverse();

	}
}

/**
 * 创建链表
 */
class LinkedList {
	//头节点，防止被修改，设置为私有的
	private StudentNode head = new StudentNode(0, "");

	/**
	 * 添加节点
	 * @param node 要添加的节点
	 */
	public void addNode(StudentNode node) {
		//因为头节点不能被修改，所以创建一个辅助节点
		StudentNode temp = head;
		//找到最后一个节点
		while (true) {
			//temp是尾节点就停止循环
			if(temp.next == null) {
				break;
			}
			//不是尾结点就向后移动
			temp = temp.next;
		}
		//现在temp是尾节点了，再次插入
		temp.next = node;
	}

	/**
	 * 遍历链表
	 */
	public void traverseNode() {
		System.out.println("开始遍历链表");
		if(head.next == null) {
			System.out.println("链表为空");
		}
		//创建辅助节点
		StudentNode temp = head.next;
		while(true) {
			//遍历完成就停止循环
			if(temp == null) {
				break;
			}
			System.out.println(temp);
			temp = temp.next;
		}
	}

	/**
	 * 按id顺序插入节点
	 * @param node
	 */
	public void addByOrder(StudentNode node) {
		//如果没有首节点，就直接插入
		if(head.next == null) {
			head.next = node;
			return;
		}
		//辅助节点，用于找到插入位置和插入操作
		StudentNode temp = head;
		//节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
		while (temp.next!=null && temp.next.id < node.id) {
			temp = temp.next;
		}
		//如果temp的下一个节点存在，则执行该操作
		//且插入操作，顺序不能换
		if(temp.next != null) {
			node.next = temp.next;
		}
		temp.next = node;
 	}

	/**
	 * 根据id来修改节点信息
	 * @param node 修改信息的节点
	 */
 	public void changeNode(StudentNode node) {
		if(head == null) {
			System.out.println("链表为空，请先加入该学生信息");
			return;
		}
		StudentNode temp = head;
		//遍历链表，找到要修改的节点
		while (temp.next!= null && temp.id != node.id) {
			temp = temp.next;
		}
		//如果temp已经是最后一个节点，判断id是否相等
		if(temp.id != node.id) {
			System.out.println("未找到该学生的信息，请先创建该学生的信息");
			return;
		}
		//修改学生信息
		temp.name = node.name;
	}

	/**
	 * 根据id删除节点
	 * @param node 要删除的节点
	 */
	public void deleteNode(StudentNode node) {
 		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
 		StudentNode temp = head.next;
 		//遍历链表，找到要删除的节点
 		if(temp.next!=null && temp.next.id!=node.id) {
 			temp = temp.next;
		}
 		//判断最后一个节点的是否要删除的节点
 		if(temp.next.id != node.id) {
			System.out.println("请先插入该学生信息");
			return;
		}
 		//删除该节点
 		temp.next = temp.next.next;
	}

	/**
	 * 得到倒数的节点
	 * @param index 倒数第几个数
	 * @return
	 */
	public StudentNode getStuByRec(int index) {
		if(head.next == null) {
			System.out.println("链表为空!");
		}
		StudentNode temp = head.next;
		//用户记录链表长度，因为head.next不为空，此时已经有一个节点了
		//所以length初始化为1
		int length = 1;
		while(temp.next != null) {
			temp = temp.next;
			length++;
		}
		if(length < index) {
			throw new RuntimeException("链表越界");
		}

		temp = head.next;
		for(int i = 0; i<length-index; i++) {
			temp = temp.next;
		}
		return temp;
	}

	/**
	 * 翻转链表
	 * @return 反转后的链表
	 */
	public LinkedList reverseList() {
		//链表为空或者只有一个节点，无需翻转
		if(head.next == null || head.next.next == null) {
			System.out.println("无需翻转");
		}
		LinkedList newLinkedList = new LinkedList();
		//给新链表创建新的头结点
		newLinkedList.head = new StudentNode(0, "");
		//用于保存正在遍历的节点
		StudentNode temp = head.next;
		//用于保存正在遍历节点的下一个节点
		StudentNode nextNode = temp.next;
		while(true) {
			//插入新链表
			temp.next = newLinkedList.head.next;
			newLinkedList.head.next = temp;
			//移动到下一个节点
			temp = nextNode;
			nextNode = nextNode.next;
			if(temp.next == null) {
				//插入最后一个节点
				temp.next = newLinkedList.head.next;
				newLinkedList.head.next = temp;
				head.next = null;
				return newLinkedList;
			}
		}
	}

	public void reverseTraverse() {
		if(head == null) {
			System.out.println("链表为空");
		}

		StudentNode temp = head.next;
		//创建栈，用于存放遍历到的节点
		Stack<StudentNode> stack = new Stack<>();
		while(temp != null) {
			stack.push(temp);
			temp = temp.next;
		}

		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}
}

/**
 * 定义节点
 */
class StudentNode {
	int id;
	String name;
	//用于保存下一个节点的地址
	StudentNode next;

	public StudentNode(int id, String name) {
		this.id = id;
		this.name = name;
	}

	@Override
	public String toString() {
		return "StudentNode{" +
				"id=" + id +
				", name='" + name + '\'' +
				'}';
	}
}

结果

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
开始遍历链表
链表为空

开始遍历链表
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}

有序插入
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}

修改学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Hulu'}
StudentNode{id=3, name='Lulu'}

删除学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}

获得倒数节点
StudentNode{id=0, name='Wenwen'}

翻转链表
开始遍历链表
StudentNode{id=3, name='Lulu'}
StudentNode{id=0, name='Wenwen'}

倒序遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}

双向链表

img

实现思路

遍历

  • 和单向链表的遍历相同，需要一个辅助节点来保存当前正在遍历的节点

添加

  • 双向链表多出了一个frnot，所以在添加时，要让新增节点的front指向链表尾节点

修改

  • 和单向链表的修改相同

删除

  • 使用temp来保存要删除的节点
  • temp.pre.next指向temp.next
  • temp.next指向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
129
130
131
132
133
134
public class Demo2 {
    public static void main(String[] args) {
        BidirectionalList bidirectionalList = new BidirectionalList();
        bidirectionalList.addNode(new PersonNode(1, "Nyima"));
        bidirectionalList.addNode(new PersonNode(2, "Lulu"));
        bidirectionalList.traverseNode();
        System.out.println();

        System.out.println("修改节点信息");
        bidirectionalList.changeNode(new PersonNode(2, "Wenwen"));
        bidirectionalList.traverseNode();
        System.out.println();

        //删除节点
        System.out.println("删除节点");
        bidirectionalList.deleteNode(new PersonNode(1, "Nyima"));
        bidirectionalList.traverseNode();
    }
}

class BidirectionalList {
    private final PersonNode head = new PersonNode(-1, "");

    /**
    * 判断双向链表是否为空
    * @return 判空结果
    */
    public boolean isEmpty() {
        return head.next == null;
    }

    /**
    * 添加将诶点
    * @param node 要被添加的节点
    */
    public void addNode(PersonNode node) {
        PersonNode temp = head;
        if(temp.next != null) {
            temp = temp.next;
        }
        //插入在最后一个节点的后面
        temp.next = node;
        node.front = temp;
    }

    public void traverseNode() {
        System.out.println("遍历链表");
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        PersonNode temp = head.next;
        while(temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
    * 修改节点信息
    * @param node 要修改的节点
    */
    public void changeNode(PersonNode node) {
        if(isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        PersonNode temp = head.next;
        //用于判定是否做了修改
        boolean flag = false;
        while (temp != null) {
            if(temp.id == node.id) {
                //匹配到节点，替换节点
                temp.front.next = node;
                node.next = temp.next;
                flag = true;
            }
            temp = temp.next;
        }
        if(!flag) {
            System.out.println("未匹配到改人信息");
        }

    }

    /**
    * 删除节点
    * @param node 要删除的节点
    */
    public void deleteNode(PersonNode node) {
        if(isEmpty()){
            System.out.println("链表为空");
            return;
        }
        PersonNode temp = head.next;
        //查看是否删除成功
        boolean flag = false;
        while(temp != null) {
            if(temp.id == node.id) {
                temp.front.next = temp.next;
                temp.next = null;
                flag = true;
            }
            temp = temp.next;
        }
        if(!flag) {
            System.out.println("未找到该节点");
        }
    }


}

class PersonNode {
    int id;
    String name;
    //指向下一个节点
    PersonNode next;
    //指向前一个节点
    PersonNode front;

    public PersonNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "PersonNode{" +
            "id=" + id +
            ", name='" + name + '\'' +
            '}';
    }
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Lulu'}

修改节点信息
遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Wenwen'}

删除节点
遍历链表
PersonNode{id=2, name='Wenwen'}

>

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=39jvp4pqpw2ss