Golang双端列表

news/2024/7/9 23:16:23 标签: golang, linux, postgresql

代码实现

package zgo_algorithm

import "sync"

// DoubleList 双端列表，双端队列
type DoubleList struct {
	head *ListNode  // 指向链表头部
	tail *ListNode  // 指向链表尾部
	len  int        // 列表长度
	lock sync.Mutex // 为了进行并发安全pop弹出操作
}

// ListNode 列表节点
type ListNode struct {
	pre   *ListNode // 前驱节点
	next  *ListNode // 后驱节点
	value string    // 值
}

// GetValue 获取节点值
func (node *ListNode) GetValue() string {
	return node.value
}

// GetPre 获取节点前驱节点
func (node *ListNode) GetPre() *ListNode {
	return node.pre
}

// GetNext 获取节点后驱节点
func (node *ListNode) GetNext() *ListNode {
	return node.next
}

// HashNext 是否存在后驱节点
func (node *ListNode) HashNext() bool {
	return node.pre != nil
}

// HashPre 是否存在前驱节点
func (node *ListNode) HashPre() bool {
	return node.next != nil
}

// IsNil 是否为空节点
func (node *ListNode) IsNil() bool {
	return node == nil
}

// Len 返回列表长度
func (list *DoubleList) Len() int {
	return list.len
}

// AddNodeFromHead 从头部开始，添加节点到第N+1个元素之前，N=0表示添加到第一个元素之前，表示新节点成为新的头部，N=1表示添加到第二个元素之前，以此类推
func (list *DoubleList) AddNodeFromHead(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 如果索引超过或等于列表长度，一定找不到，直接panic
	if n != 0 && 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
}

// AddNodeFromTail 从尾部开始，添加节点到第N+1个元素之后，N=0表示添加到第一个元素之后，表示新节点成为新的尾部，N=1表示添加到第二个元素之后，以此类推
func (list *DoubleList) AddNodeFromTail(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 如果索引超过或等于列表长度，一定找不到，直接panic
	if n != 0 && 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
}

// First 返回列表链表头结点
func (list *DoubleList) First() *ListNode {
	return list.head
}

// Last 返回列表链表尾结点
func (list *DoubleList) Last() *ListNode {
	return list.tail
}

// IndexFromHead 从头部开始往后找，获取第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
}

// IndexFromTail 从尾部开始往前找，获取第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
}

// PopFromHead 从头部开始往后找，获取第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
}

// PopFromTail 从尾部开始往前找，获取第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
}

测试

package zgo_algorithm

import (
	"fmt"
	"testing"
)

func TestDoubleList(t *testing.T) {
	list := new(DoubleList)

	// 在列表头部插入新元素
	list.AddNodeFromHead(0, "I")
	list.AddNodeFromHead(0, "love")
	list.AddNodeFromHead(0, "you")

	// 在列表尾部插入新元素
	list.AddNodeFromTail(0, "may")
	list.AddNodeFromTail(0, "happy")

	list.AddNodeFromTail(list.Len()-1, "begin second")
	list.AddNodeFromHead(list.Len()-1, "end second")

	// 正常遍历，比较慢，因为内部会遍历拿到值返回
	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())
}

测试结果

=== RUN   TestDoubleList
you
begin second
love
I
may
end second
happy
----------
you
begin second
love
I
may
end second
happy
----------
you
begin second
love
I
may
end second
happy
----------
len 0
--- PASS: TestDoubleList (0.00s)
PASS

http://www.niftyadmin.cn/n/795876.html

相关文章

oppoJava面试！java取整和取余

oppoJava面试！java取整和取余

01 阿里面试题之MySQL 之前的阿里面试题都有做总结&#xff0c;具体面试题内容整理成了文档&#xff0c;本文是针对MySQL系列的&#xff0c;所以下面只展示了自己第一次面试阿里时被吊打问到的一些MySQL难题 请解释关系型数据库概念及主要特点&#xff1f;请说出关系型数据库…
阅读更多...
oppoJava面试！毕业两年无经验找工作

oppoJava面试！毕业两年无经验找工作

为了更好的梳理相关知识&#xff0c;咱们先看纯手绘知识体系图 1.1 Kafka知识体系大纲 由于我手绘这些知识体系大纲是用的xmind软件&#xff0c;无法上传&#xff0c;所以都以截图的形式展示&#xff0c;细节处不清楚&#xff08;毕竟图片形式有限&#xff09; 1.2 RabbitMQ知…
阅读更多...
Golang集合

Golang集合

代码实现 package zgo_algorithmimport ("sync" )// 集合结构体 type Set struct {m map[int]struct{} // 用字典来实现&#xff0c;因为字段键不能重复len int // 集合的大小sync.RWMutex // 锁&#xff0c;实现…
阅读更多...
插入、选择、冒泡、梳排序性能比较

插入、选择、冒泡、梳排序性能比较

虽然标题中的排序算法往往被认为是低效率的算法.但并不意味着这些算法完全没有可取之处。本次不再探讨这些算法的基本原理&#xff0c;仅仅比较算法的性能&#xff0c;并贴出实现这些算法的源代码&#xff1a; 还是先肝代码吧&#xff08;手动狗头&#xff09;&#xff1a; # i…
阅读更多...
Android Fragment系列学习笔记之三

Android Fragment系列学习笔记之三

一、Fragment和Activity之间的数据交互 1.1、在Fragment中访问Activity 在Fragment中访问Activity&#xff0c;可调用Fragment的getActivity()方法获取Activity对象。getActivity()得到的是它的父窗口中的对象&#xff0c;再通过findViewById()方法即可找到父窗体中的控件&…
阅读更多...
#6392. 「THUPC2018」密码学第三次小作业 / Rsa （exgcd求逆元+快速幂+快速乘）

#6392. 「THUPC2018」密码学第三次小作业 / Rsa （exgcd求逆元+快速幂+快速乘）

题目链接&#xff1a;https://loj.ac/problem/6392 题目大意&#xff1a;给定五个正整数c1,c2,e1,e2,N&#xff0c;其中e1与e2互质&#xff0c;且满足 c1 m^e1 mod N c2 m^e2 mod N 求出正整数m 解题思路&#xff1a;因为e1与e2互质&#xff0c;所以可以找到两个整数x,y,满足…
阅读更多...
Golang二叉树

Golang二叉树

代码实现 package zgo_algorithmimport ("fmt""sync" )// 二叉树 type TreeNode struct {Data interface{} // 节点用来存放数据Left *TreeNode // 左子树Right *TreeNode // 右字树 }// 先序遍历&#xff1a;先访问根节点&#xff0c;再访问左子树&…
阅读更多...
Redis缓存：Java面试相关文章及Github学习资料

Redis缓存：Java面试相关文章及Github学习资料

什么是 RPC?RPC原理是什么? 什么是 RPC&#xff1f; RPC&#xff08;Remote Procedure Call&#xff09;—远程过程调用&#xff0c;它是一种通过网络从远程计算机程序上请求服务&#xff0c;而不需要了解底层网络技术的协议。比如两个不同的服务 A、B 部署在两台不同的机器…
阅读更多...
最新文章

Copyright @ 2022~2023