Go实现双向链表的示例代码

2020-01-28 14:04:59刘景俊

2、 存入以后,查询数据是否符合预期


# 查看全部元素
LRANGE commodity:queue 0 -1

# 查看队列的长度
LLEN commodity:queue

3、 抢购开始,获取商品码,抢到商品码的用户则可以购买(由于 Redis 是单线程的,同一个商品码只能被取一次


# 出队
LPOP commodity:queue

这里了解到 Redis 列表是怎么使用的,下面就用 Go 语言实现一个双向链表来实现这些功能。

3、Go双向链表

3.1 说明

这里只是用 Go 语言实现一个双向链表,实现:查询链表的长度、链表右端插入数据、左端取数据、取指定区间的节点等功能( 类似于 Redis 列表的中的 RPUSH、LRANGE、LPOP、LLEN功能 )。

3.2 实现

节点定义

双向链表有两个指针,分别指向前一个节点和后一个节点

链表表头 prev 的指针为空,链表表尾 next 的指针为空


// 链表的一个节点
type ListNode struct {
  prev *ListNode // 前一个节点
  next *ListNode // 后一个节点
  value string  // 数据
}

// 创建一个节点
func NewListNode(value string) (listNode *ListNode) {
  listNode = &ListNode{
    value: value,
  }

  return
}

// 当前节点的前一个节点
func (n *ListNode) Prev() (prev *ListNode) {
  prev = n.prev

  return
}

// 当前节点的前一个节点
func (n *ListNode) Next() (next *ListNode) {
  next = n.next

  return
}

// 获取节点的值
func (n *ListNode) GetValue() (value string) {
  if n == nil {

    return
  }
  value = n.value

  return
}

定义一个链表

链表为了方便操作,定义一个结构体,可以直接从表头、表尾进行访问,定义了一个属性 len ,直接可以返回链表的长度,直接查询链表的长度就不用遍历时间复杂度从 O(n) 到 O(1)。


// 链表
type List struct {
  head *ListNode // 表头节点
  tail *ListNode // 表尾节点
  len int    // 链表的长度
}


// 创建一个空链表
func NewList() (list *List) {
  list = &List{
  }
  return
}

// 返回链表头节点
func (l *List) Head() (head *ListNode) {
  head = l.head

  return
}

// 返回链表尾节点
func (l *List) Tail() (tail *ListNode) {
  tail = l.tail

  return
}

// 返回链表长度
func (l *List) Len() (len int) {
  len = l.len

  return
}

在链表的右边插入一个元素


// 在链表的右边插入一个元素
func (l *List) RPush(value string) {

  node := NewListNode(value)

  // 链表未空的时候
  if l.Len() == 0 {
    l.head = node
    l.tail = node
  } else {
    tail := l.tail
    tail.next = node
    node.prev = tail

    l.tail = node
  }

  l.len = l.len + 1

  return
}