数据结构与算法_链表

单链表：LinkList类，只有一个数据项，即对链表中第一个链节点的引用，叫做first。他是唯一的链表需要维护的永久信息，用以定位所有其他的链结点。从first出发，沿着链表通过每个链结点（Link类的实例）的next字段，就可以找到其他的链结点。

在链表头插入一个新的结点

public void insertFirst(int id,double dd)

       {

              Link newLink =new Link(id,dd);

              newLink.next=first;       //newLink --> old first

              first=newLink;       //first --> newLink

       }

删除链表头一个结点

       public Link deleteFirst()

       {

              Link temp=first;     //save reference to link

              first =first.next;      //delete it: first --> old next

              return temp;

       }

查找指定链结点，也即遍历链表的所有结点，判断结点的值是否给定值。

       public Link find(int key)//find link with given key

       {

              Link current = first;

              while (current.iData != key) //start at 'first'

              {

                     if(current.next == null) //didn't find it

                            return null;

                     else

                            current = current.next;   //goto next link

              }

              return current;              //found it

       }

删除指定链结点，与查找操作基本类似，，不过它还要记录当前结点的前一个结点的引用，而删除当前结点就是把前一个结点和后一个结点连在一起。而删除时也要区分一种特殊情况，即要删除的当前结点为链表的第一个结点时，只需要使first字段指向first.next。

       public Link delete(int key)            //delete link with given key

       {

              Link current = first;              //search for link

              Link previous = first;

              while (current.iData != key)

              {

                     if(current.next == null) //didn't find it

                            return null;

                     else

                     {

                            previous = current;//go to next link

                            current = current.next;

                     }

              }     //found it

              if(current == first) //if first link

                     first = first.next;     //change first

              else

                     previous.next = current.next;//bypass it

              return current;

       }

双端链表：它与传统链表基本相似，但有一个新增特性：即对最后一个结点的引用，就像对第一个结点的引用一样，由last指针指向它的最后一个结点。可以像直接用first访问表头一样访问表尾，这个特性使双端链表更适合于一些普通链表不方便操作的场合，比如实现队列。还要注意双端链表和双向链表的不同。

双端链表在表头的插入删除操作和普通链表很类似，要注意的地方是当插入的结点是第一个结点时，必须使last指针指向该结点，同样删除的如果是剩下的最后一个结点，则last不要忘了置为null。另外可以很方便的在表尾插入一个结点insertLast（代码略），同样要注意插入前链表为空的特殊情况，此时要将first置为null。

链表效率比数组要高，虽然查找时比较的次数都为O（N），但是链表的插入删除操作不需要移动任何东西，只要改变一下引用的指向。另外一个重要方面是数组在定义时大小是固定的，但是链表可以分配任意大小，甚至是所有可用内存。

抽象数据类型

ADT，简单说来它是一种考虑数据结构的方式：着重于它做了什么，而忽略它是怎么做的。栈和队列都是ADT的例子。它们不仅可以用数组来实现，而且也可以用链表来实现。栈可以用普通的链表来实现，队列可以用双端链表来实现。

数据类型就是拥有特定特性的数据项和在数据上允许的操作，如int型。在面向对象编程中，可以用类来创建自己的数据类型，那么字段就代表数据，方法就是可以在这些字段上进行的运算。

抽象的意思是“不考虑细节的描述和实现。”在面向对象编程中，抽象数据类型是一个类，且不考虑他的实现。它只有类中数据的描述和能进行的操作以及如何进行这些操作的说明。用户不知道怎么实现的，也不需要知道数据是怎么存储的。比如栈，用户只知道push和pop方法的存在和如何使用它们，至于栈是用数组来做的还是用链表来做的并不重要。Push和pop这些用户可见的方法就叫做“接口”。

利用ADT进行软件设计，如果需要存数据，就从考虑需要在数据上的操作开始。粗腰存取最后一个插入的数据码？还是第一个？。。。？回到这些问题会引出ADT的定义。定义好了ADT才考虑实现细节。好处是简化设计过程，可以不干扰用户代码的情况下修改实现，因为用户只接触ADT接口。

有序链表

在某些应用中，链表中数据项保持有序是有用的。在有序链表中，数据是按照关键值有序排列的。有序链表比有序数组效率要高，但是实现相对要复杂。有序链表的应用：为数据排序，当然也可以实现优先级队列。

       在有序链表中，插入一个数据项时，算法必须先搜索链表，直到找到合适的位置：它恰好在第一个比它大的数据项的前面。当算法找到了该插入位置后：把新链结点的next字段指向下一个链结点，然后前一个链接点的next字段改为指向新的链结点。需要考虑一些特殊情况：链结点可能插在表头，或者插在表尾。

方法 public void insert(long key) {略。。}

       有序链表可以在O（1）的时间内找到或删除最小值，因为它总在表头。所有有序链表适用于频繁地存取最小项，且不需要快速地插入的应用场景。例如：优先级队列。

       有序链表可以用于排序。假设有一个无序数组。如果从这个数据中取出数据，然后一个个地插入有序链表，他们自动地按顺序排列。把他们从有序表中删除，重新放入数组，那么数组就排好序了。这种排序方式比在数组中用插入排序效率更高一些，因为这种方式移动次数少，数组中的插入排序移动次数是O（N *N），在这种排序中，则只需要2*N次复制。不过也有缺点，就是要开辟差不多两倍的空间。

双向链表

它提供链表向前和向后的遍历的能力。秘密在于每个链结点有两个指向其他链结点的引用，而不是一个。第一个指向下一个链结点。第二个指向前一个链结点。

       它的缺点是每次插入或删除一个链结点时，要处理四个链结点的引用，而不是两个。由于多了两个引用，占的空间也就大了些。

       基于双向链表可以实现双端队列。

迭代器

迭代器类包含对数据结构中数据项的引用，用来遍历这些结构的对象。最初定义如下：

Class ListIterator()

{

       Private Link current;

       ……

}

Current字段包含迭代器当前指向的链接点的一个引用。

       在使用迭代器时，可以让链表创建，它同时可以传入一些必要信息。迭代器与链表相关联，但并不等同于链表或是链结点。过去在链表类中实现的所有与进行迭代有关的操作，例如insertAfter（），现在自然可以由迭代器实现。哪些任务由迭代器实现，哪些由链表本身完成？需要迭代的最好由迭代器内完成，而insertBefore（）方法总是在链表头插入新链结点，它更适合在链表类中实现。

       设计迭代器时一个问题是决定在不同的操作后，迭代器应该指向哪里？

迭代器代码（略。。。）。