链表
为什么使用数组来模拟链表
如果数据规模很大, 一个一个的new操作太慢了, 会超时, 使用数组会大大加快速度
单链表
数组模拟单链表
**idx = 0开始的, 所以第k个元素的下标就是 k-1 传值的时候要注意 **
–
例题
例题 :
单链表
实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；
删除第 k 个插入的数后面的数；
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6
输出样例：
6 4 6 5
java代码
import java.io.*;
import java.util.Scanner;
public class Main {
private static int N = 100010; // 数据规模为 10w
private static int head; // 表示头结点的下标
private static int[] e = new int[N]; // 表示结点 i的值
private static int[] ne = new int[N]; // 表示结点 i的 next指针是多少
private static int idx; // 表示存储当前结点已经使用结点的下一个结点
// 初始化数据
private static void init() {
head = -1; // 没有头结点
idx = 0; // 没有存入数据
}
// 将 val插到头结点
private static void addToHead(int val) {
e[idx] = val; // 赋值
ne[idx] = head; // 插入之前头结点的前面
head = idx; // 更新头结点信息
idx++; // idx向右移动
}
// 将下标是 k的点后面的点删掉
private static void remove(int k) {
ne[k] = ne[ne[k]]; // 让下标为 k的结点指向 下个结点的下个结点
}
// 将 val插入下标为 k的点的后面
private static void add(int k, int val) {
e[idx] = val;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 程序入口
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(reader.readLine());
init(); // 初始化操作
// 进行 m次操作
while (m-- > 0) {
String[] s = reader.readLine().split(" ");
if (s[0].equals("H")) { // 插入头结点操作, 不能使用 ==, 要使用 equals()
int val = Integer.parseInt(s[1]);
addToHead(val);
} else if (s[0].equals("I")) { // 普通插入操作
int k = Integer.parseInt(s[1]);
int val = Integer.parseInt(s[2]);
add(k - 1, val); // 第 k个结点的下标为 k-1, 所以插入到下标为 k-1结点的后面
} else { // s[0] == "D", 删除操作
int k = Integer.parseInt(s[1]);
if (k == 0) { // 题意: k = 0, 删除头结点
head = ne[head];
} else
remove(k - 1); // 第 k个结点的下标为 k-1, 所以是删除到下标为 k-1后面的后面
}
}
// 打印输出
for (int i = head; i != -1; i = ne[i]) {
System.out.print(e[i] + " ");
}
}
}
双链表
实现双链表的基本操作 :
首先是结构 以及初始化操作
–为什么没有头呢 ?
这里使用下标为 0 作为头结点 下标为 1 作为尾结点
所以初始化的时候就要注意了 先将 0 和 1 连接起来
–插入删除操作
插入的话 其实不分最左还是左右 以及在k的左还是右插入 统统一个方法即可 实现在k的右边插入
最左插入的话就是在不断的在0的右边插入
最右插入的话就是在不断的在1的左边的值的右边插入
删除的话就好说了
!!!**还有就是因为 idx是从 2 开始的 所以第k个元素的下标就是 k+1 **
//IL IR 第k个数右插入 public static void insert(int k , int x){ e[idx] = x; re[idx] = re[k]; le[idx] = k; le[re[k]] = idx; //先 re[k] = idx; //后 idx++; } //del 删除第k个数 public static void del(int k ){ re[le[k]] = re[k]; le[re[k]] = le[k]; }
遍历输出 注意遍历输出的for写法
for(int i= re[0];i!=1;i = re[i]){ System.out.print(e[i]+" "); }
例题
双链表
实现一个双链表，双链表初始为空，支持 5 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。数据范围
1≤M≤100000
所有操作保证合法。输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2
java代码
import java.util.*;
public class Main{
static int[] e = new int[100010]; //存放具体的值
static int[] le = new int [100010 ]; //左值的下标
static int[] re = new int [100010 ]; //左值的下标
static int idx = 0; //当前操作的索引
//初始化
public static void init(){
//这里的话 直接使用0号点做为head 使用=1号点做为tail
//给0 1 初始化
re[0] = 1;
le[1] = 0;
idx = 2; //0 1 被占用了所以从2号点开始
}
//IL IR 第k个数右插入
public static void insert(int k , int x){
e[idx] = x;
re[idx] = re[k];
le[idx] = k;
le[re[k]] = idx; //先
re[k] = idx; //后
idx++;
}
//del 删除第k个数
public static void del(int k ){
re[le[k]] = re[k];
le[re[k]] = le[k];
}
public static void main(String[] args){
init(); //切记要初始化嗷嗷 !!!!!
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n-- >=0){
String s = sc.nextLine();
//System.out.println(s);
String[] s1 = s.split(" ");
if(s1[0].equals("R")){
//执行最右插入 k就是1的左边
int k = le[1];
int x = Integer.parseInt(s1[1]);
insert(k,x);
}
if(s1[0].equals("L")){
//执行最左插入 就是0的右边
int k = 0;
int x = Integer.parseInt(s1[1]);
insert(k,x);
}
if(s1[0].equals("D")){
//执行删除
del(Integer.parseInt(s1[1])+1);
}
if(s1[0].equals("IL")){
int k = Integer.parseInt(s1[1]);
int x = Integer.parseInt(s1[2]);
insert(le[k+1],x);
}
if(s1[0].equals("IR")){
int k = Integer.parseInt(s1[1]);
int x = Integer.parseInt(s1[2]);
insert(k+1,x);
}
}
for(int i= re[0];i!=1;i = re[i]){
System.out.print(e[i]+" ");
}
}
}