Java数据结构与算法（第五章链表）

        数组作为数据存储机构有一定的缺陷。在无序数组中，搜索是低效的；而在有序数组中，插入效率又很低；不管在哪一种数组重删除效率都很低。况且一个数组创建后，它的大小是不可改变的。

        链表可能是继数组之后第二种使用得最广泛的通用存储结构。

链结点（Link）

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

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

引用和基本类型

        在链表的环境中，很容易对“引用”产生混淆。

        在Link的类定义中定义了一个Link类型的域，这看起来很奇怪。编译器怎样才能不混淆呢？编译器在不知道一个LInk对象占多大空间的情况下，如何能知道一个包含了相同对象的Link对象占用多大空间呢？

        在Java语言中，这个wen ti的da an是Link对象并没有真正包含另外一个Link对象。看似包含了，类型的Link的next字段仅仅是对另外一个Link对象的“引用”，而不是一个对象。

关系而不是位置

        链表不同于数组的主要特性之一。在一个数组中，每一项占用一个特定的位置。这个位置可以用一个下标号直接访问。它就像一排房子，你可以凭地址找到其中特定的一间。

        在链表中，寻找一个特定的元素的唯一方法就医沿着这个元素的链一直向下找。它很想人们之间的关系。可能你问Harry，Bob在哪儿，Harry不知道，但是他想Jane可能知道，所以你又去问Jane。Jane看到Bob和Sally一起离开了公司，所以你打Sally的手机，她说她在Peter的办公室和Bob分开了，所以。。。。。。但是总有线索，不能直接访问到数据项；必须使用数据之间的关系来定位它。从第一项开始，到第二项，然后到第三个，知道发现要找的那个数据项。

??单链表??

双端链表

链表的效率

        在表头插入和删除速度很快。仅需要改变一两个引用值，所以花费O(1)的时间。

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

        链表比数组优越的另外一个重要方面是链表需要多少内存就可以用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常有序数组太大导致效率低下，或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量）。这个解决方案在内存使用效率上来说还是要比链表的低。

抽象数据类型（ADT）

        抽象数据类型（ADT）。简单说来，它是一种考虑数据结构的方式：着重于它做了什么，而忽略它是做么做的。

        栈和队列都是ADT的例子。前面已经看到栈和队列都可以用数组来实现。在继续ADT的讨论之前，先看一下如何用链表实现栈和队列。这个讨论将展示栈和队列的“抽象”特性：即如何脱离具体实现来考虑栈和队列。

用链表实现栈Java代码：

package com.stack.linkstack;
public class LinkStack {
    private LinkList theList;
    public LinkStack(){
        theList = new LinkList();
    }
    public void push(long j){
        theList.insertFirst(j);
    }
    public long pop(){
        return theList.deleteFirst();
    }
    public boolean isEmpty(){
        return theList.isEmpty();
    }
    public void displayStack(){
        System.out.print("Stack (top --> bottom): ");
        theList.displayList();
    }
}
class Link{
    public long dData;
    public Link next;
    public Link(long dd){
        dData = dd;
    }
    public void displayLink(){
        System.out.print(dData+" ");
    }
}
class LinkList{
    private Link first;
    public LinkList(){
        first = null;
    }
    public boolean isEmpty(){
    return first == null;
    }
    public void insertFirst(long dd){
        Link newLink = new Link(dd);
        newLink.next = first;
        first = newLink;
    }
    public long deleteFirst(){
        Link temp = first;
        first = first.next;
        return temp.dData;
    }
    public void displayList(){
        Link current = first;
        while(current!=null){
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
}

public class LinkStackApp {
    public static void main(String[] args) {
        LinkStack theStack = new LinkStack();
        
        theStack.push(20);
        theStack.push(40);
        
        theStack.displayStack();
        
        theStack.push(60);
        theStack.push(80);
        
        theStack.displayStack();
        theStack.pop();
        theStack.pop();
        
        theStack.displayStack();
    }
}

//输出：
Stack (top --> bottom): 40 20 
Stack (top --> bottom): 80 60 40 20 
Stack (top --> bottom): 40 20

用链表实现队列Java代码：

package com.queue.linkqueue;
public class LinkQueue {
    private FirstLastList theList;
    public LinkQueue(){
        theList = new FirstLastList();
    }
    public boolean isEmpty(){
        return theList.isEmpty();
    }
    public void insert(long j){
        theList.insertLast(j);
    }
    public long remove(){
        return theList.deleteFirst();
    }
    public void displayQueue(){
        System.out.print("Queue (front --> rear): ");
        theList.displayList();
    }
}
class Link{
    public long dData;
    public Link next;
    public Link(long d){
        dData = d;
    }
    public void displayLink(){
        System.out.print(dData+" ");
    }
}
class FirstLastList{
    private Link first;
    private Link last;
    public FirstLastList(){
        first = null;
        last = null;
    }
    public boolean isEmpty(){
        return first == null;
    }
    public void insertLast(long dd){
        Link newlink = new Link(dd);
        if(isEmpty()){
            first = newlink;
        }else{
            last.next = newlink;
        }
        last = newlink;
    }
    public long deleteFirst(){
        long temp = first.dData;
        if(first.next==null)
            last = null;
        first = first.next;
        return temp;
    }
    public void displayList(){
        Link current = first;
        while(current!=null){
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
}

public class LinkQueueApp {
    public static void main(String[] args) {
        LinkQueue theQueue = new LinkQueue();
        theQueue.insert(20);
        theQueue.insert(40);
        theQueue.displayQueue();
        theQueue.insert(60);
        theQueue.insert(80);
        theQueue.displayQueue();
        theQueue.remove();
        theQueue.remove();
        theQueue.displayQueue();
    }
}
//输出：
Queue (front --> rear): 20 40 
Queue (front --> rear): 20 40 60 80 
Queue (front --> rear): 60 80

数据类型和抽象：

待续。。。

162

Java数据结构与算法（第五章链表）

原文：http://my.oschina.net/u/1431757/blog/521529