数组作为数据存储结构有一定缺陷。在无序数组中，搜索低效；在有序数组中，插入低效。创建一个数组后大小不可改变。
链表可以解决数组存在的缺陷，机制灵活，用途广泛。它可以取代数组，作为其他存储结构的基础，例如栈、队列。除非需要频繁通过下标随机访问各个数据，否则很多使用数组的地方都可以用链表代替。

1，链结点

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

2，单链表

• 构造一个单链表，这个链表仅有的操作是：在链表头插入一个数据项；在链表头删除一个数据项；遍历链表显示它的内容。

/*
 * demonstrates linked list
 * */
class Link
{
    public int iData;//data item(key)
    public double dData;//data item
    public Link next;//next link in list

    public Link(int id, double dd)
    {
        iData = id;//initialize data
        dData = dd;//next is automatically set to null
    }

    public void displayLink()
    {
        System.out.print("{" + iData + " , " + dData + "} ");
    }
}

class LinkList
{
    private Link first;//ref to first link on list

    public LinkList()
    {
        first = null;//no items on list yet
    }

    public boolean isEmpty()//true if list is empty
    {
        return (first == null);
    }

    public void insertFirst(int id, double dd)//make new link
    {
        Link newLink = new Link(id, dd);
        newLink.next = first;//newLink --> old first
        first = newLink;//first --> newLink
    }

    public Link deleteFirst()//delete first item
    {
        Link temp = first;
        first = first.next;
        return temp;
    }

    public void displayList()
    {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null)
        {
            current.displayLink();//print data
            current = current.next;//move to next link
        }
        System.out.println("");
    }
}

public class LinkListApp
{
    public static void main(String[] args)
    {
        LinkList theList = new LinkList();//make new list
        theList.insertFirst(22, 2.00);
        theList.insertFirst(44, 4.00);
        theList.insertFirst(66, 6.00);
        theList.insertFirst(88, 8.00);
        theList.displayList();
        while (!theList.isEmpty())
        {
            Link aLink = theList.deleteFirst();
            System.out.print("Deleted ");
            aLink.displayLink();
            System.out.println("");
        }
        theList.displayList();
    }
    /*
    * Result
    *   List (first-->last): {88 , 8.0} {66 , 6.0} {44 , 4.0} {22 , 2.0} 
        Deleted {88 , 8.0} 
        Deleted {66 , 6.0} 
        Deleted {44 , 4.0} 
        Deleted {22 , 2.0} 
        List (first-->last): 
    * */
}

3，查找和删除指定链结点

• 根据单链表程序增加两个方法，一是在链表中查找包含指定关键字的链结点，二是删除包含指定关键字的链结点。

/*
 * demonstrates linked list
 * */
class Link
{
    public int iData;//data item(key)
    public double dData;//data item
    public Link next;//next link in list

    public Link(int id, double dd)
    {
        iData = id;//initialize data
        dData = dd;//next is automatically set to null
    }

    public void displayLink()
    {
        System.out.print("{" + iData + " , " + dData + "} ");
    }
}

class LinkList
{
    private Link first;//ref to first link on list

    public LinkList()
    {
        first = null;//no items on list yet
    }

    public boolean isEmpty()//true if list is empty
    {
        return (first == null);
    }

    public void insertFirst(int id, double dd)//make new link
    {
        Link newLink = new Link(id, dd);
        newLink.next = first;//newLink --> old first
        first = newLink;//first --> newLink
    }

    public Link deleteFirst()//delete first item
    {
        Link temp = first;
        first = first.next;
        return temp;
    }

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

    public Link delete(int key)
    {
        Link current = first;
        Link 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;
    }

    public void displayList()
    {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null)
        {
            current.displayLink();//print data
            current = current.next;//move to next link
        }
        System.out.println("");
    }
}

public class LinkList2App
{
    public static void main(String[] args)
    {
        LinkList theList = new LinkList();
        theList.insertFirst(22, 2.00);
        theList.insertFirst(44, 4.00);
        theList.insertFirst(66, 6.00);
        theList.insertFirst(88, 8.00);
        theList.displayList();
        Link f = theList.find(44);
        if (f != null)
        {
            System.out.println("Found link with key " + f.iData);
        }
        else
        {
            System.out.println("Can't find link");
        }
        Link d = theList.delete(66);
        if (d != null)
        {
            System.out.println("Deleted link with key " + d.iData);
        }
        else
        {
            System.out.println("Can't delete link");
        }
        theList.displayList();
    }
    /*
    * Result
    *   List (first-->last): {88 , 8.0} {66 , 6.0} {44 , 4.0} {22 , 2.0} 
        Found link with key 44
        Deleted link with key 66
        List (first-->last): {88 , 8.0} {44 , 4.0} {22 , 2.0} 
    * */
}

4，双端链表

• 双端链表和传统链表很像，但有一个新特征：即对最后一个链结点的引用，就像对第一个链结点的引用一样。

• 

• 对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。仍可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但效率很低。

• 像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。

/*
 * demonstrates list with first and last references
 * */
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 insertFirst(long dd)
    {
        Link newLink = new Link(dd);
        if (isEmpty())
        {
            last = newLink;
        }
        newLink.next = first;
        first = newLink;
    }

    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()
    {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null)
        {
            current.displayLink();//print data
            current = current.next;//move to next link
        }
        System.out.println("");
    }
}

public class FirstLastApp
{
    public static void main(String[] args)
    {
        FirstLastList theList = new FirstLastList();

        theList.insertFirst(22);
        theList.insertFirst(44);
        theList.insertFirst(66);

        theList.insertLast(11);
        theList.insertLast(33);
        theList.insertLast(55);

        theList.displayList();

        theList.deleteFirst();
        theList.deleteFirst();

        theList.displayList();
    }
    /*
    * Result
    *   List (first-->last): 66 44 22 11 33 55 
        List (first-->last): 22 11 33 55 
    * */
}

5，链表的效率

• 在表头插入和删除速度很快。仅需要改变一两个引用值，所以花费O(1)的时间。
• 平均起来，查找、删除和在指定链结点后面插入都需要搜索链表中的一半链结点。需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链结点时，链表不需要移动任何东西。增加的效率是很显著的，特别是当复制时间远大于比较时间时。
• 链表比数组优越的另一个方面就是需要多少内存就可以用多少内存。数组大小在创建时固定了，向量是一种可拓展数组，可以通过可变长度解决问题，但是只允许以固定大小的增量拓展（比如快溢出的时候，就增加一倍数组容量）。这个解决方案内存利用率上比链表低。

6，有序链表

• 在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表头部的最小或最大链结点。不过，有时也用find()方法和delete()方法在整个链表中搜索某一特定点。
• 一般，在大多数需要使用有序数组的场合也可用有序链表。有序链表优点是插入速度（不需要移动元素），可以拓展到全部有效的使用内存。

class Link
{
    public long dData;
    public Link next;

    public Link(long dd)
    {
        dData = dd;
    }

    public void displayLink()
    {
        System.out.print(dData + " ");
    }
}

class SortedList
{
    private Link first;

    public SortedList()
    {
        first = null;
    }

    public boolean isEmpty()
    {
        return (first == null);
    }

    public void insert(long key)
    {
        Link newLink = new Link(key);
        Link previous = null;
        Link current = first;
        while (current != null && key > current.dData)
        {
            previous = current;
            current = current.next;
        }
        if (previous == null)
        {
            first = newLink;
        }
        else
        {
            previous.next = newLink;
        }
        newLink.next = current;
    }

    public Link remove()
    {
        Link temp = first;
        first = first.next;
        return temp;
    }

    public void displayList()
    {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null)
        {
            current.displayLink();//print data
            current = current.next;//move to next link
        }
        System.out.println("");
    }
}

public class SortedListApp
{
    public static void main(String[] args)
    {
        SortedList theSortedList = new SortedList();

        theSortedList.insert(20);
        theSortedList.insert(40);

        theSortedList.displayList();

        theSortedList.insert(10);
        theSortedList.insert(30);
        theSortedList.insert(50);

        theSortedList.displayList();

        theSortedList.remove();

        theSortedList.displayList();
    }
    /*
    * Result
    *   List (first-->last): 20 40 
        List (first-->last): 10 20 30 40 50 
        List (first-->last): 20 30 40 50 
    * */
}

7，双向链表

• 传统链表一个潜在问题是沿链表的反向遍历是困难的。双向链表提供了这个能力。
• 双向链表允许向前遍历，允许向后遍历整个链表。秘密在于每个链结点有两个指向其他链结点的引用，而不是一个。
• 

class Link
{
    public long dData;
    public Link next;
    public Link previous;

    public Link(long d)
    {
        dData = d;
    }

    public void displayLink()
    {
        System.out.print(dData + " ");
    }
}

class DoublyLinkedList
{
    private Link first;
    private Link last;

    public DoublyLinkedList()
    {
        first = null;
        last = null;
    }

    public boolean isEmpty()
    {
        return first == null;
    }

    public void insertFirst(long dd)
    {
        Link newLink = new Link(dd);
        if (isEmpty())
        {
            last = newLink;
        }
        else
        {
            first.previous = newLink;
        }
        newLink.next = first;
        first = newLink;
    }

    public void insertLast(long dd)
    {
        Link newLink = new Link(dd);
        if (isEmpty())
        {
            first = newLink;
        }
        else
        {
            last.next = newLink;
            newLink.previous = last;
        }
        last = newLink;
    }

    public Link deleteFirst()
    {
        Link temp = first;
        if (first.next == null)
        {
            last = null;
        }
        else
        {
            first.next.previous = null;
        }
        first = first.next;
        return temp;
    }

    public Link deleteLast()
    {
        Link temp = last;
        if (first.next == null)
        {
            first = null;
        }
        else
        {
            last.previous.next = null;
        }
        last = last.previous;
        return temp;
    }

    public boolean insertAfter(long key, long dd)
    {
        Link current = first;
        while (current.dData != key)
        {
            current = current.next;
            if (current == null)
            {
                return false;
            }
        }
        Link newLink = new Link(dd);
        if (current == last)
        {
            newLink.next = null;
            last = newLink;
        }
        else
        {
            newLink.next = current.next;
            current.next.previous = newLink;
        }
        newLink.previous = current;
        current.next = newLink;
        return true;
    }

    public Link deleteKey(long key)
    {
        Link current = first;
        while (current.dData != key)
        {
            current = current.next;
            if (current == null)
            {
                return null;
            }
        }
        if (current == first)
        {
            first = current.next;
        }
        else
        {
            current.previous.next = current.next;
        }
        if (current == last)
        {
            last = current.previous;
        }
        else
        {
            current.next.previous = current.previous;
        }
        return current;
    }

    public void displayForward()
    {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null)
        {
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }

    public void displayBackward()
    {
        System.out.print("List (last-->first): ");
        Link current = last;
        while (current != null)
        {
            current.displayLink();
            current = current.previous;
        }
        System.out.println("");
    }
}

public class DoublyLinkedApp
{
    public static void main(String[] args)
    {
        DoublyLinkedList theList = new DoublyLinkedList();

        theList.insertFirst(22);
        theList.insertFirst(44);
        theList.insertFirst(66);

        theList.insertLast(11);
        theList.insertLast(33);
        theList.insertLast(55);

        theList.displayForward();
        theList.displayBackward();

        theList.deleteFirst();
        theList.deleteLast();
        theList.deleteKey(11);

        theList.displayForward();

        theList.insertAfter(22, 77);
        theList.insertAfter(33, 88);

        theList.displayForward();
    }
    /*
    * Result
    *   List (first-->last): 66 44 22 11 33 55 
        List (last-->first): 55 33 11 22 44 66 
        List (first-->last): 44 22 33 
        List (first-->last): 44 22 77 33 88 
    * */
}