List、Set、數據結構、Collections

初次學習,涉及到List集合,Set集合和數據結構方面的一些知識,有錯誤還請批評指正

數據結構

數據存儲的常用結構有：棧、隊列、數組、鏈表和紅黑樹。

棧

先進後出(FILO).

隊列

先進先出(FIFO).

數組

有序的元素序列,以索引訪問.查詢快,增刪慢.

鏈表

鏈式結構,查詢慢,增刪快.通過地址進行連接.
單向鏈表:結點包括兩個內容,一個是存儲元素,一個是下一個元素的地址.
雙向鏈表:結點包括3個部分,前一個元素的存儲地址,當前結點存儲的元素,後一個元素的存儲地址

紅黑樹

二叉樹,查詢快.根節點的左邊數據小於右邊數據.

關於使用java具體實現上面的數據結構以後寫,當前只需要瞭解一下他們的特性就可以.

List集合

java.util.List 介面繼承自Collection 介面，是單列集合的一個重要分支，在List集合中允許出現重覆的元素，所有的元素是以一種線
性方式進行存儲的，在程式中可以通過索引來訪問集合中的指定元素。另外，List集合還有一個特點就是元素有序，即元素的存入順序和
取出順序一致。(remove(Object obj)只能移除集合中第一個相同的元素)

List集合的特點:

• 元素存儲有序.
• 可以存儲重覆元素
• 有索引,可以通過索引來訪問元素

常用的方法有(list的特有方法大都與索引相關):

• public void add(int index, E element) : 將指定的元素，添加到該集合中的指定位置上。
• public E get(int index) :返回集合中指定位置的元素。
• public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
• public E set(int index, E element) :用指定元素替換集合中指定位置的元素,返回值的更新前的元素。

List的子類

• Vector : 線程安全相關
• ArrayList : 底層數組實現
• LinkedList : 鏈表實現

ArrayList

特有的常用方法:

• int indexOf(Object o) 返回此列表中指定元素的第一次出現的索引，如果此列表不包含元素，則返回-1。

LinkedList

java.util.LinkedList 集合數據存儲的結構是鏈表結構。方便元素添加、刪除的集合。

• 鏈表結構,查詢慢,增刪快
• 包含大量操作首尾元素的方法

特有的方法:

• public void addFirst(E e) :將指定元素插入此列表的開頭。
• public void addLast(E e) :將指定元素添加到此列表的結尾。

• public void push(E e) :將元素推入此列表所表示的堆棧。等效於addFirst

• public E getFirst() :返回此列表的第一個元素。
• public E getLast() :返回此列表的最後一個元素。

• E get(int index) 返回此列表中指定位置的元素。

• public E removeFirst() :移除並返回此列表的第一個元素。
• public E removeLast() :移除並返回此列表的最後一個元素。

• public E pop() :從此列表所表示的堆棧處彈出一個元素。等效於removeFirst

• int indexOf(Object o) 返回此列表中指定元素的第一次出現的索引，如果此列表不包含元素，則返回-1。
  

• public boolean isEmpty() ：如果列表不包含元素，則返回true。

Vector

這個在使用上和ArrayList基本沒有區別,要註意的是二者的區別:

相同點:

• 二者的底層實現都是數組結構.
  不同點:
• Vector是與線程安全相關的,效率低下.ArrayList是線程不安全的,但是高效.

Set介面

java.util.Set介面特點:

• 不允許存儲重覆元素
• 無索引(意味著不能用普通for迴圈遍歷)

HashSet

特點:

• 不允許存儲重覆元素(存儲相同的元素在Set中只能保存一個,但程式不會出錯)
• 無索引(意味著不能用普通for迴圈遍歷)
• 存儲和讀取元素無序(順序可能不一致,在底層Set有他自己的排序規則)
• 底層使用哈希表結構

哈希值:

• int hashCode() 返回對象的哈希碼值。

HashSet集合存儲數據的結構:

• jdk8之前是:數組 + 鏈表
• jdk8之後是:數組 + 紅黑樹(二叉樹)
• 數組保存哈希值,存儲元素時,哈希值相同的保存在數組的下方.
• 當有多個元素的哈希值相同時(哈希衝突),這個時候保存的時候就會繼續向下排列.具體的看下圖.
• 當有8個及以上的元素的哈希值相同,鏈式結構就會轉化為紅黑樹結構.

HashSet如何保證元素唯一?與hashCode()方法與equals()方法相關:

舉個例子:

public class HashSet {

    public static void main(String[] args) {
        Set<String> set = new java.util.HashSet<>();
        set.add(new String("abc"));
        set.add(new String("abc"));
        set.add("abc");
        set.add("重地");
        set.add("通話");

        System.out.println(set); // [重地, 通話, abc]
    }
}

重地和通話兩個字元串比較特殊,二者的哈希值相同,從這個例子也可以看出String重寫了hashCode()和equals()方法.

LinkedHashSet

特點:

• 有序
• 沒有索引
• 不可以存儲重覆元素
  哈希表(數組 + 鏈表/紅黑樹) + 鏈表(最後的鏈表是用來存儲存入順序的)

可變參數

定義格式:

修飾符 返回類型 方法名(參數類型...參數名){}

特點:

• 可變參數底層實現是數組

註意事項:可變參數必須在參數列表的最後一位,一個參數列表只能有一個可變參數.

Collections

工具類特點:

• 構造方法私有.
• 所有的方法和屬性靜態,直接用類名調用.

常用方法:
public static

Comparatable與Comparator

Comparable：強行對實現它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的compareTo方法
被稱為它的自然比較方法。只能在類中實現compareTo()一次，不能經常修改類的代碼實現自己想要的排序。實現
此介面的對象列表（和數組）可以通過Collections.sort（和Arrays.sort）進行自動排序，對象可以用作有序映射中
的鍵或有序集合中的元素，無需指定比較器。
Comparator強行對某個對象進行整體排序。可以將Comparator 傳遞給sort方法（如Collections.sort或
Arrays.sort），從而允許在排序順序上實現精確控制。還可以使用Comparator來控制某些數據結構（如有序set或
有序映射）的順序，或者為那些沒有自然順序的對象collection提供排序。

二者都存在時,優先使用Comparator.

Comparatable的例子:

public class Student implements Comparable<Student>{

    private String name;

    private int age;

    public Student() {
    }

    public Student(String name, int age) {

        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {

        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {

        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {

        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }


    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

ArrayList<String> list = new ArrayList<>();

Collections.addAll(list,"迪麗熱巴","鄭爽","李溪芮");

System.out.println(list);

Collections.sort(list);

System.out.println(list);

Comparator的例子:

// 還是上面的實體類
ArrayList<Student> list = new ArrayList<>();

list.add(new Student("Silme",20));
list.add(new Student("Roke",19));
list.add(new Student("Aoke",19));
list.add(new Student("Robin",18));
System.out.println(list);
Collections.sort(list, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        // 年齡自然排序
        int flag = o1.getAge() - o2.getAge();
        // 年齡相同,按照姓名排序
        if(flag == 0){
            flag = o1.getName().charAt(0)- o2.getName().charAt(0);
        }
        return flag;
    }
});
System.out.println(list);