单链表

用数组模拟单链表用数组效率高

单链表：领接表应用：存储图和树
双链表：优化某些题

单列表：直往后看，不往前看

单链表的几个基本操作：

插入头部
插入第k个数之后
删除第k个点

用下标来关联，空数组的下标是-1

模板

//head 表示头节点的下标
//e[i] 表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx 表示当前以及用到了那个点

void init() {
    head = -1;
    idx = 0;
}

void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; //图中1 注意head表示为头节点的下标
    head = idx; // 头节点下标变为idx，idx称为头节点
    idx++; //idx用过，移到下一个位置
}

//一般操作 插入到k的点后面
void add(int k, int x) {
    e[idx] = x; 
  	ne[idx] = ne[k]; //图1
    ne[k] = idx; //图2
    idx++; 
}


void remove(int k) {
    ne[k] = ne[ne[k]]; //直接让1节点指向3节点
}

题目

AcWing

826 单链表

826

描述

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

解答

import java.util.*;
import java.io.*;


public class Main {
	private static int N = 100010;//数据十万
	
	private static int head;
	private static int[] e = new int[N];
	private static int[] ne = new int[N];
	private static int idx;
    
    //初始化操作
    private static void init(){
        head = -1;
        idx = 0;
    }
    
    //头部插入
    private static void addToHead(int val){
        e[idx] = val; //赋值
        ne[idx] = head; //插入
        head = idx; //头节点信息跟新
        idx++;
    }
    
    //将 val插入下标为 k的点的后面
    private static void add(int k, int val){
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }
    
    //将下标是k的点后面的那个节点删除
    private static void remove(int k){
        ne[k] = ne[ne[k]];
    }

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//m操作数
		int m = Integer.parseInt(br.readLine());
		
		init();
    	while(m-- > 0){
        
            String[] line = br.readLine().split(" ");
			if(line[0].equals("H")) {
            	//插入头部节点
				int val = Integer.parseInt(line[1]);
				addToHead(val);
            }else if (line[0].equals("I")) {
				int k = Integer.parseInt(line[1]);
				int val = Integer.parseInt(line[2]);
				//第一个节点idx 0，第k个节点下标k-1
                add(k-1,val); //注意k这个参数接受的是下标
            }else {
				//line[0] == "D"
				int k = Integer.parseInt(line[1]);
				
				if(k==0){
					head = ne[head];
				}else{
					remove(k-1);
				}
            }
        
        }
    	for(int i = head; i!= -1;i = ne[i]){
			System.out.print(e[i]+" ");
		}
    
    }
}