线性表链式存储的应用
由于链表是一种动态存储管理的结构，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统应需求即时生成，因此，建立链表的过程是一个动态生成的过程。即从 "空表"起，依次建立结点，并逐个插入链表。所谓"逆序"创建链表指的是，依和线性表的逻辑顺序相"逆"的次序输入元素。
由于链表的生成是从最后一个结点起逐个插入，因此每个新生成的结点都是插入在链表的"第一个"结点之前，即头结点之后，使新插入的结点成为插入之后的链表中的第一个结点。
1、假设线性表( ，，…， )的数据元素存储在一维数组 A[n]中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为"空"的链表中。
算法
void CreateList_L(SLink &L, int n, ElemType A[])
{
// 已知数组 A 中存有线性表的 n 个数据元素，
// 逆序建立带头结点的单链表。
L = new LNode;
if (!L) exit(1); // 存储空间分配失败
L->next = NULL; // 先建立一个带头结点的空的单链表
for (i = n; i > 0; --i)
{ p = new LNode;
if (!p) exit(1); // 存储空间分配失败
p->data = A[i-1]; // 赋元素值
p->next = L->next; L->next = p; // 插入在头结点之后
} // for
} // CreateList_L
容易看出，算法的时间复杂度为O (ListLength(L))。
2、以链表作存储结构解例2-5的问题，即将线性表 (a1,a2,…am，b1,b2,b3,……bn ) 改变成 ( b1,b2,b3,……bn ，a1,a2,…am) 。
解题分析：
因为对链表来说，"插入"和"删除"仅需修改指针即可完成，并且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变，则算法的实际操作为：
(1) 从链表中删除(a1,a2,a3……am)
(2) 将(b1,b2,b3,……bn)链接到头结点之后；
(3) 将( a1,a2,…am)链接到bn之后。
算法:
void exchange_L( SLink &L，int m )
{
// 本算法实现单链表中前 m 个结点和后 n 个结点的互换
if ( m && L->next ) // 链表不空且 m!=0
{
p = L->next; k = 1;
while( k< m && p ) // 查找 所在结点
{
p = p->next; ++k;
} // while
if (p && p->next) // n!=0 时才需要修改指针
{
ha = L->next; // 以指针 ha 记 结点的位置
L->next = p->next; // 将 结点链接在头结点之后
p->next = NULL; // 设 的后继为空
q = L->next; // 令q 指向 结点
while (q->next) q = q->next; // 查找 结点
q->next = ha; // 将 结点链接到 结点之后
} // if(p)
} // if(m)
} // exchange_L
算法的时间复杂度为O (ListLength(L))。
循环的条件中为什么要有p!=NULL的判断？
因为单链表的长度是个隐含值，在此无法如顺序表那样事先判别参数 m 是否合法，如果参数不合适，则在没有找到第 m 个结点时，p=NULL，while 循环中的语句就会出问题。
由于参数中没有给出 n 的值，只有在找到 之后加以判别。
如果这里不加 p->next 是否为空的判别条件，下面哪一个语句会出问题？
算法执行到 q->next 时会出问题，因为当p->next=NULL 时，q=NULL，q->next 也就不成立了。这种情况对初学链表的人是最容易出问题的地方，但千万要注意避免。
整个算法就是对链表从头巡视到尾，两个单循环次数之和恰为表长。因此算法的时间复杂度为O(ListLength(L))。
此例充分显示了用"指针"指示"后继"的灵活性。
3、编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。
解题分析：
可以和顺序表采用同样算法，即设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在"新表"中进行查找，如果有相同的则舍弃之，否则就插入到新表中。
算法：
void purge_L(SLink &L )
{
// 删除单链表L中的冗余元素，即使操作之后的单链表中只保留
// 操作之前表中所有值都不相同的元素
p = L->next;
L->next = NULL;; // 设新表为空表
while ( p ) // 顺序考察原表中每个元素
{
succ = p->next; // 记下结点 *p 的后继
q = L->next; // q 指向新表的第一个结点
while( q && p->data!=q->data ) q = q->next;
// 在新表中查询是否存在和p->data相同的元素
if ( !q ) // 将结点 *p 插入到新的表中
{
p->next = L->next;
L->next = p;
}
else delete p; // 释放结点 *p
p = succ;
} // for
} // purge_L
此算法的时间复杂度为O (ListLength2(L))。
假设已知链表中的数据元素为(5,2,5,3,3,4,2,5,7,5,4,3),则经算法2.21操作之后的链表表示的线性表是什么？
是(7,4,3,2,5)。因为算法中的"插入"操作是将元素"倒序"插入新表中的，由于考虑集合中的元素没有次序关系，而"倒插"不需要加辅助指针变量。
试比较算法2.21和算法2.12，你将得出什么结论？
你一定发现这两个算法极为相似，因为它们处理的是例2-2提出的同一个问题。由此可见，顺序表和链表只是存储结构的不同，不影响问题求解的算法。
由于对原表中每个元素都需要在新的链表中进行查询，因此最坏情况下的时间复杂度仍为平方级的，和顺序表相同，正好说明这个时间复杂度是由算法决定的。