《知识点021：Java中LinkedList排序（2种））》

 一、LinkedList类介绍

LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.，它和ArrayList一样实现了List接口，但是她执行插入和删除操作时比ArrayList更加高效，因为她是基于链表的，但同时也决定了她在随机访问方面要比ArrayList弱一点。

1.1：结构原理

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

 

1.2：构造方法

public LinkedList() {//生成空的链表
    header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {//复制构造函数
    this();
    addAll(c);
}

第一个构造方法不接受参数，将header实例的previous和next全部指向header实例（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），这样整个链表其实就只有header一个节点，用于表示一个空的链表。执行完构造函数后，header实例自身形成一个闭环，如下图所示：

第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。

 

二、LinkedList排序（2种）

LinkedList通过Collections.sort进行排序，代码如下：

2.1：降序

public class Person1 implements Comparable < Person1 > {
    private Float height;
    private String name;
 
    Person1(float height) {
        this.height = height;
    }
 
    public Float getHeight() {
        return height;
    }
 
    public void setHeight(float height) {
        this.height = height;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    @Override public int compareTo(Person1 p) {
        if (this.getHeight() < p.getHeight()) {
            return 1;
 
        } else if (this.getHeight() > p.getHeight()) {
            return - 1;
        } else {
            return 0;
        }
    }
}
 
public class Question3_1 {
 
    public static void main(String[] args) {
        Person1 p1 = new Person1(23.4f);
        p1.setName("Stud1");
        Person1 p2 = new Person1(2.34f);
        p2.setName("Stud2");
        Person1 p3 = new Person1(34.32f);
        p3.setName("Stud3");
        Person1 p4 = new Person1(56.45f);
        p4.setName("Stud4");
        Person1 p5 = new Person1(21.4f);
        p5.setName("Stud5");
 
        LinkedList < Person1 > al = new LinkedList < Person1 > ();
 
        al.add(p1);
        al.add(p2);
        al.add(p3);
        al.add(p4);
        al.add(p5);
 
        Collections.sort(al); //这里控制降序
        for (Person1 p: al) System.out.println(p.getName() + " " + p.getHeight());
    }
}

运行结果：

Stud4 56.45
Stud3 34.32
Stud1 23.4
Stud5 21.4
Stud2 2.34

2.2：升序

修改上面代码 Collections.sort(al,Collections.reverseOrder());//更改为升序

运行结果：
Stud2 2.34
Stud5 21.4
Stud1 23.4
Stud3 34.32
Stud4 56.45