學(xué)習(xí)目標(biāo)
- 能夠說(shuō)出常見(jiàn)得數(shù)據(jù)結(jié)構(gòu)有哪些及其特點(diǎn)
- 能夠說(shuō)出數(shù)組結(jié)構(gòu)特點(diǎn)
- 能夠說(shuō)出棧結(jié)構(gòu)特點(diǎn)
- 能夠說(shuō)出數(shù)組結(jié)構(gòu)特點(diǎn)
- 能夠說(shuō)出單向鏈表結(jié)構(gòu)特點(diǎn)
- 能夠說(shuō)出紅黑樹特點(diǎn)
- 能夠說(shuō)出list集合特點(diǎn)
- 能夠說(shuō)出Set集合的特點(diǎn)
- 能夠說(shuō)出哈希表的特點(diǎn)
- 使用HashSet集合存儲(chǔ)自定義元素
- 能夠說(shuō)出可變參數(shù)的格式
- 能夠使用集合工具類
- 能夠使用Comparator比較器進(jìn)行排序
1.棧結(jié)構(gòu)特點(diǎn)
棧又稱堆棧，它是運(yùn)算受限得線性表烤宙，只允許一端進(jìn)行插入和刪除（只有一個(gè)口遍烦，先進(jìn)后出，類似彈夾）
2.隊(duì)列結(jié)構(gòu)特點(diǎn)
隊(duì)列只允許一端插入一端刪除（兩個(gè)口躺枕，先進(jìn)先出乳愉，類似安檢）
3.數(shù)組結(jié)構(gòu)特點(diǎn)
數(shù)組，在內(nèi)存中開辟一段連續(xù)的內(nèi)存空間屯远。特點(diǎn)是查詢快蔓姚，增刪慢。原因是查詢數(shù)組中長(zhǎng)度固定并連續(xù)慨丐，知道開頭位置和偏移量就能知道元素具體地址坡脐；增刪慢是因?yàn)樾枰匦聞?chuàng)建新數(shù)組，復(fù)制刪除或增加的其他元素到新數(shù)組中房揭，在指定位置進(jìn)行添加和刪除操作备闲。
4.鏈表結(jié)構(gòu)特點(diǎn)
鏈表，查詢慢捅暴，增刪快恬砂。因?yàn)殒湵淼刂贩沁B續(xù)，必須重頭開始查詢蓬痒，當(dāng)增加/刪除元素對(duì)鏈表結(jié)構(gòu)沒(méi)有影響泻骤，所以增刪快。
單向列表：鏈表中只有一個(gè)鏈子梧奢，不能保證元素順序
-
雙向列表：鏈表中有兩條鏈子狱掂，專門紀(jì)錄元素順序，是一個(gè)有序集合亲轨。
image
image
5.紅黑樹特點(diǎn)
紅黑樹趋惨，趨近于平衡樹，查詢得速度非车胛茫快器虾，查詢?nèi)~子節(jié)點(diǎn)最大次數(shù)和最小次數(shù)不能超過(guò)2倍
6.list接口特點(diǎn)
list讯嫂，是一個(gè)存取有序得集合，允許出現(xiàn)重復(fù)元素兆沙，可以通過(guò)索引訪問(wèn)指定元素端姚。
public void add(int index, E element) : 將指定的元素，添加到該集合中的指定位置上挤悉。
public E get(int index) :返回集合中指定位置的元素。
public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素巫湘。
public E set(int index, E element) :用指定元素替換集合中指定位置的元素,返回值的更新前的元素装悲。
- ArrayList集合 底層是一個(gè)數(shù)組結(jié)構(gòu)，查詢快尚氛，增刪慢诀诊。
- LinkedList集合 底層是鏈表結(jié)構(gòu)，查詢慢阅嘶，增刪快属瓣。
public void addFirst(E e) :將指定元素插入此列表的開頭。
public void addLast(E e) :將指定元素添加到此列表的結(jié)尾讯柔。
public E getFirst() :返回此列表的第一個(gè)元素抡蛙。
public E getLast() :返回此列表的最后一個(gè)元素。
public E removeFirst() :移除并返回此列表的第一個(gè)元素魂迄。
public E removeLast() :移除并返回此列表的最后一個(gè)元素粗截。
public E pop() :從此列表所表示的堆棧處彈出一個(gè)元素。
public void push(E e) :將元素推入此列表所表示的堆棧捣炬。
public boolean isEmpty() ：如果列表不包含元素熊昌，則返回true。
- Vector集合單線程集合
7.Set接口的特點(diǎn)
無(wú)序集合湿酸，不允許重復(fù)元素婿屹。沒(méi)有索引，沒(méi)有帶索引得方法推溃，不能for循環(huán)遍歷
- HashSet是 Set 接口的一個(gè)實(shí)現(xiàn)類昂利，不允許重復(fù)元素，存取順序可能不一致铁坎。
- hash值：是一個(gè)十進(jìn)制整數(shù)页眯，系統(tǒng)隨機(jī)給出（是邏輯地址，不是真實(shí)得存儲(chǔ)物理地址）
HashSet存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（哈希表）厢呵，jdk>=1.8 哈希表=數(shù)組+紅黑樹 窝撵，jdk<1.8 哈希表=數(shù)組+鏈表。
1.Hashset存儲(chǔ)數(shù)據(jù)步驟：
- 第一步襟铭，開辟數(shù)組空間碌奉，先計(jì)算元素得hash值
- 第二步短曾，不同哈希值放在數(shù)組空間內(nèi)，相同hash值形成鏈表（紅黑樹）==【當(dāng)鏈表長(zhǎng)度超過(guò)8位赐劣，會(huì)把鏈表轉(zhuǎn)成紅黑樹】==
2.set元素不允許存儲(chǔ)重復(fù)元素原理
set元素在調(diào)用add()方法時(shí)嫉拐，add()方法會(huì)調(diào)用元素得hashcode方法和equals方法，判斷是否重復(fù)魁兼。
3.HashSet存儲(chǔ)自定義類型元素
需求：同名同年齡婉徘，視為同一個(gè)人，只能存儲(chǔ)一次咐汞。
回答：重寫equals()和hashCode()方法盖呼。
代碼如下：
public class Student {
private String name;
private int age;
public Student() {}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@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);
}
}
public class HashSetDemo2 {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象 該集合中存儲(chǔ) Student類型對(duì)象
HashSet<Student> stuSet = new HashSet<Student>();
//存儲(chǔ)
Student stu = new Student("于謙", 43);
stuSet.add(stu);
stuSet.add(new Student("郭德綱", 44));
stuSet.add(new Student("于謙", 43));
stuSet.add(new Student("郭麒麟", 23));
stuSet.add(stu);
for (Student stu2 : stuSet) {
System.out.println(stu2);
}
}
}
執(zhí)行結(jié)果：
Student [name=郭德綱, age=44]
Student [name=于謙, age=43]
Student [name=郭麒麟, age=23]
4.LinkedHashSet集合特點(diǎn)
繼承Hashset集合,不重復(fù)，底層是哈希表（數(shù)組+鏈表/紅黑樹）+鏈表（紀(jì)錄元素得存儲(chǔ)位置）,保證元素有序化撕。
5.可變參數(shù)
jdk1.5之后出現(xiàn)的新特性几晤，方法類型已知，個(gè)數(shù)未知.（數(shù)據(jù)類型 ...）,其原理底層是一個(gè)數(shù)組植阴，根據(jù)傳遞參數(shù)不同蟹瘾，創(chuàng)建不同長(zhǎng)度數(shù)組來(lái)存儲(chǔ)參數(shù)個(gè)數(shù)。
8.Collections集合工具類
public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素掠手。
public static void shuffle(List<?> list) 打亂順序 :打亂集合順序憾朴。
public static <T> void sort(List<T> list) :將集合中元素按照默認(rèn)規(guī)則排序。
public static <T> void sort(List<T> list喷鸽，Comparator<? super T> ) :將集合中元素按照指定規(guī)則排 序伊脓。
1.Comparator比較器
public static <T> void sort(List<T> list) :將集合中元素按照默認(rèn)規(guī)則排序。
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.charAt(0) ‐o1.charAt(0);
}
});
public class Student implements Comparable<Student> {
@Override
public int compareTo(Student o) {
return this.age‐o.age;//升序 } }
}
}
