一、定义和要实现的操作

线性表的定义很简单，只需要将一些数据串起来即可
image.png
对于这样一种数据结构，应该实现的操作有哪些？

  • InitList(*L)：初始化操作，建立一个空的线性表L
  • ListEmpty(L)：查看线性表是否为空。若线性表为空，返回true，否则返回false
  • ClearList(*L)：将线性表清空
  • GetElem(L, i, *e)：将线性表L的第i个元素值返回给e
  • LocateElem(L, e)：将线性表L中查找与给定值e相等的元素。如果查找成功，返回该元素在表中序号；否则，返回0表示查找失败。
  • ListInsert(*L, i, e)：在线性表L中的第i个位置插入新元素e
  • ListDelete(*L, i, *e)：删除线性表L中第i个位置元素，并用e返回其值
  • ListLength(L)：返回线性表L的元素个数

    二、两种存储方式

    在计算机里，最主要的两种存储方式为链式存储和顺序存储，链表用这两种存储方式都可以实现，就像下面这张图表示的一样。
    image.png

    三、链表的几种类型

    上面根据存储方式定义的两种链表类型，接下来换一个角度，从链表的方向上看一下链表有几种：

3.1 单链表

最简单的应该就是单链表了，它只需要指向下一个数据就行
image.png

3.2 双向链表

单链表是单向的，那双向链表就是双向的了
image.png

3.3 循环链表

循环链表是将头和尾链起来的链表，单向和双向链表都有循环链表，如下所示
image.png