擁抱大資料：凱哥帶你從零學大資料系列-學習大資料前奏(必讀)(點我)!
上一篇:擁抱大資料：凱哥帶你從零學大資料系列之Java篇---第十六章:集合基礎
課程重點:
- List的概念
- List的常用方法
- List的周遊
- 資料結構:數組與連結清單原理
- 資料結構:連結清單代碼實作(了解)
17.1. 存儲特點
List集合是單列集合，是Collection接口的子接口。Collection接口中所有的方法，這裡都有。同時，這個集合比Collection集合，多個若幹方法。
在List接口中，是有下标的概念的。多出來的這些方法，基本也都是圍繞着下标操作的。
17.2. List API
import java.util.ArrayList;
import java.util.List;
/**
* @Description List接口的方法
*/
public class Test1 {
public static void main(String[] args) {
// 1. 執行個體化一個ArrayList對象，向上轉型為接口類型。
List<String> list = new ArrayList<>();
// 2. 增元素
list.add("Lily");
list.add("Lucy");
list.add("Polly");
list.add("Jim");
// 3. 在集合中指定的下标位插入元素
list.add(2, "Tom");
// 4. 在集合中指定的下标位插入另外一個集合中所有的資料
list.addAll(2, list);
// 5. 删除集合中指定下标位的元素
// 傳回值：這個被删除的元素
System.out.println(list.remove(2));
// 6. 修改指定下标位的值
// 傳回被覆寫的值。
System.out.println(list.set(2, "AAA"));
// 7* 元素替換
// 将集合中的每一個元素，帶入到接口的方法中，用傳回值替換原來的元素
// list.replaceAll(ele -> ele.concat(".txt"));
// 8. 擷取指定下标位的元素。
System.out.println(list.get(2));
// 9. 擷取集合中的某一個元素第一次出現的下标
System.out.println(list.indexOf("Jim"));
// 10. 擷取集合中的某一個元素最後一次出現的下标
System.out.println(list.lastIndexOf("Jim"));
// 11. 從一個集合中，截取一部分，作為子集合。 [from, to)
List<String> sub = list.subList(2, 60);
System.out.println(list);
System.out.println(sub);
}
}
在List接口中，提供了一個排序的方法 sort
方法原型default void sort(Comparator<? super E> c)
這是一個系統封裝好的一個用來做排序的方法，由于集合中隻能存儲引用資料類型的資料，是以，需要明确兩個元素的大小關系。參數Comparator是一個對象大小比較的接口。在這個接口的方法中，有兩個參數，分别表示參與比較的兩個對象。傳回值是int類型，不看具體的值，隻看正負。
/**
* 兩個對象的大小比較方法
* @param o1 參與比較的一個對象
* @param o2 參與比較的另一個對象
* @return 比較的結果
* > 0 : o1 > o2
* == 0 : o1 == o2
* < 0 : o1 < o2
*/
int compare(T o1, T o2)
import java.util.ArrayList;
import java.util.List;
/**
* @Description 集合的元素排序
*/
public class Test2 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
// 2. 增元素
list.add("Lily");
list.add("Lucy");
list.add("Polly");
list.add("Jim");
// 排序: 按照兩個字元串的長度進行大小比較，升序排序
list.sort((e1, e2) -> e1.length() - e2.length());
}
}
由于List接口是繼承自Collection接口的，是以在Collection部分的三種周遊方式，都可以用來周遊List集合。同時，在List集合中，還添加了兩種用來周遊集合的其他方式。
17.5.1. 下标周遊
顧名思義， 類似于數組的下标周遊。 周遊集合中的所有的下标， 依次擷取指定下标位的元素。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
/**
* @Description List集合周遊
*/
public class List1 {
public static void main(String[] args) {
// 1. 執行個體化一個List集合，存儲若幹資料
List<Integer> list = new ArrayList<>();
Collections.addAll(list, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100);
// 2. 周遊
index(list);
}
/**
* 下标周遊法
* @param list 需要周遊的集合
*/
private static void index(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
// 擷取每一個元素
System.out.println(list.get(i));
}
}
}
這種方式， 類似于疊代器。 在List集合中， 有一個方法
listIterator()
， 可以擷取到一個
ListIterator
接口的引用。 而
ListIterator
是
Iterator
的子接口。 是以在保留了傳統的疊代器的疊代方法的基礎上， 還添加了若幹個其他的方法。
使用ListIterator， 在周遊集合中的元素的同時， 可以向集合中添加元素、删除元素、修改元素。
但是， 這裡對集合中的元素操作， 并不是使用 List 接口中的方法， 而是用 ListIterator 接口中的方法完成。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
/**
* @Description List集合周遊
*/
public class List1 {
public static void main(String[] args) {
// 1. 執行個體化一個List集合，存儲若幹資料
List<Integer> list = new ArrayList<>();
Collections.addAll(list, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100);
// 2. 周遊
listIterator(list);
}
/**
* 使用清單疊代器完成周遊
* @param list 需要周遊的集合
*/
private static void listIterator(List<Integer> list) {
// 1. 擷取到 ListIterator 對象
ListIterator<Integer> iterator = list.listIterator(4);
// 2. 循環周遊
while (iterator.hasNext()) {
// 2.1. 擷取疊代器目前指向的元素
Integer ele = iterator.next();
System.out.println(ele);
// 2.2. 元素操作
if (ele == 30) {
// 添加：在疊代器目前指向的元素的下一位插入一個元素
// 新增的元素，沒有存在于疊代清單中，疊代器會直接指向原集合中的下一個元素
// iterator.add(300);
// 删除：删除疊代器目前指向的這一位元素
// iterator.remove();
// 修改：修改疊代器目前指向的這一位元素
// iterator.set(300);
}
}
System.out.println(list);
}
}
17.6. ArrayList與LinkedList
- 相同點：
- 都是List集合的常用的實作類。
- 對集合中的元素操作的方法基本一緻。
- 不同點：
- ArrayList底層實作是數組， 使用數組這種資料結構進行資料的存儲。
- LinkedList底層實作是雙連結清單， 使用雙連結清單這種資料結構進行資料的存儲。
- 如果對集合中的元素， 增删操作不怎麼頻繁， 查詢操作比較頻繁。 使用ArrayList。
- 如果對集合中的元素， 增删操作比較頻繁， 查詢操作不怎麼頻繁。 使用LinkedList。
17.7. 雙連結清單資料結構
17.7.1. 連結清單簡介
連結清單， 其實是一種比較常見的資料結構。 增删效率比較高， 查詢效率比較低。
資料在連結清單中存儲， 是以節點為機關進行存儲的。 節點之間在記憶體上是不連續的。 雙向連結清單中的每一個節點， 除了記錄了目前節點存儲的元素之外， 還記錄了上一個節點和下一個節點的位址。
17.7.2. 示例代碼
/**
* @Description 使用連結清單資料結構實作一個自定義的集合(模拟LinkedList)
*/
public class MyLinkedList<E> {
// 連結清單中，元素是以節點的形式存儲的
// 内部類，表示一個節點
private class Node {
E element; // 表示這個節點需要存儲的元素
Node previous; // 上一個節點的位址
Node next; // 下一個節點的位址
Node(E element) {
this.element = element;
}
}
private Node first; // 描述連結清單中的首節點
private Node last; // 描述連結清單中的尾結點
private int count; // 描述連結清單中節點數量
/**
* 在目前集合中添加一個元素
* @param element 要添加的元素
*/
public void add(E element) {
// 1. 執行個體化一個節點，用來存儲這個節點要存儲的元素
Node node = new Node(element);
// 2. 判斷目前的連結清單是否是空連結清單
if (count == 0) {
// 說明目前連結清單是一個空連結清單
this.first = node;
}
else {
// 說明目前連結清單不是一個空連結清單
// 需要把目前節點挂在尾結點的後面
this.last.next = node;
node.previous = this.last;
}
this.last = node; // 新增的這個節點，就是目前連結清單中的新的尾結點
count++; // 節點數量+1
}
/**
* 在連結清單中，指定的下标位置插入一個元素
* @param index 指定的下标位
* @param element 需要插入的元素
*/
public void add(int index, E element) {
// 1. 執行個體化一個新的節點
Node node = new Node(element);
// 2. 節點關聯
if (index == 0) {
// 說明在首位插入一個新的節點
this.first.previous = node;
node.next = this.first;
// 這個節點就是新的首節點
this.first = node;
}
else if (index == count) {
// 說明在尾結點插入一個新的節點
this.last.next = node;
node.previous = this.last;
// 這個新的節點就是新的尾結點
this.last = node;
}
else {
// 說明在中間節點插入一個元素
// 1. 擷取指定下标的節點
Node target = getNode(index);
// 節點關聯
node.next = target;
node.previous = target.previous;
target.previous.next = node;
// 這個節點設定需要在後面
target.previous = node;
}
count++;
}
/**
* 删除指定下标位的元素
* @param index 指定的下标位
* @return 剛剛被删除的元素
*/
public E remove(int index) {
// 1. 擷取需要被删除的這個節點
Node node = getNode(index);
// 2. 删除節點
removeNode(node);
return node.element;
}
/**
* 删除一個節點
* @param node 需要被删除的節點
*/
private void removeNode(Node node) {
// 當一個連結清單中有且隻有一個節點的情況
if (count == 1) {
this.first = null;
this.last = null;
count--;
return;
}
// 判斷是否删除的是首節點
if (node == this.first) {
this.first = this.first.next; // 設定新的首節點
// 取消新的首節點與上一個節點的關聯
this.first.previous.next = null;
this.first.previous = null;
}
else if (node == this.last) {
// 設定新的尾結點
this.last = this.last.previous;
// 取消新的尾結點與下一個節點的關聯
this.last.next.previous = null;
this.last.next = null;
}
else {
// 删除的是中間節點
node.previous.next = node.next;
node.next.previous = node.previous;
node.previous = null;
node.next = null;
}
count--;
}
/**
* 通過下标擷取指定的節點
* @param index 指定的下标
* @return 下标對應的節點
*/
private Node getNode(int index) {
// 1. 判斷下标的合法性
if (index < 0 || index >= count) {
throw new IndexOutOfBoundsException("size() = " + count + ", index = " + index);
}
// 2. 循環向下查找指定的節點
Node node = this.first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 删除連結清單中指定的元素
* @param element 要删除的元素
* @return 删除的結果(是否删除，如果删除了資料，傳回true)
*/
public boolean remove(E element) {
// 1. 通過元素擷取指定的節點
Node node = getNode(element);
// 2. 判斷這個節點是否存在
if (node == null) {
// 說明這個節點不存在
return false;
}
// 3. 删除節點
removeNode(node);
return true;
}
/**
* 通過元素擷取節點
* @param element 元素
* @return 節點
*/
private Node getNode(E element) {
Node node = this.first;
while (node != null) {
if (node.element.equals(element)) {
return node;
}
node = node.next;
}
// 如果找不到這個元素
return null;
}
/**
* 清空連結清單中的所有的資料
*/
public void clear() {
this.first = null;
this.last = null;
count = 0;
}
/**
* 将連結清單中指定下标位的元素，修改成新的元素
* @param index 要修改元素的下标
* @param element 新的元素
* @return 被覆寫的，修改之前的資料
*/
public E set(int index, E element) {
// 1. 通過下标擷取指定的節點
Node node = getNode(index);
// 2. 備份一次原來的元素
E ele = node.element;
// 3. 設定這個節點新的元素
node.element = element;
// 4. 傳回覆寫之前的資料
return ele;
}
/**
* 擷取連結清單中指定下标位的元素
* @param index 下标位
* @return 指定的元素
*/
public E get(int index) {
// 1. 擷取指定的節點
Node node = getNode(index);
// 2. 傳回這個節點的資料
return node.element;
}
public int size() {
return count;
}
/**
* 判斷一個連結清單中是否包含指定的元素
* @param element 查詢的元素
* @return 是否包含
*/
public boolean contains(E element) {
return indexOf(element) != -1;
}
/**
* 查詢連結清單中某一個元素第一次出現的下标
* @param element 查詢的元素
* @return 下标
*/
public int indexOf(E element) {
// 從首節點開始，周遊每一個元素
Node node = this.first;
for (int i = 0; i < count; i++) {
// 判斷目前周遊的這個節點，是否是要查詢的節點
if (node.element.equals(element)) {
return i;
}
// 周遊下一個節點
node = node.next;
}
return -1;
}
@Override
public String toString() {
if (count == 0) {
return "[]";
}
// 1. 執行個體化一個StringBuilder進行字元串的拼接
StringBuilder stringBuilder = new StringBuilder("[");
// 2. 周遊每一個節點
Node node = this.first;
for (int i = 0; i < count; i++) {
// 元素的拼接
stringBuilder.append(node.element).append(", ");
// 節點向後指向
node = node.next;
}
// 3. 将最後兩位替換成 ]
stringBuilder.replace(stringBuilder.length() - 2, stringBuilder.length(), "]");
return stringBuilder.toString();
}
}
擁抱大資料：凱哥帶你從零學大資料系列之Java篇---第十八章:集合(Set)zhuanlan.zhihu.com