首页 > 其他分享 >数据结构篇——链表

数据结构篇——链表

时间:2022-11-11 08:11:17浏览次数:46  
标签:head idx int ne 链表 static 数据结构 public

数据结构篇——链表

本次我们介绍基础算法中的区间合并,我们会从下面几个角度来介绍:

  • 单链表
  • 双链表

单链表

我们会在这里介绍单链表

单链表简介

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

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

单链表的作用:

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

}

结束语

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

标签:head,idx,int,ne,链表,static,数据结构,public
From: https://www.cnblogs.com/qiuluoyuweiliang/p/16879417.html

相关文章

  • 循环双向链表实现
    双向链表实现链表结点定义双向链表节点定义由一个数据域和两个指针域组成。template<typenameT>classList_Node{public: typedefList_Node<T>*link_node;publi......
  • 力扣203 移除链表元素
    题目:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例:输入:head=[1,2,6,3,4,5,6],val=6输......
  • 142.环形链表 II
    给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环......
  • 【数据结构-树】树及森林的定义
    目录1双亲表示法2孩子表示法2.1孩子表示法2.2双亲孩子表示法3孩子兄弟表示法1双亲表示法dataparent存储某个结点的数据信息存储该结点的双亲所在数组中......
  • Redis数据结构简介-Set
     Set结构存储值与结构读写能力:包含字符串的无序收集器(unorderedcollection),且数据不重复.添加,获取,移除单个元素;检查一个元素是否存在于集合中;......
  • Redis数据结构简介-Hash
     Hash结构存储值与结构读写能力:包含键值对的无序散列表添加,获取,移除单个键值对;获取所有键值对.存储类似HashMap的数据 hash是日常开发过......
  • Redis数据结构简介-List
     List结构存储值与结构读写能力:一个链表,链表上的每个节点都包含了一个字符串从链表的两端推入或者弹出元素;根据偏移量对链表进行修剪(trim);读取单......
  • 数据结构:线性表
    线性表分类区别​顺序表一般是使用数组存储的,存储空间是连续的;​链式表一般是使用指针,将一个个结点联系起来。结点有数据域和指针域,数据域用来存储数据,指针域用......
  • 有点私心,记录一下课后的学习笔记(数据结构)
    2022.11.09课后——数据结构笔记主要分为两部分,第一部分关于拓扑排序;第二部分关于关键路径拓扑排序(AOV-网的相关基本思路)利用图进行拓扑排序(排序结果不唯一)首先找到图......
  • python的数据结构之栈
    栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。由于栈具有后入先出的特点,所以任何不在栈顶......