列表
对于列表的表示我们有如下两种实现形式：
- 顺序表示：指的是使用一组地址连续的存储单元依次存储线性表的数据，成为此线性表为顺序存储结构， 它以物理位置相邻来表示线性表中的数据间的逻辑位置，可随机存取表中的任何一个数据元素，顺序表示的也叫做顺序表，也就是用数组来实现的列表。
- 链式表示：指的是用一组任意的非连续的存储单元存储线性表中的数据元素，成为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储本身信息之外，还需要存储一个指向直接后继节点的信息，也就是用链表来实现的列表。
双端列表
定义数据类型
// 定义双端链表的数据类型
type ListNode struct {
prev *ListNode
next *ListNode
value string
}
type DoubleList struct {
head *ListNode // 头节点
tail *ListNode // 尾节点
len int // 长度
lock sync.Mutex // 为了并发安全，引入锁
}
常见操作
/*
一些常见的基本操作
*/
// GetValue 获取节点值
func (node *ListNode) GetValue() string {
return node.value
}
// GetPre 获取前一个节点
func (node *ListNode) GetPre() *ListNode {
return node.prev
}
// GetNext 获取后一个节点
func (node *ListNode) GetNext() *ListNode {
return node.next
}
// HasNext 是否有后一个节点
func (node *ListNode) HasNext() bool {
return node.next != nil
}
// HasPre 是否有前一个节点
func (node *ListNode) HasPre() bool {
return node.prev != nil
}
// IsNil 是否为空
func (node *ListNode) IsNil() bool {
return node == nil
}
// Len 获取长度
func (list *DoubleList) Len() int {
return list.len
}
// First 头部节点
func (list *DoubleList) First() *ListNode {
return list.head
}
// Last 尾部节点
func (list *DoubleList) Last() *ListNode {
return list.tail
}
插入操作
实现从头部开始，在某个节点之前插入一个节点。
// AddNodeFormHead 从头部开始，在某个节点之前插入一个节点
// 0 表示第一个元素之前，1 表示第二个元素之前...
func (list *DoubleList) AddNodeFormHead(value string, pre int) {
list.lock.Lock()
defer list.lock.Unlock()
if pre <= 0 || pre > list.len {
panic("pre is out of range")
}
// 找到头部节点
node := list.head
// 向后进行遍历，找到pre-1个节点
for i := 0; i <= pre; i++ {
node = node.next
}
newNode := new(ListNode)
node.value = value
// 如果定位到的节点为空，则直接插入到头部
if node.IsNil() {
list.head = newNode
list.tail = newNode
} else {
// 找到前一个节点
pre := node.prev
// 如果定位到的节点为头部，则直接插入到头部
if pre.IsNil() {
newNode.next = node
node.prev = newNode
list.head = newNode
} else {
// 将新节点插入到定位节点之前
// 新节点的后一个节点为定位节点
pre.next = newNode
newNode.prev = pre
// 新节点的前一个节点为定位节点的前一个节点
node.next.prev = newNode
newNode.next = node.next
}
}
list.len++
}
实现从尾部开始，在某个节点之后插入一个节点。
// AddNodeFormTail 从尾部开始，在某个节点之后插入一个节点
// 0 表示第一个元素之后，1 表示第二个元素之后...
func (list *DoubleList) AddNodeFormTail(value string, next int) {
list.lock.Lock()
defer list.lock.Unlock()
// 找到尾部节点
node := list.tail
if next <= 0 || next > list.len {
panic("next is out of range")
}
// 向前进行遍历，找到next-1个节点
for i := 0; i <= next; i++ {
node = node.prev
}
newNode := new(ListNode)
newNode.value = value
// 如果定位到的节点为空，则直接插入到尾部
if node.IsNil() {
list.head = newNode
list.tail = newNode
} else {
// 找到定位节点的后一个节点
next := node.next
// 如果定位到的节点为尾部，则直接插入到尾部,需要更新尾部节点
if next.IsNil() {
// 新节点的前一个节点为尾部节点
// 新节点的后一个节点为空
newNode.prev = node
node.next = newNode
list.tail = newNode
} else {
// 将新节点插入到定位节点之后
// 新节点的前一个节点为定位节点
newNode.prev = node
node.next = newNode
// 新节点的后一个节点为定位节点的后一个节点
newNode.next = next
next.prev = newNode
}
}
list.len++
}
获取节点
实现从头部开始，获取第 n + 1 个位置上的节点。
// IndexFormHead 从头部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormHead(n int) *ListNode {
if n > list.len || n < 0 {
panic("index is out of range")
}
// 找到头部节点
node := list.head
// 向后进行遍历，找到第 n 个节点
for i := 0; i < n; i++ {
node = node.next
}
return node
}
实现从尾部开始，获取第 n + 1 个位置上的节点。
// IndexFormTail 从尾部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormTail(n int) *ListNode {
if n > list.len || n < 0 {
panic("index is out of range")
}
// 找到尾部节点
node := list.tail
// 向前进行遍历，找到第 n 个节点
for i := 0; i < n; i++ {
node = node.prev
}
return node
}
删除节点
实现从头部开始，删除第 n + 1 个位置上的节点。
// RemoveNodeFormHead 从头部开始，删除第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) RemoveNodeFormHead(n int) *ListNode {
list.lock.Lock()
defer list.lock.Unlock()
if n >= list.len || n < 0 {
return nil
panic("index is out of range")
}
// 找到头部节点
node := list.head
// 向后进行遍历，找到第 n 个节点
for i := 0; i < n; i++ {
node = node.next
}
// 移除节点
pre := node.prev
next := node.next
// 如果前继和后继都为空，则直接删除头部节点
if pre.IsNil() && next.IsNil() {
list.head = nil
list.tail = nil
} else if pre.IsNil() {
// 表示移除的是头部节点，让下一个节点变成头部节点
list.head = next
next.prev = nil
} else if next.IsNil() {
// 表示移除的是尾部节点，让前一个节点变成尾部节点
list.tail = pre
pre.next = nil
} else {
// 前继和后继都不为空，则将后继节点的前继节点变成前继节点
pre.next = next
next.prev = pre
}
list.len--
return node
}
实现从尾部开始，删除第 n + 1 个位置上的节点。
// PopTailFromHead 从尾部开始往前找，获取第 n 个位置上的节点，并将移除返回
func (list *DoubleList) PopTailFromHead(n int) *ListNode {
list.lock.Lock()
defer list.lock.Unlock()
if n >= list.len || n < 0 {
return nil
panic("index is out of range")
}
// 获取尾部元素
node := list.tail
// 向前进行遍历，找到第 n 个节点
for i := 0; i < n; i++ {
node = node.prev
}
// 移除的节点的前驱和后继
pre := node.prev
next := node.next
// 如果前驱和后继都为空，则直接删除尾部节点
if pre.IsNil() && next.IsNil() {
list.head = nil
list.tail = nil
} else if pre.IsNil() {
// 直接将后继节点变成尾部节点
list.head = next
next.prev = nil
} else if next.IsNil() {
list.tail = pre
pre.next = nil
} else if next.IsNil() {
pre.next = next
pre.next = nil
} else {
pre.next = next
next.prev = pre
}
list.len--
return node
}
字典
字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射。并且键不能重复。
func DicExample() {
m := make(map[string]int64, 4)
m["dog"] = 1
m["hen"] = 2
m["cat"] = 3
fmt.Println(m)
which := "hen"
v, ok := m[which]
if ok {
// find
fmt.Println("finn", which, "value:", v)
} else {
// not find
fmt.Println("not find", which)
}
}
不可重复集合
在 Golang 中，实现集合是一件很有意思的事情。
我们通常借助空结构体为值来实现 Set， 因为我们知道字典的键是不重复的，所以只要我们不考虑字典的值，就可以来实现集合了。
注意：空结构体并不占用内存在大小。
定义数据类型
// 思想：不考虑字典的值，我们可以实现一个set
type Set struct {
m map[int]struct{} // 为什么我们要使用空结构体，因为空结构体不占用内存
len int
sync.RWMutex
}
新建一个Set操作
// NewSet 新建一个set
func NewSet(cap int64) *Set {
temp := make(map[int]struct{}, cap)
return &Set{
m: temp,
}
}
增加一个元素
// Add 增加一个元素
func (s *Set) Add(item int) {
s.Lock()
defer s.Unlock()
s.m[item] = struct{}{}
s.len = len(s.m)
}
删除一个元素
//Remove 移除一个元素
func (s *Set) Remove(item int) {
s.Lock()
defer s.Unlock()
if s.len == 0 {
return
}
// 从字典中删除
delete(s.m, item)
// 计算长度
s.len = len(s.m)
}
判断元素是否存在
// Has 判断一个元素是否在set中
func (s *Set) Has(item int) bool {
s.RLock()
defer s.RUnlock()
_, ok := s.m[item]
return ok
}
获取长度
// Len 获取set的长度
func (s *Set) Len() int {
return s.len
}
判断是否为空
//IsEmpty 判断set是否为空
func (s *Set) IsEmpty() bool {
if s.len == 0 {
return true
}
return false
}
清空
// Clear 清空set
func (s *Set) Clear() {
s.Lock()
defer s.Unlock()
s.m = make(map[int]struct{})
s.len = 0
}
转化为Slice
// List 将 Set 转化为 Slice
func (s *Set) List() []int {
s.RLock()
defer s.RUnlock()
list := make([]int, 0, s.len)
for item := range s.m {
list = append(list, item)
}
return list
}
总结
本次我们介绍使用Go语言实现数据结构中的列表和字典，并且介绍了一些常见的操作。数据结构这一系列我们没有涉及到具体的细节的讲解，适合有一定数据结构基础的童鞋，本系列代码已经上传至Github，欢迎大家 Star。