单链表定义

  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。 链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

  • 大概来讲,就是由一个个结点(里面包含数据,和记录下一个结点的标识),连接而成的一条链子。

  • image.png

静态单链表

  • 通过静态的数组,来模拟内存分配。这样就省去动态内存分配所耗费的时间。

  • 变量介绍

    • head -> 指向链表的头
    • e[i] -> 存储 i 这个结点的值
    • ne[i] -> 后继 也就是 i 所连接的下一个点 位置
    • idx -> 用来模拟内存分配,idx 值表示下一个该分配的地址。
  • 单链表的操作

    • 定义单链表
      • 	const int N = 100005;
        	int head, e[N], ne[N], idx;
        	// 初始链表
        	init() {
        		head = -1; // 链表没有结点指向 -1
        		idx = 0;  // 从数组第 0 个位置开始分配空间,idx <= N;
        	}
        
    • 实现链表插入
      • image.png
      • 	// 在 链表中 第 k 个结点 后面插入 一个结点
        	insert(int k, int x){
        		e[idx] = x; // 为 这个结点 分配 空间
        
        		ne[idx] = ne[k]; // 将 原来 k 所指向的 后继 赋值 给插入点的 后继
        
        		ne[k] = idx; // 将 k 的后继 更新成 插入的这个点
        
        		idx ++; // 将 idx +1 ,指向下一待分配数组的下标
        	}
        
    • 在链表头部插入
      • 已知 head 指向的是链表头部, head 可以当成一个结点,但是它没有值,可以参考上面的,进行插入。
      • 	insertToHead(int x) {
        		e[idx] = x;
        		ne[idx] = head;
        		head = idx; // 将链表头结点更新成 新插入的这个点。
        		idx ++;
        	}
        
    • 删除操作
      • image.png
      • 
        	// 删除第 k 个 插入的结点的后面一个结点
        	remove(int k) {
        		ne[k] = ne[ne[k]];
        	}
        
    • 遍历单链表
      • 已知链表没有后继 则指向 -1,通过这个属性可以遍历整个链表
      • 	for (int i = head; i != -1; i = ne[i]) {
        		printf("%d ",e[i]);
        	}