单链表

                     

贡献者: 有机物

   链表是一种用于存储数据的链式数据结构,形如一条链子一样来连接元素,通常用于存储树和图。

   与数组不同的是:数组是一种支持随机访问,但不支持在任意位置插入或删除元素的数据结构。但链表支持在任意位置插入或删除,但只能按顺序依次访问其中的元素。

   单链表:

图
图 1:单链表示意图

   可以看到,链表上每个结点都有三个值,分别为:下标、值和 $\text{next}$ 指针。

   下标为 $3$ 的结点的下一个结点为空结点,所以 $\text{next}$ 值为 $-1$。

   如果用 C++ 的指针和结构体来写链表的话,长成这样子:

struct List
{
    int value;
    List *next;
};

   一般在竞赛中很少用上面这种方式来实现链表,因为这种写法效率很低,所以这里我们来讲一下如何使用数组来模拟链表。

   数组模拟单链表需要这么几个数组和变量:

int e[N], ne[N], head, idx;
// N 表示数组的大小
// head 表示头结点的下标
// idx 表示是第几个插入的数,后续模拟一下链表就懂了
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少

   单链表通常有这么几个操作:

  1. 向链表头插入一个数;
  2. 删除第 $k$ 个插入的数后面的数;
  3. 在第 $k$ 个插入的数后插入一个数。

   我们来模拟一个样例来更好的理解单链表,如要进行如下这些操作:

  1. 先在链表头插入一个数 $9$
  2. 在第 $1$ 个插入的数后面再插入一个数 $1$
  3. 删除第一个插入的数的后面的一个数
  4. 删除头结点后面的数
  5. 在链表头插入一个数 $6$
  6. 在第 $3$ 个插入的数后面再插入一个数 $6$
  7. 在第 $4$ 个插入的数后面再插入一个数 $5$
  8. 在第 $4$ 个插入的数后面再插入一个数 $5$
  9. 在第 $3$ 个插入的数后面再插入一个数 $4$
  10. 删除第 $6$ 个插入的数的后面一个数

   我们来借助几张图片来模拟一下上面的 $10$ 个操作

图
图 2:执行 $1\sim3$ 次操作
图
图 3:执行 $4\sim7$ 次操作
图
图 4:执行 $8\sim9$ 次操作

   经过模拟了 $10$ 次单链表的操作,就可以理解单链表的执行过程了,让我们来看看这些操作具体怎么写。

   第一个操作向头结点插入一个数

   代码如下:

void add_to_head(int x) 
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}
// 熟练掌握了之后就可以写成一行了。

e[idx] = x, ne[idx] = head, head = idx ++ ;

图
图 5:向头结点插入一个数

   第二个操作:在第 $k$ 个插入的数后插入一个数

   代码如下:

void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

   插入方式和插入一个数到头结点的后面类似,这里就再不详讲了。

   第三个操作:删除一个点的后面一个点

   代码如下:

// 删除第 k 个插入的点的后面一个点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

// 删除头结点:head = ne[head]

图
图 6:删除一个点

   到目前为止,单链表的基本操作就讲完了。


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利