数据结构篇——链表

数据结构篇——链表

本次我们介绍数据结构中的链表，我们会从下面几个角度来介绍：

• 单链表
• 双链表

单链表

我们会在这里介绍单链表

单链表简介

我们首先来简单介绍一下单链表：

• 单链表就是一条长链，我们会延一个固定的顺序来获得或增添值
• 我们在算法计算中，通常会采用数组来模拟单链表来完成一些操作

单链表的作用：

• 单链表的作用其实是用来设计邻接表，由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];
    }

}

结束语

好的，关于数据结构篇的链表就介绍到这里，希望能为你带来帮助~