列表 List
最后更新于：2022-04-02 04:22:07
[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 // 值
}
```
## 实例
main.go
```
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())
}
```
';