链表（一）

一.链节点

链表由链节点构成，链节点有一个对象构成，对象中有一个属性引用上一个或下一个节点。链表本身有一个字段指向对第一个链节点的引用。

二.单链表：表头插入数据，表头删除数据，遍历数据。

代码：

链节点

 1 public class Link {
 2     public  int iDate;
 3     public  double dDate;
 4     public  Link next;
 5     
 6     public Link(){        
 7     }
 8     
 9     public Link(int iDate,double dDate){
10         this.iDate = iDate;
11         this.dDate = dDate;
12     }
13     
14     public void display(){
15         System.out.println("{"+iDate+","+dDate+"}");
16     }
17 }

链表

 1 public class LinkList {
 2     private Link first;
 3     
 4     public LinkList(){
 5         first = null;
 6     }
 7     
 8     public boolean isEmpty(){
 9         return first == null;
10     }
11     
12     public void insert(int id,double dd){
13         Link link = new Link(id, dd);
14         link.next = first;
15         first = link;
16     }
17     
18     public Link deleteFirst(){
19         Link link = first;
20         first = first.next;
21         return link;
22     }
23     
24     public void displayList(){
25         System.out.println("first-list");
26         Link link = first;
27         while(link != null){        
28             link.display();
29             link = link.next;
30         }
31     }
32 }

测试类：

 1 public class LinkListApp {
 2     public static void main(String[] args) {
 3         LinkList ll = new LinkList();
 4         ll.insert(5, 10.0);
 5         ll.insert(23, 10.5);
 6         ll.insert(9, 23.9);
 7         ll.displayList();
 8         if(!ll.isEmpty()){
 9             ll.deleteFirst();
10         }
11         ll.displayList();
12     }
13 }

三.双端链表：与单链表很相似，只增加了一个对最后一个节点的引用，从而可以在链表后面插入数据。

代码：

链表：

 1 public class LinkList {
 2     private Link first;
 3     private Link last;
 4 
 5     public LinkList() {
 6         first = null;
 7         last = null;
 8     }
 9 
10     public boolean isEmpty() {
11         return first == null;
12     }
13 
14     public void insertFirst(int id, double dd) {
15         Link link = new Link(id, dd);
16 
17         if (isEmpty())
18             last = link;
19         else
20             link.next = first;
21         first = link;
22     }
23 
24     public void insertLast(int id, double dd) {
25         Link link = new Link(id, dd);
26 
27         if (isEmpty())
28             first = link;
29         else
30             last.next = link;
31         last = link;
32     }
33 
34     public Link deleteFirst() {
35         Link link = first;
36         if(first.next==null)
37             last = null;
38         first = first.next;
39         return link;
40     }
41 
42     public void displayList() {
43         System.out.println("first-list");
44         Link link = first;
45         while (link != null) {
46             link.display();
47             link = link.next;
48         }
49     }
50 }

四.链表的效率

1.表头插入和删除的效率很高，只需要改变一两个引用值，O(1)

2.平均起来，查找，删除和指定节点后面插入都需要遍历一半的节点，需要O(n)次比较，跟数组一样，但是链表不需要移动任何东西。

3.链表比数组更优越的是，链表对内存的利用率更高。