链表

有三种链表，单向链表、双向链表、循环链表

循环链表分为单向和双向两种。没有结束，也没有头和尾。主要遍历问题是避免产生循环：如果没有记住从哪里开始，就会在链表中无限循环下去。

链表的基本操作：遍历链表、插入删除链表元素。这些问题总是使用单向链表。

单向链表的重要的一点：维护头指针head和尾指针tail。head丢失会导致链表在内存中丢失。这意味着在进行插入、删除元素操作的时候，如果有必要，必须及时更新链表的head和tail指针。

C语言实现的链表基本操作中，需要注意更新的是否是“本地拷贝”的问题。如下两个方法，只有后者恰当更新了头指针。在C++中，除了本例中采用的传递指向链表头指针的指针方法外，还可以采用传递引用。 形参和头指针的更新1boolinsertInFront(IntElementhead,intdata);

2{

3IntElementnewElem=newIntElement;

4if(!newElem)returnfalse;

5newElem->data=data;

6newElem->next=head;

7head=newElem;//Incorrect, head is not update

8returntrue;

9}

10

11boolinsertInFront(IntElementhead,intdata);

12{

13IntElementnewElem=newIntElement;

14if(!newElem)returnfalse;

15newElem->data=data;

16newElem->next=head;

17*head=newElem;//Correctly updates head

18returntrue;

19}

20

栈的链表实现和数组实现

动态数组：动态数组实现的栈必须能根据需要改变大小。优点在于，数组提供对元素的随机访问。但是栈的操作总是在数据结构的一端进行（栈顶），所以数组的随机访问并不能带来好处。另外数组的动态增长导致的数据迁移可能非常耗时。但是如果采用比较良好的方式来减少数组大小的改变次数，较之链表实现的栈速度更快。

链表：链表为每个元素动态分配内存，在处理小规模元素时开销可能很大。链表实现的栈比较简单，面试时候应当选择。

C语言实现基于链表的栈的时候，考虑2个问题：

1. push、pop函数返回值表征操作是否成功，还是push、和pop的data？

2. 本地拷贝的问题，更新head，也就是栈指针，也就是指向链表头元素的指针。

对于第一个问题，C语言实现中，倾向于选择始终让方法返回此操作是否成功。返回的数据则采用这样的方法：传入一个变量的指针。方法可以通过这个指针改变变量的值，从而实现返回数据。1//void 类型泛指栈存储的数据类型，具体可以为int等其他

2typedefstructElement{

3structElementnext;

4voiddata;

5}

6

7boolpush(Elementstack,voiddata);

8boolpop(Elementstack,voiddata);

9

另外，栈的实现一般还需要2个函数： bool createStack(Element stack) 和 bool deleteStack(Elementstack)。createStack只需要简单讲*stack=NULL 既可。后者则需要遍历栈，释放每一个空间。

在面向对象的语言，如C++中，栈的借口设计就更为简单。creatStack和deleteStack变成了构造函数和析构函数。push和pop也和栈对象绑定，不需要将栈作为传入参数，也不需要返回操作是否成功的错误代码，可以让pop直接返回栈中的数据。因为错误都可以通过抛出异常来实现。struct Element则作为类Stack的类型成员。具体代码参考相关资料。

链表中插入、删除元素（C语言）

bool remove ( Element *elem);

bool insertAfter ( Element *elem, int data);

后者能够以NULL作为参数调用，实现在链表头前插入。这些函数成功返回true，失败返回false。编写这两个函数的难点是：保证头指针和尾指针都是当前的。

解决思路是：先写出处理一般链表的代码，之后逐个考虑是否可以满足特殊情况。比如特殊情况有：NULL指针参数，三种可能的链表长度：空、1、2、大于等于3。当链表长度为2时候，remove操作删除第一个元素和删除第二个元素时候head和tail指针的更新。具体参考相关资料。 原文链接: https://www.cnblogs.com/younes/archive/2010/03/01/1675944.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍