线性表-链式存储结构(数据结构及算法03)

一、定义:

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

二、种类

1、单链表

应用：MessageQueue
插入：enqueueMessage(Message msg, long when)
删除：next()

2、单循环链表

3、双链表

radixSort.png

麻将实体类（链表基数排序-适合20-30个数据效率较高）

public class Mahjong {
    public int suit;//筒，万，索
    public int rank;//点数 一  二  三

    public Mahjong(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return "("+this.suit+" "+this.rank+")";
    }
}

麻将排序算法

    public static void radixSort(LinkedList<Mahjong> list){
        //先对点数进行分组
        LinkedList[] rankList=new LinkedList[9];
        for (int i=0;i<rankList.length;i++){
            rankList[i]=new LinkedList();
        }
        //把数据一个一个的放入到对应的组中
        while(list.size()>0){
            //取一个
            Mahjong m=list.remove();
            //放到组中
            rankList[m.rank-1].add(m);
        }
        //把9个组合到一起
        for (int i = 0; i < rankList.length; i++) {
            list.addAll(rankList[I]);
        }

        //先花色数进行分组
        LinkedList[] suitList=new LinkedList[3];
        for (int i=0;i<suitList.length;i++){
            suitList[i]=new LinkedList();
        }
        //把数据一个一个的放入到对应的组中
        while(list.size()>0){
            //取一个
            Mahjong m=list.remove();
            //放到组中
            suitList[m.suit-1].add(m);
        }
        //把3个组合到一起
        for (int i = 0; i < suitList.length; i++) {
            list.addAll(suitList[I]);
        }
    }

测试代码

    @org.junit.Test
    public void testRadixSort(){
        LinkedList<Mahjong> list=new LinkedList<Mahjong>();
        list.add(new Mahjong(3,1));
        list.add(new Mahjong(2,3));
        list.add(new Mahjong(3,7));
        list.add(new Mahjong(1,1));
        list.add(new Mahjong(3,8));
        list.add(new Mahjong(2,2));
        list.add(new Mahjong(3,2));
        list.add(new Mahjong(1,3));
        list.add(new Mahjong(3,9));
        System.out.println(list);
        radixSort(list);
        System.out.println(list);
    }

打印结果

[(3 1), (2 3), (3 7), (1 1), (3 8), (2 2), (3 2), (1 3), (3 9)]
[(1 1), (1 3), (2 2), (2 3), (3 1), (3 2), (3 7), (3 8), (3 9)]

4、双循环链表

三、优缺点：

优点：插入、删除速度快
缺点：不支持随机访问