[TOC] ## 列表 List 概述 1. 列表`List`：存放數據，數據按順序排列，可以依次入隊和出隊，有序號關系，可以取出某序號的數據。 2. 先進先出的`隊列 (queue)`和先進后出的`棧（stack）`都是列表。 3. 大家也經常聽說一種叫`線性表`的數據結構，表示具有相同特性的數據元素的有限序列，實際上就是`列表`的同義詞。 列表的實現有`順序表示`或`鏈式表示` * 順序(數組)表示：指的是用一組`地址連續的存儲單元`依次存儲線性表的數據元素，稱為線性表的`順序存儲結構`。它以`物理位置相鄰`來表示線性表中數據元素間的邏輯關系，可隨機存取表中任一元素。順序表示的又叫`順序表`，也就是用數組來實現的列表。 * 鏈式(鏈表)表示：指的是用一組 任意的存儲單元 存儲線性表中的數據元素，稱為線性表的 鏈式存儲結構。它的存儲單元可以是連續的，也可以是不連續的。在表示數據元素之間的邏輯關系時，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息，也就是用鏈表來實現的列表。 雙端隊列: 鏈表形式的雙端列表 ## 實現雙端列表 ``` // 雙端列表，雙端隊列 type DoubleList struct { head *ListNode // 指向鏈表頭部 tail *ListNode // 指向鏈表尾部 len int // 列表長度 lock sync.Mutex // 為了進行并發安全pop操作 } // 列表節點 type ListNode struct { pre *ListNode // 前驅節點 next *ListNode // 后驅節點 value string // 值 } ```  ## 實例 <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) // 雙端列表，雙端隊列 type DoubleList struct { head *ListNode // 指向鏈表頭部 tail *ListNode // 指向鏈表尾部 len int // 列表長度 lock sync.Mutex // 為了進行并發安全pop操作 } // 列表節點 type ListNode struct { pre *ListNode // 前驅節點 next *ListNode // 后驅節點 value string // 值 } // 獲取節點值 func (node *ListNode) GetValue() string { return node.value } // 獲取節點前驅節點 func (node *ListNode) GetPre() *ListNode { return node.pre } // 獲取節點后驅節點 func (node *ListNode) GetNext() *ListNode { return node.next } // 是否存在后驅節點 func (node *ListNode) HashNext() bool { return node.pre != nil } // 是否存在前驅節點 func (node *ListNode) HashPre() bool { return node.next != nil } // 是否為空節點 func (node *ListNode) IsNil() bool { return node == nil } // 返回列表長度 func (list *DoubleList) Len() int { return list.len } // 添加節點到鏈表頭部的第N個元素之前，N=0表示新節點成為新的頭部 func (list *DoubleList) AddNodeFromHead(n int, v string) { // 加并發鎖 list.lock.Lock() defer list.lock.Unlock() // 索引超過列表長度，一定找不到，panic if n > list.len { panic("index out") } // 先找出頭部 node := list.head // 往后遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.next } // 新節點 newNode := new(ListNode) newNode.value = v // 如果定位到的節點為空，表示列表為空，將新節點設置為新頭部和新尾部 if node.IsNil() { list.head = newNode list.tail = newNode } else { // 定位到的節點，它的前驅 pre := node.pre // 如果定位到的節點前驅為nil，那么定位到的節點為鏈表頭部，需要換頭部 if pre.IsNil() { // 將新節點鏈接在老頭部之前 newNode.next = node node.pre = newNode // 新節點成為頭部 list.head = newNode } else { // 將新節點插入到定位到的節點之前 // 定位到的節點的前驅節點 pre 現在鏈接到新節點前 pre.next = newNode newNode.pre = pre // 定位到的節點鏈接到新節點之后 newNode.next = node node.pre = newNode } } // 列表長度+1 list.len = list.len + 1 } // 添加節點到鏈表尾部的第N個元素之后，N=0表示新節點成為新的尾部 func (list *DoubleList) AddNodeFromTail(n int, v string) { // 加并發鎖 list.lock.Lock() defer list.lock.Unlock() // 索引超過列表長度，一定找不到，panic if n > list.len { panic("index out") } // 先找出尾部 node := list.tail // 往前遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.pre } // 新節點 newNode := new(ListNode) newNode.value = v // 如果定位到的節點為空，表示列表為空，將新節點設置為新頭部和新尾部 if node.IsNil() { list.head = newNode list.tail = newNode } else { // 定位到的節點，它的后驅 next := node.next // 如果定位到的節點后驅為nil，那么定位到的節點為鏈表尾部，需要換尾部 if next.IsNil() { // 將新節點鏈接在老尾部之后 node.next = newNode newNode.pre = node // 新節點成為尾部 list.tail = newNode } else { // 將新節點插入到定位到的節點之后 // 新節點鏈接到定位到的節點之后 newNode.pre = node node.next = newNode // 定位到的節點的后驅節點鏈接在新節點之后 newNode.next = next next.pre = newNode } } // 列表長度+1 list.len = list.len + 1 } // 返回列表鏈表頭結點 func (list *DoubleList) First() *ListNode { return list.head } // 返回列表鏈表尾結點 func (list *DoubleList) Last() *ListNode { return list.tail } // 從頭部開始往后找，獲取第N+1個位置的節點，索引從0開始。 func (list *DoubleList) IndexFromHead(n int) *ListNode { // 索引超過或等于列表長度，一定找不到，返回空指針 if n >= list.len { return nil } // 獲取頭部節點 node := list.head // 往后遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.next } return node } // 從尾部開始往前找，獲取第N+1個位置的節點，索引從0開始。 func (list *DoubleList) IndexFromTail(n int) *ListNode { // 索引超過或等于列表長度，一定找不到，返回空指針 if n >= list.len { return nil } // 獲取尾部節點 node := list.tail // 往前遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.pre } return node } // 從頭部開始往后找，獲取第N+1個位置的節點，并移除返回 func (list *DoubleList) PopFromHead(n int) *ListNode { // 加并發鎖 list.lock.Lock() defer list.lock.Unlock() // 索引超過或等于列表長度，一定找不到，返回空指針 if n >= list.len { return nil } // 獲取頭部 node := list.head // 往后遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.next } // 移除的節點的前驅和后驅 pre := node.pre next := node.next // 如果前驅和后驅都為nil，那么移除的節點為鏈表唯一節點 if pre.IsNil() && next.IsNil() { list.head = nil list.tail = nil } else if pre.IsNil() { // 表示移除的是頭部節點，那么下一個節點成為頭節點 list.head = next next.pre = nil } else if next.IsNil() { // 表示移除的是尾部節點，那么上一個節點成為尾節點 list.tail = pre pre.next = nil } else { // 移除的是中間節點 pre.next = next next.pre = pre } // 節點減一 list.len = list.len - 1 return node } // 從尾部開始往前找，獲取第N+1個位置的節點，并移除返回 func (list *DoubleList) PopFromTail(n int) *ListNode { // 加并發鎖 list.lock.Lock() defer list.lock.Unlock() // 索引超過或等于列表長度，一定找不到，返回空指針 if n >= list.len { return nil } // 獲取尾部 node := list.tail // 往前遍歷拿到第 N+1 個位置的元素 for i := 1; i <= n; i++ { node = node.pre } // 移除的節點的前驅和后驅 pre := node.pre next := node.next // 如果前驅和后驅都為nil，那么移除的節點為鏈表唯一節點 if pre.IsNil() && next.IsNil() { list.head = nil list.tail = nil } else if pre.IsNil() { // 表示移除的是頭部節點，那么下一個節點成為頭節點 list.head = next next.pre = nil } else if next.IsNil() { // 表示移除的是尾部節點，那么上一個節點成為尾節點 list.tail = pre pre.next = nil } else { // 移除的是中間節點 pre.next = next next.pre = pre } // 節點減一 list.len = list.len - 1 return node } func main() { list := new(DoubleList) // 在列表頭部插入新元素 list.AddNodeFromHead(0, "I") list.AddNodeFromHead(0, "love") list.AddNodeFromHead(0, "you") // 在列表尾部插入新元素 list.AddNodeFromTail(0, "may") list.AddNodeFromTail(0, "happy") // 索引正常遍歷，比較慢 for i := 0; i < list.Len(); i++ { // 從頭部開始索引 node := list.IndexFromHead(i) // 節點為空不可能，因為list.Len()使得索引不會越界 if !node.IsNil() { fmt.Println(node.GetValue()) } } fmt.Println("----------") // 鏈表正常遍歷，特別快 // 先取出第一個元素 first := list.First() for !first.IsNil() { // 如果非空就一直遍歷 fmt.Println(first.GetValue()) // 接著下一個節點 first = first.GetNext() } fmt.Println("----------") // 元素一個個 POP 出來 for { node := list.PopFromHead(0) if node.IsNil() { // 沒有元素了，直接返回 break } fmt.Println(node.GetValue()) } fmt.Println("----------") fmt.Println("len", list.Len()) } ``` </details> <br/>