线性表的顺序存储结构存在以下几方面的缺点：

因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用链式存储结构。

假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储点，简称结点。

在链式存储方式中，要求每个结点有两部分组成：数据域和指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在表示较复杂的非线性结构时，其指针域的个数要多一些。

线性表的链式存储结构称为线性链表。

将计算机中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个数据元素的存储序号（即存储结点的地址），即指向后件的点，称为指针域。

在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性链表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0来表示），表示链表终止。

在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来表示的，指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。

在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但找不到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便。为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink）用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为线性双链表。

栈也是线性表，也可以采用链式存储结构。

在实际应用中，带链的栈可以用来手机计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

队列也是线性表，也可以采用链式存储结构。

当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。

在链表中，如果有指定元素，则扫描到等于该元素值的结点时，停止扫描，返回该结点的位置。因此，如果链表中有多个等于指定元素的结点只返回第一个结点的位置。如果链表中没有元素的值等于指定元素，则扫描完所有元素后，返回NULL。

线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。

假设现在要在线性链表中包含元素x的结点之前插入一个新元素b，插入过程如下：

由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表的插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。

线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。

为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除的结点放回可利用栈。

假设现在要在线性链表中删除包含元素x的结点，其删除过程如下：

此时，线性链表的删除运算完成。

循环链表的结构与线性链表相比，具有以下两个特点：

在实际应用中，循环链表与线性单链表相比主要有两个优点：

树是一种简单的非线性结构。

在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。每个结点可以有多个后件，它们都称为该结点的子结点，没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度，所有结点中的最大的度称为树的度。

树中的结点数=树中所有结点的度之和+1

在树结构中，一般按照如下原则分层：

树在计算机中通常用多重链表来表示。

二叉树具有以下两个特点：

在二叉树中，每一个结点的度最大为2。

满二叉树与完全二叉树是两种特殊形态的二叉树。

除最后一层外，每一层上所有的结点都有两个子结点，即每一层上的结点树都达到最大值。

满二叉树的第k层上有2^(k-1)个结点，深度为m的满二叉树有2(m-1)个结点。

除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少右边的若干结点。

满二叉树也是完全二叉树，完全二叉树一般不是满二叉树

在计算机中，二叉树通常采用链式存储结构。

对于满二叉树和完全二叉树，可以按层序进行顺序存储，但顺序存储结构对一般的二叉树不适用。

二叉树的遍历指不重复地访问二叉树中的所有结点。

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。

首先访问根结点，然后遍历左子树，最后遍历右子树。并且在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

前序遍历二叉树的过程是一个递归的过程。

首先遍历左子树，然后访问根结点，最后遍历右子树。并且在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历二叉树也是一个递归的过程。

首先遍历左子树，然后遍历右子树，最后访问根结点。并且在遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

后序遍历二叉树也是一个递归的过程。