链表概念
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单向链表
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。
头插法和尾插法
头插法：
头插法的实现相对简单 思路是将新形成的节点的下一个赋值为header
再把新形成的节点地址传给header即将header向前移动
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
|
import java.util.Random;
import java.util.Scanner;
public class Link {
int data;
Link next;
static int length=0;
public static Link creat(int len){
Random r=new Random();
Link newnode,header;
header=null;
for (int i = 0; i < len; i++) {
int temp=r.nextInt(100);
newnode=new Link();
length++;
newnode.data=temp;
if(header==null){
header=newnode;
}else{
newnode.next=header;
header=newnode;
}
}
return header;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("输入长度：");
int l=sc.nextInt();
System.out.println("打印数组：");
Link head=Link.creat(l);
for (int i = 0; i < Link.length; i++) {
System.out.print(head.data+" ");
head=head.next;
}
}
}
|
尾插法： 尾插法相对于头插法有些许不同 因为要返回头 头不能动 所以需要一个tailer来记录最后一个值 tailer右移
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
|
import java.util.Random;
import java.util.Scanner;
public class Link {
int data;
Link next;
static int length=0;
public static Link creat(int len){
Random r=new Random();
Link newnode,header,tailer;
header=tailer=null;
for (int i = 0; i < len; i++) {
int temp=r.nextInt(100);
newnode=new Link();
length++;
newnode.data=temp;
if(header==null){
header=tailer=newnode;
}else{
tailer.next=newnode;
tailer=newnode;
}
}
return header;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("输入长度：");
int l=sc.nextInt();
System.out.println("打印数组：");
Link head=Link.creat(l);
for (int i = 0; i < Link.length; i++) {
System.out.print(head.data+" ");
head=head.next;
}
}
}
|
例题
- 找出两个链表的交点
- 链表反转
- 归并两个有序的链表
- 从有序链表中删除重复节点
- 删除链表的倒数第 n 个节点
- 交换链表中的相邻结点
- 链表求和
- 回文链表
- 分隔链表
- 链表元素按奇偶聚集
https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E9%93%BE%E8%A1%A8.md
参考文章:
Java数据结构和算法(七)
java 手动实现单链表（尾插法和头插法）
FROM :blog.cfyqy.com | Author:cfyqy
评论