数据结构

基本概念

顺序存储结构中只需要存储元素信息即可，链式存储结构中需要额外存储后继元素的存储地址，数据域和指针域，两部分合起来称为结点。

我们把第一个结点的位置（链表中首个结点的地址）叫做头指针，为了更加方便的操作链表会在单链表的第一个结点前附加一个结点称为头结点，头结点的数据域不存储任何东西，头结点可以没有。

有了头结点，对第一个元素结点前插入结点和删除第一结点的操作和其他操作统一了，通常是一个值为 null 的节点头结点，或者存储链表的公用数据。头节点的地址通常就是整个链表的地址，且不会改变。

空链表则是头节点的指针域为空。