数据结构篇——链表
数据结构篇——链表
本次我们介绍基础算法中的区间合并，我们会从下面几个角度来介绍：
- 单链表
- 双链表
单链表
我们会在这里介绍单链表
单链表简介
我们首先来简单介绍一下单链表：
- 单链表就是一条长链，我们会延一个固定的顺序来获得或增添值
- 我们在算法计算中，通常会采用数组来模拟单链表来完成一些操作
单链表的作用：
- 单链表的作用其实是用来设计邻接表，由n个单链表来组成邻接表
- 而邻接表的作用是用来存储后续我们所学习的图和数
单链表基本组成
我们这里的单链表由以下几部分组成：
-
head：头节点，用于存储下一个节点的位置（-1表示空）
-
e[n]: 数据数组，用来存储下标为n的数的值
-
ne[n]：next数组，用来存储第n个数的下一个数的节点坐标
-
idx：当前数的下标，我们通常在使用过一个下标后对idx++来获得一个新的下标
我们给出一张单链表的基本图：
单链表各类操作
首先我们要对单链表进行初始化操作：
public void init(){
head = -1;
idx = 0;
}
其次我们需要对单链表进行添加删除操作：
// 头插法(在第一位增加一个数x)
public void insertHead(int x){
// 我们首先赋值
e[idx] = x;
// 我们将head的值赋给idx的下一位（因为head是第一位的存储点位，我们把idx变为第一位，后续就要存储第二位的存储点位）
ne[idx] = head;
// 我们将head的值变为idx(因为idx变为了第一位，head要指向第一位，所以需要指向idx)
head = idx;
// 记得idx++，使其变为一个新的下标节点
idx++;
}
// 增加操作(在第k位后面增加一个数x)
public void add(int k，int x){
// 我们首先赋值
e[idx] = x;
// 我们让x的下一位变为k的下一位
ne[idx] = ne[k];
// 我们让k的下一位变为idx
ne[k] = idx;
// 记得idx++，使其变为一个新的下标节点
idx++;
}
// 删除操作(删除第k位后面的那个数)
public void delete(int k){
// 我们直接控制k的下一位跳过k的下一位即可(这里会造成内存泄漏，但是由于是算法，我们就不清楚空余出来的idx了)
ne[k] = ne[ne[k]];
}
我们给出相关操作的展示图：
单链表题型展示
我们给出一道简单的单链表题型：
- 实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数
- 删除第k个插入的数后面的数
- 在第k个插入的数后插入一个数
- 现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表
我们给出实际代码：
import java.util.Scanner;
public class TableSingle {
// 设置N，Head，e[]，ne[],idx等
public final static int N = 100010;
public static int head;
public static int idx;
public static int[] e = new int[N];
public static int[] ne = new int[N];
public static void main(String[] args) {
// 首先获得执行次数m
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
init();
while (m-- > 0) {
int k,x;
// 执行操作类型
String op = scanner.next();
// 执行操作
if (op.equals("H")){
x = scanner.nextInt();
insertInHead(x);
}else if (op.equals("I")){
k = scanner.nextInt();
x = scanner.nextInt();
add(k-1,x);
}else if (op.equals("D")){
k = scanner.nextInt();
// 注意：这里如果k==0，需要删除第一个点
if (k == 0)
head = ne[head];
else
delete(k - 1);
}
}
// 输出一下
int i = head;
while (i != -1) {
System.out.print(e[i] + " ");
i = ne[i];
}
}
/**
* 初始化
*/
public static void init(){
head = -1;
idx = 0;
}
/**
* 头插法
* @param x
*/
public static void insertInHead(int x){
// 我们首先赋值
e[idx] = x;
// 我们将head的值赋给idx的下一位（因为head是第一位的存储点位，我们把idx变为第一位，后续就要存储第二位的存储点位）
ne[idx] = head;
// 我们将head的值变为idx(因为idx变为了第一位，head要指向第一位，所以需要指向idx)
head = idx;
// 记得idx++，使其变为一个新的下标节点
idx++;
}
/**
* 添加操作
* @param k
* @param x
*/
public static void add(int k,int x){
// 我们首先赋值
e[idx] = x;
// 我们让x的下一位变为k的下一位
ne[idx] = ne[k];
// 我们让k的下一位变为idx
ne[k] = idx;
// 记得idx++，使其变为一个新的下标节点
idx++;
}
/**
* 删除操作
* @param k
*/
public static void delete(int k){
// 我们直接控制k的下一位跳过k的下一位即可(这里会造成内存泄漏，但是由于是算法，我们就不清楚空余出来的idx了)
ne[k] = ne[ne[k]];
}
}
双链表
我们会在这里介绍双链表
双链表简介
我们首先来简单介绍一下双链表：
- 单链表就是一条长链，我们在表中的值的两侧都具有一个可以传到下一个点的链条
- 我们在算法计算中，通常会采用数组来模拟单链表来完成一些操作
双链表的作用：
- 通常是用来优化某些问题
双链表基本组成
我们这里的双链表由以下几部分组成：
-
head：头节点，下标为0
-
tail：尾节点，下标为1
-
e[n]: 数据数组，用来存储下标为n的数的值
-
le[n]:存储该点左侧的下标
-
re[n]:存储该点右侧的下标
-
idx：当前数的下标，我们通常在使用过一个下标后对idx++来获得一个新的下标
我们给出一张双链表的基本图：
双链表各类操作
首先我们要对双链表进行初始化操作：
public static void init(){
head = 0;
tail = 1;
r[head] = 1;
l[tail] = 0;
}
我们这里给出双链表的一种添加和删除操作：
// 在k的右侧添加x
public static void add(int k,int x){
// 赋值
e[idx] = x;
// 我们依次修改三个点之间的四条链的指向方向即可（可以画图~）
r[idx] = r[k];
l[idx] = k;
l[r[idx]] = idx;
r[k] = idx;
// 记得idx++
idx++;
}
// 删除第k个点
public static void delete(int k){
// 我们只需要修改k左右两侧的点不指向k即可
l[r[k]] = l[k];
r[l[k]] = r[k];
}
双链表题型展示
我们给出一道简单的双链表题型：
-
实现一个双链表，双链表初始为空，支持5种操作：
-
在最左侧插入一个数；
-
在最右侧插入一个数；
-
将第k个插入的数删除；
-
在第k个插入的数左侧插入一个数；
-
在第k个插入的数右侧插入一个数
-
现在要对该链表进行m次操作，进行完所有操作后，从左到右输出整个链表。
我们给出实际代码：
import java.util.Scanner;
public class TableDouble {
// 创建初始值
public static final int N = 100010;
public static int idx;
public static int head;
public static int tail;
public static int[] e = new int[N];
public static int[] l = new int[N];
public static int[] r = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
init();
while(m -- > 0){
String s = scan.next();
char op = s.charAt(0);
if(op == 'L'){
int x = scan.nextInt();
addInRight(head,x);
}else if(op == 'R'){
int x = scan.nextInt();
addInRight(l[tail],x);
}else if(op == 'D'){
int k = scan.nextInt();
delete(k + 1);
}else if(s.equals("IR")){
int k = scan.nextInt();
int x = scan.nextInt();
addInRight(k + 1,x);
}else {
int k = scan.nextInt();
int x = scan.nextInt();
addInRight(l[k+1],x);
}
}
for(int i = r[0];i != 1; i= r[i]){
System.out.print(e[i] + " ");
}
}
/**
* 初始化
*/
public static void init(){
head = 0;
tail = 1;
idx = 2;
r[head] = tail;
l[tail] = head;
}
/**
* 在k的右侧添加x
* @param k
* @param x
*/
public static void addInRight(int k,int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[idx]] = idx;
r[k] = idx;
idx++;
}
/**
* 删除k
* @param k
*/
public static void delete(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
}
结束语
好的，关于数据结构篇的链表就介绍到这里，希望能为你带来帮助~
