两种并发安全链表的实现和对比

```type MutexList struct {
locker     *sync.Mutex
size       int64
}```

```type Node struct {
Value interface{}
Next  *Node
}

func NewNode(v interface{}) *Node {
n := &Node{Value: v}
n.Next = nil
return n
}```

```func (l *MutexList) Enq(v interface{}) bool {
if v == nil {
return false
}

l.locker.Lock()
node := NewNode(v)
l.tail.Next = node
l.tail = node
l.size++
l.locker.Unlock()
return true
}```

```func (l *MutexList) Insert(index int64, v interface{}) bool {
l.locker.Lock()
defer l.locker.Unlock()

if index > l.size || index < 0 || v == nil {
return false
}

for i := int64(0); i <= index-1; i++ {
// index - 1是最后一个节点时
if current.Next == nil {
break
}
current = current.Next
}

node := NewNode(v)
node.Next = current.Next
current.Next = node
l.size++

return true
}```

```func (l *MutexList) Length() int64 {
}```

```type List struct {
size int64
}

type MutexNode struct {
Locker *sync.Mutex
Value interface{}
Next *MutexNode
}

func NewMutexNode(v interface{}) *MutexNode {
n := &MutexNode{Value: v}
n.Locker = &sync.Mutex{}
n.Next = nil
return n
}

func NewList() *List {
l := &List{}

return l
}```

list和node的定义

```func (l *List) Enq(v interface{}) bool {
if v == nil {
return false
}

tail := l.tail
tail.Locker.Lock()
for tail.Next != nil {
next := tail.Next
next.Locker.Lock()
tail.Locker.Unlock()
tail = next
}

node := NewMutexNode(v)
tail.Next = node
l.tail = node
l.size++
tail.Locker.Unlock()

return true
}```

```func (l *List) Insert(index int64, v interface{}) bool {
if index < 0 || v == nil {
return false
}

current.Locker.Lock()
for i := int64(0); i <= index-1; i++ {
next := current.Next
if next == nil {
// 如果index前的某个节点为nil，那么说明链表可能被修改了，没有index个节点，insert失败
if index < index - 1 {
current.Locker.Unlock()
return false
}

break
}
next.Locker.Lock()
current.Locker.Unlock()
current = next
}

node := NewMutexNode(v)
node.Next = current.Next
current.Next = node
l.size++
current.Locker.Unlock()

return true
}```

remove的做法和insert类似，不再赘述。

```import (
"math/rand"
"sync"
"testing"
"time"
)

func init() {
rand.Seed(time.Now().Unix())
}

func BenchmarkEnq(b *testing.B) {
list := NewMutexList()
b.ResetTimer()

for i := 0; i < b.N; i++ {
if done := list.Enq(rand.Int()); !done {
b.Error("Enq failed")
}
}
}

func BenchmarkGoroutineEnq(b *testing.B) {
list := NewMutexList()
wg := &sync.WaitGroup{}
b.ResetTimer()

for i := 0; i < 6; i++ {
go func(n int) {
for i := 0; i < n; i++ {
if done := list.Enq(rand.Int()); !done {
b.Error("Enq by goroutines failed")
}
}
wg.Done()
}(b.N)
}
wg.Wait()
}

func BenchmarkInsert(b *testing.B) {
list := NewMutexList()
for i := 0; i < 5; i++ {
list.Enq(i)
}
b.ResetTimer()

for i := 0; i < b.N; i++ {
if done := list.Insert(rand.Int63n(list.Length()), rand.Int()); !done {
b.Error("Insert failed")
}
}
}

func BenchmarkGoroutineInsert(b *testing.B) {
list := NewMutexList()
for i := 0; i < 5; i++ {
list.Enq(i)
}
wg := &sync.WaitGroup{}
b.ResetTimer()

for i := 0; i < 6; i++ {
go func(n int) {
for i := 0; i < n; i++ {
if done := list.Insert(rand.Int63n(list.Length()), rand.Int()); !done {
b.Error("insert by goroutine failed")
}
}
wg.Done()
}(b.N)
}
wg.Wait()
}```

```import (
"math/rand"
"sync"
"testing"
)

func BenchmarkMutexNodeEnq(b *testing.B) {
list := NewList()
b.ResetTimer()

for i := 0; i < b.N; i++ {
if done := list.Enq(rand.Int()); !done {
b.Error("MutexNode Enq failed")
}
}
}

func BenchmarkGoroutineMutexNodeEnq(b *testing.B) {
list := NewList()
wg := &sync.WaitGroup{}
b.ResetTimer()

for i := 0; i < 6; i++ {
go func(n int) {
for i := 0; i < n; i++ {
if done := list.Enq(rand.Int()); !done {
b.Error("MutexNode Enq by goroutines failed")
}
}
wg.Done()
}(b.N)
}
wg.Wait()
}

func BenchmarkMutexNodeInsert(b *testing.B) {
list := NewList()
for i := 0; i < 5; i++ {
list.Enq(i)
}
b.ResetTimer()

for i := 0; i < b.N; i++ {
if done := list.Insert(rand.Int63n(list.Length()), rand.Int()); !done {
b.Error("MutexNode Insert failed")
}
}
}

func BenchmarkGoroutineMutexNodeInsert(b *testing.B) {
list := NewList()
for i := 0; i < 5; i++ {
list.Enq(i)
}
wg := &sync.WaitGroup{}
b.ResetTimer()

for i := 0; i < 6; i++ {
go func(n int) {
for i := 0; i < n; i++ {
if done := list.Insert(rand.Int63n(list.Length()), rand.Int()); !done {
b.Error("MutexNode Insert by goroutine failed")
}
}
wg.Done()
}(b.N)
}
wg.Wait()
}```

go test -bench=. -benchmem

原文作者：apocelipes
原文地址: https://www.cnblogs.com/apocelipes/p/9461405.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。