學習編程至少要知道以下這些數據結構知識

List集合

掌握了Collection接口的使用後，再來看看Collection接口中的子類

Collection中的常用幾個子類（ java.util.List 集合、java.util.Set 集合）

List接口介紹

java.util.List 接口繼承自Collection 接口，是單列集合的一個重要分支，習慣性地會將實現了List 接口的對象稱為List集合。在List集合中允許出現重複的元素，所有的元素是以一種線性方式進行存儲的，在程序中可以通過索引來訪問集合中的指定元素。另外，List集合還有一個特點就是元素有序，即元素的存入順序和取出順序一致。

List接口特點：

1. 它是一個元素存取有序的集合。

2. 它是一個帶有索引的集合，通過索引就可以精確的操作集合中的元素（與數組的索引是一個道理）。

3. 集合中可以有重複的元素，通過元素的equals方法，來比較是否為重複的元素。

List接口中常用方法

List作為Collection集合的子接口，不但繼承了Collection接口中的全部方法，而且還增加了一些根據元素索引來操作集合的特有方法，如下：

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

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

棧：stack,又稱堆棧，它是運算受限的線性表，其限制是僅允許在標的一端進行插入和刪除操作，不允許在其他任何位置進行添加、查找、刪除等操作。

簡單的說：採用該結構的集合，對元素的存取有如下的特點

先進後出（即，存進去的元素，要在後它後面的元素依次取出後，才能取出該元素）。例如，子彈壓進彈夾，先壓進去的子彈在下面，後壓進去的子彈在上面，當開槍時，先彈出上面的子彈，然後才能彈出下面的子彈。棧的入口、出口的都是棧的頂端位置。

壓棧：就是存元素。即，把元素存儲到棧的頂端位置，棧中已有元素依次向棧底方向移動一個位置。

彈棧：就是取元素。即，把棧的頂端位置元素取出，棧中已有元素依次向棧頂方向移動一個位置。

隊列

隊列：queue,簡稱隊，它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。

先進先出（即，存進去的元素，要在後它前面的元素依次取出後，才能取出該元素）。

隊列的入口、出口各佔一側。例如，下圖中的左側為入口，右側為出口。

數組

數組:Array,是有序的元素序列，數組是在內存中開闢一段連續的空間，並在此空間存放元素。

簡單的說,採用該結構的集合，對元素的存取有如下的特點：

查找元素快：通過索引，可以快速訪問指定位置的元素

增刪元素慢

指定索引位置增加元素：需要創建一個新數組，將指定新元素存儲在指定索引位置，再把原數組元素根據索引，複製到新數組對應索引的位置

指定索引位置刪除元素：需要創建一個新數組，把原數組元素根據索引，複製到新數組對應索引的位置，原數組中指定索引位置元素不復制到新數組中

鏈表

鏈表:linked list,由一系列結點node（鏈表中每一個元素稱為結點）組成，結點可以在運行時i動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。我們常說的鏈表結構有單向鏈表與雙向鏈表，那麼這裡給大家介紹的是單向鏈表。

多個結點之間，通過地址進行連接。例如，多個人手拉手，每個人使用自己的右手拉住下個人的左手，依次類推，這樣多個人就連在一起了。

查找元素慢：想查找某個元素，需要通過連接的節點，依次向後查找指定元素

增刪元素快：

紅黑樹

二叉樹：binary tree ,是每個結點不超過2的有序樹（tree） 。

簡單的理解，就是一種類似於我們生活中樹的結構，只不過每個結點上都最多隻能有兩個子結點。

二叉樹是每個節點最多有兩個子樹的樹結構。頂上的叫根結點，兩邊被稱作“左子樹”和“右子樹”。

我們要說的是二叉樹的一種比較有意思的叫做紅黑樹，紅黑樹本身就是一顆二叉查找樹，將節點插入後，該樹仍然是一顆二叉查找樹。

紅黑樹可以通過紅色節點和黑色節點儘可能的保證二叉樹的平衡，從而來提高效率