链表（三）

链表的效率：

在表头插入和删除数据项很快，仅需要改变一两个引用值，所花费时间O(1)。
平均起来，删除、查找、在指定的链接点插入仅需要搜索一半的数据，需要O(N)次比较。在数据执行这些操作也需要O(N)次比较，但链表更快一些，因为插入删除数据项时，链表不需要移动其它数据项。
链表比数组优越的重要方面在于链表需要多少内存就用多少内存，并且可以扩展到其它所有可用的内存。数组的大小从创建时就定义好，所以经常由于数组太大导致效率低下，或者数组太小空间溢出。向量是一种可扩展的数组，但它只允许以固定的大小增长扩展（溢出时增长一倍数组容量），在内存使用率比链表的低。

ADT：抽象数据类型，是指一些数据以及对这些数据所进行的的操作的集合。

双向链表：提供向前 / 向后遍历整个链表，因为每个链接点都有两个指向其它链接点的引用。
缺点：每次插入 / 删除链接点，都要处理四个链接点的引用（两个连接前一个链接点，两个连接后一个链接点）。由于多了两个引用，占用的空间也更大了。

与双端链表的区别：可以提供removeLast()

 1 public class Link {
 2 
 3     private int iData;
 4     private double dData;
 5     
 6     private Link next;
 7 
 8     // 针对双向链表
 9     private Link previous;
10 
11     public Link(int i, double d) {
12     　　this.iData = i;
13     　　this.dData = d;
14     }
15 
16     public void displayLink() {
17     　　System.out.println("{ " + iData + " , " + dData + " }");
18     }
19 
20     public Link getNext() {
21     　　return next;
22     }
23 
24     public void setNext(Link next) {
25     　　this.next = next;
26     }
27 
28     public int getiData() {
29     　　return iData;
30     }
31 
32     public double getdData() {
33     　　return dData;
34     }
35 
36     public Link getPrevious() {
37     　　return previous;
38     }
39 
40     public void setPrevious(Link previous) {
41     　　this.previous = previous;
42     }
43 
44 }

 1 public class DoublyLinkList {
 2 
 3     private Link first;
 4     private Link last;
 5 
 6     public boolean isEmpty() {
 7     　　return first == null;
 8     }
 9 
10     public void insertFirst(int i, double d) {
11     　　Link newLink = new Link(i, d);
12     　　if (isEmpty())
13         　　last = newLink;
14     　　else
15         　　first.setPrevious(newLink);
16     　　newLink.setNext(first);
17     　　first = newLink;
18     }
19 
20     public void insertLast(int i, double d) {
21     　　Link newLink = new Link(i, d);
22     　　if (isEmpty()) {
23         　　first = newLink;
24     　　} else {
25         　　last.setNext(newLink);
26         　　newLink.setPrevious(last);
27    　　 }
28     　　last = newLink;
29     　　}
30 
31     public Link deleteFirst() {
32     　　Link l = first;
33     　　if (first.getNext() == null)
34         　　last = null;
35     　　else
36         　　first.getNext().setPrevious(null);
37     　　first = l.getNext();
38     　　return l;
39     }
40 
41     public Link deleteLast() {
42     　　Link l = last;
43     　　if (first.getNext() == null)
44         　　first = null;
45     　　else
46         　　last.getPrevious().setNext(null);
47     　　last = last.getPrevious();
48     　　return l;
49     }
50 
51     public Link find(int key) {
52     　　Link current = first;
53     　　while (current != null) {
54         　　if (current.getiData() == key) {
55         　　　　return current;
56         　　}
57         　　current = current.getNext();
58     　　}
59     　　return null;
60     }
61 
62     public Link delete(int key) {
63     　　Link l = find(key);
64     　　if (l != null) {
65         　　if (l.getPrevious() != null) {
66         　　　　l.getPrevious().setNext(l.getNext());
67         　　} else {
68         　　　　first = l.getNext();
69         　　}
70     　　}
71     　　return l;
72     }
73 
74     public void displayListForward() {
75     　　Link current = first;
76     　　System.out.println("FirstLastList (First --> Last)");
77     　　while (current != null) {
78         　　current.displayLink();
79         　　current = current.getNext();
80     　　}
81     }
82 
83     public void displayListBackward() {
84     　　Link current = last;
85     　　System.out.println("FirstLastList (Last --> First)");
86     　　while (current != null) {
87         　　current.displayLink();
88         　　current = current.getPrevious();
89     　　}
90     }
91 
92 }

 1     public static void main(String[] args) {
 2     　　DoublyLinkList ll = new DoublyLinkList();
 3     
 4     　　ll.insertFirst(5, 1.6);
 5     　　ll.insertFirst(6, 1.7);
 6     　　ll.insertFirst(0, 0.7);
 7     　　ll.insertLast(2, 1.8);
 8     　　ll.insertLast(8, 8.8);
 9     　　ll.insertLast(100, 8.8);
10     　　ll.displayListForward();
11     　　ll.deleteLast();
12     　　ll.deleteFirst();
13     　　ll.displayListForward();
14     　　System.out.println("delete 5 --> " );
15     　　ll.delete(5).displayLink();
16     　　ll.displayListForward();
17     }

打印结果：
FirstLastList (First --> Last)
{ 0 , 0.7 }
{ 6 , 1.7 }
{ 5 , 1.6 }
{ 2 , 1.8 }
{ 8 , 8.8 }
{ 100 , 8.8 }
FirstLastList (First --> Last)
{ 6 , 1.7 }
{ 5 , 1.6 }
{ 2 , 1.8 }
{ 8 , 8.8 }
delete 5 -->
{ 5 , 1.6 }
FirstLastList (First --> Last)
{ 6 , 1.7 }
{ 2 , 1.8 }
{ 8 , 8.8 }