連結清單是什麼
連結清單是一種很常見的資料結構，是一種線性結構。他的資料形式類似我們日常認知中的鎖鍊，使用每個節點儲存下一個節點的指針的方式實作關聯。
連結清單在删除和新增的時候，隻需要修改前一個結點的指向位置即可，和數組相比并不需要進行整體位移，是以連結清單在修改操作上比數組要優秀。
簡單的連結清單示例
使用連結清單的集合
我們長接觸的連結清單結構主要有LinkedList、LinkedHashMap，隊列、棧等。
連結清單分類
我們目前經常用到的連結清單主要有下面幾種：
- 單連結清單
- 雙向連結清單
- 循環連結清單
單向連結清單
單向連結清單的一個節點被分為了兩個部分，一部分為節點資料儲存了節點了資訊。一部分為next的位址。
根據這個結構，單向連結清單隻能向一個方向進行周遊，查找一個節點的時候需要從第一個節點開始每次通路下一個節點，直到找到需要的位置。
圖示
操作
新增
此時為原始資料
在B和C之間添加O節點
将O的next坐标設定為之前B的next
流程為：
- 定位需要添加節點的位置B。
- 将B指向的nextc，修改為o
- 将O中next指向為c。此時完成資料插入
删除
此時為原始資料，準備一處O節點
此時獲得O節點的上一節點，同時擷取O節點next的指向資訊
流程為：
- 周遊連結清單找到需要删除的節點的節點以及其上一節點。
- 将上一節點的next指向修改為被删除節點的next
雙向連結清單
連結清單中的元素，除了能夠指向下一個節點，同時還能夠指向上一個元素節點，每個節點都存在兩個指針。整個關聯關系從前向後和從後向前都是可以的。
圖示
操作
新增
添加節點O，修改B和C節點的坐标
流程為：
- 确定需要插入節點的位置。
- 将插入位置的上一節點的next指向新的節點，然後将原來下一節點的pre指向新的節點
- 添加新的節點的next和pre分别指向新的前後坐标
删除
流程為：
- 首先确定删除節點，然後根據pre和next确定其前後節點
- 将pre節點的next指向為被删除節點的next，将next節點的pre指向為被删除節點的pre資訊
循環連結清單
循環連結清單指的是在連結清單的最後一個結點上指向第一個節點進而實作循環
圖示
判斷循環連結清單
一個完美的圓形連結清單可以從某處開始循環當再次周遊到此位置的時候可以确定其為循環連結清單。但是對于其他情況則不能這樣使用。比如這種部分循環的連結清單。在執行周遊後連結清單會在某處進入生死循環。
是以我們可以使用快慢指針的思想的思想去判斷是否循環連結清單。
快慢指針的原理是：我們定義兩個節點指針fast、slow。對這兩個指針設定不同的步長，比如fast步長2、slow步長1。然後讓他們同時從頭部節點開始周遊連結清單，如果連結清單是循環的則快慢指針總會相遇。
當然除了快慢指針我們還可以将我們之前周遊過的資料緩存起來。每次周遊下一節點的時候去緩存中比對下此節點是否已經被周遊過。如果緩存中已經存在則證明連結清單中存在環形結構。
棧
棧也是一種線性表，但是和連結清單不同之處。棧隻允許從尾部操作資料。也就是隻能對尾部的元素進行新增和删除操作。它按照先進先出原則進行操作（last in first out）
棧的資料添加和移除
java中的棧
java中
java.util.Stack
實作了出棧和入棧的操作，其通過繼承Vector添加了自己的方法來實作入棧和出棧，還是用的父類Vector的方法來執行元素操作。
棧的操作
初始化
壓棧
壓棧的時候使用
出棧
按照真正的棧的操作，執行出棧的時候棧頂元素會被移除，但是在
java.util.Stack
中提供了兩個方法
peek：會檢視棧頂元素但是并不會移除它。
pop：類似真正的出棧操作，會移除棧頂元素
s.peek();
s.pop();
判空
java為棧提供了
empty
方法來進行空值判斷。
周遊
java為棧提供了
removeAllElements
方法來進行空值判斷。
清空
java為棧提供了
elements
方法來進行空值判斷。
隊列
和棧相反，隊列是一種隻允許一端進行插入而在另一端進行删除的線性結構
隊列的操作
假如存在以下隊列
删除
執行删除操作的時候會将頭部元素取出
插入
當我們插入資料的時候隻能從尾部插入
java中的隊列
JAVA中使用了
java.util.Queue
來實作了隊列的相關内容。
雙端隊列
在JAVA中對隊列做了一個擴充使用了
java.util.Deque
定義了一種可以從頭部和尾部進行删除操作的隊列。
java中隊列關系圖
java中隊列的實作
在JAVA中對于隊列提供了兩種實作：
java.util.concurrent.LinkedBlockingQueue
基于連結清單的實作
java.util.concurrent.ArrayBlockingQueue
基于數組的實作