链表（一）

在链表中，每个数据项都被包含在<链接点>（Link）中，一个链接点是某个类的对象，这个类可以叫做Link。
每个Link对象都包含一个对下一个链接点引用的字段（next）。

1 public class Link {
2     public int iData;
3     public double dData;
4     public Link next;
5 }

引用和基本类型：

在链表的环境中，很容易对<引用>产生混淆。
在Java语言中，Link对象并没有真正包含另一个Link对象，尽管看起来像是包含了，类型为Link的next字段仅仅对另一个Link对象的“引用”，而不是一个对象。
一个引用是对一个对象的参照数值，它是计算机内存中一个地址，所有的引用，不管它指向谁，大小都是一样的。对编译器来说，知道这个字段大小从而构造整个Link对象，是没有问题的。

对于int和double等基本数据类型，含有的字段并不是引用，而是实实在在的值。例如 double salary = 2000.0;
它在内存地址创建了一个空间，然后把数值2000.0放进去。
如：Link newLink = new Link();
newLink字段并没有真正拥有一个对象，它仍然是个引用。这个对象存在内存某个地方。
Link otherLink = newLink;
newLink把自己本身对Link的引用放到变量otherLink中。

单链表：

 1 public class Link {
 2     
 3     private int iData;
 4     private double dData;
 5     private Link next;
 6     
 7     public Link(int i, double d){
 8         this.iData = i;
 9         this.dData = d;
10     }
11     
12     public void displayLink(){
13         System.out.println("{ " + iData + " , " + dData + " }");
14     }
15 
16     public Link getNext() {
17         return next;
18     }
19 
20     public void setNext(Link next) {
21         this.next = next;
22     }
23 
24     public int getiData() {
25         return iData;
26     }
27 
28     public double getdData() {
29         return dData;
30     }
31     
32 }

  1 public class LinkList
  2 {
  3     private Link first;
  4 
  5     public void addFirst(int i, double d)
  6     {
  7         Link newLink = new Link(i, d);
  8         newLink.setNext(first);
  9         first = newLink;
 10     }
 11 
 12     public Link removeFirst()
 13     {
 14         Link f = first;
 15         first = first.getNext();
 16         return f;
 17     }
 18 
 19     public boolean isEmpty()
 20     {
 21         return first == null;
 22     }
 23 
 24     public void display()
 25     {
 26         Link current = first;
 27         while (current != null)
 28         {
 29             current.displayLink();
 30             current = current.getNext();
 31         }
 32     }
 33 
 34     public Link find(int key)
 35     {
 36         Link current = first;
 37         while (current != null)
 38         {
 39             if (current.getiData() == key)
 40             {
 41                 return current;
 42             }
 43             else
 44             {
 45                 current = current.getNext();
 46             }
 47         }
 48         return null;
 49     }
 50 
 51     public Link find2(int key)
 52     {
 53         Link current = first;
 54         while (current.getiData() != key)
 55         {
 56             if (current.getNext() == null)
 57             {
 58                 return null;
 59             }
 60             else
 61             {
 62                 current = current.getNext();
 63             }
 64         }
 65         return current;
 66     }
 67 
 68     public Link delete(int key)
 69     {
 70         Link current = first;
 71         Link previous = first;
 72         while (current != null)
 73         {
 74             if (current.getiData() == key)
 75             {
 76                 if (current == first)
 77                     first = first.getNext();
 78                 else
 79                     previous.setNext(current.getNext());
 80                 return current;
 81             }
 82             else
 83             {
 84                 previous = current;
 85                 current = current.getNext();
 86             }
 87         }
 88         return null;
 89     }
 90 
 91     public Link delete2(int key)
 92     {
 93         Link current = first;
 94         Link previous = first;
 95         while (current.getiData() != key)
 96         {
 97             if (current.getNext() == null)
 98             {
 99                 return null;
100             }
101             else
102             {
103                 previous = current;
104                 current = current.getNext();
105             }
106         }
107         if (current == first)
108         {
109             first = first.getNext();
110         }
111         else
112         {
113             previous.setNext(current.getNext());
114         }
115         return current;
116     }
117 
118 }

 1     public static void main(String[] args)
 2     {
 3         LinkList ll = new LinkList();
 4         ll.addFirst(2, 2.8);
 5         ll.addFirst(7, 7.6);
 6         ll.addFirst(5, 5.5);
 7         ll.addFirst(9, 9.5);
 8         ll.addFirst(12, 12.5);
 9         ll.addFirst(14, 14.5);
10         ll.addFirst(16, 16.5);
11         ll.removeFirst();
12         System.out.println("------------DISPLAY");
13         ll.display();
14         System.out.println("------------FIND");
15         ll.find(12).displayLink();
16         System.out.println("------------DELETE");
17         ll.delete(14).displayLink();
18         System.out.println("------------DISPLAY");
19         ll.display();
20     }

打印结果：
------------DISPLAY
{ 14 , 14.5 }
{ 12 , 12.5 }
{ 9 , 9.5 }
{ 5 , 5.5 }
{ 7 , 7.6 }
{ 2 , 2.8 }
------------FIND
{ 12 , 12.5 }
------------DELETE
{ 14 , 14.5 }
------------DISPLAY
{ 12 , 12.5 }
{ 9 , 9.5 }
{ 5 , 5.5 }
{ 7 , 7.6 }
{ 2 , 2.8 }

有序链表：

 1     public void insert(int i, double d) {
 2     　　Link newLink = new Link(i, d);
 3     　　Link previous = null;
 4     　　Link current = first;
 5     　　while (current != null && i > current.getiData()) {
 6         　　previous = current;
 7         　　current = current.getNext();
 8     　　}
 9     　　if (previous == null) {
10         　　first = newLink;
11         　　newLink.setNext(current);
12     　　} else {
13         　　previous.setNext(newLink);
14         　　newLink.setNext(current);
15     　　}
16     }