数据结构和算法5——链表

　　前面已经介绍了数组，我们看到数组作为数据存储结构是有一定缺陷的，在无序数组中，搜索是低效的；而在有序数组中，插入效率很低；不管哪一种数组，删除效率都很低。而且创建一个数组后，数组大小不可变。
　　本部分介绍链表，它是一种新的数据结构，可以解决上面的一些问题，这种数据结构就是链表，链表也是使用非常广泛的数据结构。这里将介绍单链表、双端链表、有序链表、双向链表和有迭代器的链表。

1 链结点(Link)                                         

　　在链表中，每个数据项都被包含在链结点中，一个链结点是某个类的对象，这个类可以叫做Link。因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达链结点。每个Link对象中都包含一个对下一个链结点引用的字段，通常叫next，但是链表本身的对象中有一个字段指向对第一个链结点的引用。

class Link{
    public int iData;
    public double dData;
    public Link next;
}

　　这种类定义有时叫做自引用式，因为它包含了一个和自己类型相同的字段，本例中叫做next。
　　链结点中仅包含两个数据项:一个int类型的数据，一个double类型的数据。在一个真正的应用程序中，可能包含更多的数据项。通常用一个包含这些数据的类的对象来代替这些数据项.
　　上面类对象里面有一个Link next类型的变量，这个变量是Link类型的，指向下一个节点。

2 链表访问与数组的区别                                  

　　链表不同于数组的访问，在一个数组中，每一项占用一个特定的位置，这个位置可以用一个下标来直接访问，比如要访问第7个元素，只要下标6肯定能访问，不需要知道前6个元素是什么。但是在链表中不是这样的。在链表中，寻找一个特定元素的唯一方法就是沿着这个元素的链一直向下寻找。它很像人们之间的关系。可能你问Harry，Bob在哪，Harry不知道，但是他想Jane知道，所以又去问Jane，Jane看到Bob和Sally一起离开，所以你又去问Sally，如此循环，总有线索，最终找到Bob。

3 链表及相关操作的实现                                  

3.1 单链表                             

先定义链表的节点Node类

class Node{
    public int iData;
    public double dData;
    public Node next;
    //有参数构造器
    public Node(int iData, double dData){
        this.iData = iData;
        this.dData = dData;
    };
    //该方法显示链结点的数据值，例如{22, 33.1}
    public void displayNode(){
        System.out.print("{" + iData + "," + dData + "}  ");
    }
};

　　上面的构造函数并没有初始化next字段，因为当它创建时候自动赋成null的值，不需要指向其他任何结点。
LinkList类
　　LinkList类只包含一个数据项:即对链表中第一个链表结点的引用，叫做first，它是唯一的链表需要维护的永久信息，用以定位所有其他的链表结点。从first出发，沿着链表结点的next字段，就可以找到其他结点。

class LinkList{
private Node first =  null;
    //链表是否为空
    public boolean isEmpty(){
        return (first == null);
    }
}

上面就实现了一个链表。下面实现链表的相关方法。

插入一个表头结点

　　该方法是insertFirst，该方法是在表头插入一个新链结点。这是很容易插入的一个结点，first当前指向的是第一个链结点，为了插入表头链结点，只需要使新创建的链结点的next字段等于原来的first值，然后改变first值，使它指向新创建的链结点。

　　在insertFirst方法中，首先创建一个新链接结点，把数据作为参数传入，然后改变链结点的引用。

　　上面我们看到插入一个新结点是在表头插入的，为什么不在表末尾插入呢？在尾巴上面添加不是很好吗？这个想法很好，但末尾结点并不好索引到，所以会很麻烦。

删除结点

　　该方法是deleteFirst，是插入的逆操作。它通过把first重新指向第二个链结点，断开了和第一个链结点的连接，通过查看第一个链结点的next字段可以找到第二个链结点。

//删除结点
public Node deleteFirst(){
    Node temp = first;
    first = first.next;
    return temp;
}

显示链表

　　displayList()方法可以从first开始，沿着引用链从一个链表结点到下一个链表结点。

public void displayList(){
    System.out.println("List(first --> last):");
    Node current = first;
    while(current != null){
        current.displayNode();
        current = current.next;
    }
    System.out.println("");
}

　　链表的尾端是最后一个链结点，它的next字段为null值，而不是其他的链结点，因为创建结点时候，这个字段就是null，而该链表结点总是停留在链表尾端，后来再也没有变过，当执行到链表的尾端的时候，while循环使用这个条件来终止自己。
　　把上面几个小程序合在一起即可：

输出结果：
List(first --> last):
{77,7.7} {7,7.7} {2,7.7} {7,2.7} {2,2.7} 
List(first --> last):
{7,7.7} {2,7.7} {7,2.7} {2,2.7} 
可以看出链表删除时候也是后入先出的。

查找指定结点

　　查找指定结点就是查找值在某个结点上的结点。

public Node find(int key){
        Node current = first;
        while(current.iData != key){
            //如果已达结尾
            if(current.next == null){
                return null;
            }else{
                current = current.next;
            }
        }
        return current;
}

删除指定结点:

public Node delete(int key){
    Node current = first;
    Node previous = first;
    while(current.iData != key){
        if(current.next == null){
            return null;
        }else{
            previous = current;
            current = current.next;
        }
        if(current == first){
            first = first.next;
        }else{
            previous.next = current.next;
        }
    }
    return current;
}

3.2 双端链表                        

　　双端链表和传统的链表非常相似，但是它有一个新增的特性:即对最后一个链表结点的引用，就像对第一个链表结点的引用一样。

　　对最后一个链表结点的引用允许像在表头一样，在表尾直接插入一个链表结点，当然，仍然可以在普通的单链表的表尾插入一个链表结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。
　　像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样的情况。

3.3 链表的效率

　　在表头插入和删除速度很快，仅需要改变一两个引用值，所以花费O(1)时间。
　　平均起来，查找、删除和在指定链结点后面插入都需要搜索链表中的一半链结点，需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但链表仍然要快一些，因为当插入和删除链表结点时，链表不需要移动任何东西，增加的效率是很显著的，特别是当复制时间远远大于比较时间的时候。

4 抽象数据类型                                               

　　抽象数据类型更注重数据结构能做什么，而不是怎么做。是对一些传统的数据结构的封装。下面我们用链表来实现栈及队列两种数据结构。

4.1 用链表实现栈                   

　　前面用数组来实现栈的时候，栈的push和pop操作实际是通过数组操作来完成的，例如下面的代码
　　arr[++top] = data;和data = arr[top--];
　　下面用链表来实现一个栈。

输出结果：
Stack (top --> bottom): 35 20 
Stack (top --> bottom): 33 21 35 20 
Stack (top --> bottom): 35 20

　　注意整个程序的组织：LinkStackApp类中的main()方法只和LinkStack类有关，LinkStack类只和LinkList类有关，main方法和LinkList类是不进行通信的。

4.2 用双端链表实现的队列    

　　队列是先进先出的，也就是插只往后插，删只删前面的。

运行结果：
Queue (front-->rear): 20 40 
Queue (front-->rear): 20 40 60 80 
Queue (front-->rear): 60 80

5 抽象：数据结构、数据类型和算法                 

　　数据结构是数据类型在几何结构上的一种描述，栈是一种数据结构，这种数据结构是寄托在一种数据类型上的，也就是一个类上的，数据结构上有一些操作，也就是一些算法。int类型也是有数据结构的，它是存储一个变量的，操作有很多种，比如加减乘除。

5.1 抽象数据类型                  

　　抽象数据类型就是不考虑数据类型的描述和实现，而是对外提供一些操作。面向对象编程中，一个抽象数据类型是一个类，且不考虑它的实现。它是对类中数据的描述和数据上执行的一系列方法以及如何使用这些操作的说明，每个方法如何执行任务对其他类来说是不可知的。比如对于栈这种数据类型来说，其他类只知道它有push和pop等方法的存在，以及如何用它们工作，用户不需要知道它如何运作，或者数据是否存储在数组里、链表里或者其他数据结构中。

ADT设计

　　ADT的概念在软件设计中是很有用的，如果需要存储数据，那么就从考虑需要在数据上实现的操作开始，需要存取最后一个插入的数据项吗？还是第一个？是特定值的项？还是在特定位置的项？回答这些问题会引出ADT的定义，只有在完整定义了ADT后，才应该考虑细节问题，例如如何表示数据，如何编码使方法可以存取数据等等。
　　一旦设计好ADT，必须仔细选择内部的数据结构，以使规定的操作的效率尽可能高。例如，如果需要随机存取元素N，使用链表就不够好，因为对链表来说，随机访问不是一个高效操作，选择数组会得到更好的效果。

5.2有序链表                          

　　有序链表中，数据是有序存储的。有序链表的删除常常只限于删除在链表头部的最小火最大的链表结点。不过有时候也用find方法和delete方法在整个链表中搜索某一特定点。
　　一般，在大多数需要使用有序数组的场合也可以使用有序链表，有序链表优于有序数组的地方是插入的速度(因为元素不需要移动)，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。但是有序链表实现起来比有序数组更困难一些。
下面实现这一点：

上面实现了一个有序链表，并且在表头、表中、表尾都插入了数据。

5.3 有序链表的效率               

　　在有序链表插入和删除最多需要O(N)次比较，(平均N/2)，因为必须沿着链表上一步一步走才能找到正确的位置，然而可以在O(1)的时间内找到或删除最小值，因为它总是在表头。

5.4 利用链表进行插入排序      

　　有序链表可以用于一种高效的排序机制，假设有一个无序数组，如果从这个数组中取出数据，然后一个个地插入有序链表，它们自动地按顺序排列，把它们从有序表中删除，重新放入数组，那么数组就会排好序了。
　　这种排序方式总体上比在数组中用常用的插入排序效率更高。因为复制次数更少，数组的插入排序算法时间级是O(N^2),在有序链表中每插入一个新的链结点，平均要与一半已存在的数据进行比较，如果插入N个新数据，就进行了N^2/4 次比较，每一个链结点只进行两次复制:一次从数组到链表，一次从链表到数组，在数组中进行插入排序需要N^2 次移动，相比之下，2*N次移动更好。

运行结果：
Unsorted Array: 
81 94 67 13 35 0 14 42 58 89 
Sorted Array: 
0 13 14 35 42 58 67 81 89 94 
上面生成的结果是随机的。

5.4 双向链表                          

　　下面讨论另一种链表：双向链表(注意和双端链表是不同的)。传统链表的一个潜在问题是沿着链表的反向遍历是困难的，用这样一个语句current = current.next可以很方便地到达下一个链结点，然而没有对应的方法回到前一个链结点。比如说有下面的情形：对于一个编辑器来说，移动光标可以从左往右移动，但是如果只能从左往右移动效率就很低，因为有时候我们也想从右往左边移动。
　　双向链表允许前向遍历也允许后向遍历。对于每一个结点有两个指向其他链结点的引用，一个指向前一个结点，另一个指向后一个结点。
下面是示意图：

在双向链表中，Link类定义的开头是这样声明的：

class Node{
    public long dData;
    public Node next;
    public Node previous;
    ......
}

　　双向链表每次插入或删除一个结点时候，需要处理四个结点的引用，而不是两个：两个连接前一个结点，两个连接后一个链结点。
遍历
从前往后遍历，和之前的链表一样，从后往前遍历如下:

Node current = last;
while(current != null){
    current = current.previous;
}

插入
　　除非这个链表是空的，否则insertFirst()方法把原先first指向的链表结点的previous字段指向新链表结点，把新链表结点指向原来first指向的结点，最后再把first指向新链表结点。

如果链表是空的，last字段必须改变，而不是first.previous字段改变，下面是代码：

if(isEmpty()){
    last = newNode;
}else{
    first.previous = newNode;
}
newNode.next = first;
first = newNode;

　　inserLast是在链表末尾插入，和头没有多少区别。
　　中间插入有点复杂，需要建立4个连接。如果结点在中间，这个和之前说的find方法没有什么区别，如果在末尾，next字段必须设为null，last值必须指向新结点。

if(current == last){
    newNode.next = null;
    last = newNode;
}else{
    newNode.next = current.next;
    current.next.previous = newNode;
}
newNode.previous = current;
current.next = newNode;

删除
　　删除同样需要处理四个结点：

current.previous.next = current.next;
current.next.previous = current.previous;

下面是双向链表的实现：

输出结果：
List (first-->last:)37 30 20 
List(last-->first:)20 30 37 
List (first-->last:)37 30 20 23 24 25 
List (first-->last:)37 30 20 23 33 24 25

6 迭代器                                                     

　　前面我们查找数值所在的结点时候，都是从头开始查找的，或者逆着查找，直到找到匹配值。但是这些方法没有提供给用户任何遍历上的控制手段，就是说找到这些并进行处理。比如你要遍历一个链表，并在某些特定的链结点上执行一些操作，比如提高拿最低工资的人员工工资，而不影响其他员工。

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

class ListIterator(){
　　private Node current;
　　....
}

　　注意迭代器是必须和对应的链表相关联的，不能单独存在。迭代器总是指向链表中的一些链表结点