链表

admin 2022年1月6日01:36:40安全博客评论12 views2753字阅读9分10秒阅读模式

链表概念

 链表(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;
/**
* 创建一个链表
* @param len 产生数据的长度
* @return 链表第一个节点地址
*/
public static Link creat(int len){
//定义随机对象
Random r=new Random();
//定义链表的节点
Link newnode,header;
//header永远存储第一个节点的地址,tailer永远存储最后一个节点的地址
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永远存储第一个节点的地址
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("打印数组:");
//调用数组生成方法 传入键盘值l
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;
/**
* 创建一个链表
* @param len 产生数据的长度
* @return 链表第一个节点地址
*/
public static Link creat(int len){
//定义随机对象
Random r=new Random();
//定义链表的节点
Link newnode,header,tailer;
//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永远存储最后一个节点的地址
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("打印数组:");
//调用数组生成方法 传入键盘值l
Link head=Link.creat(l);
for (int i = 0; i < Link.length; i++) {
System.out.print(head.data+" ");
//把当前对象的下一个对象地址传给当前对象
head=head.next;
}
}
}

例题

  1. 找出两个链表的交点
  2. 链表反转
  3. 归并两个有序的链表
  4. 从有序链表中删除重复节点
  5. 删除链表的倒数第 n 个节点
  6. 交换链表中的相邻结点
  7. 链表求和
  8. 回文链表
  9. 分隔链表
  10. 链表元素按奇偶聚集

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

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:36:40
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  链表 http://cn-sec.com/archives/721958.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: