golang实现单链表

1.链表

1.1常见的链表

1.1.1单向链表

单向链表每个数据节点包含数据和后继节点的指针，最后一个节点的后继节点指针为NULL

1.1.2单向循环链表

单向循环链表和单向链表相似，每个数据节点包含数据和后继节点的指针，区别在于最后一个节点的后继节点指针为链表的头部节点，形成一个环。

1.1.2双向链表

双向链表的每个数据节点包含三个元素：数据、前驱节点的指针、后继节点的指针。头部节点的前驱指针为NULL, 尾部节点的后继指针为NULL

2.双向链表

2.1 双向链表节点示意图

2.2 双向链表实现

2.2.1 数据结构

var (
	ERROR_OUT_OF_RANGE = errors.New("index out of range!")
)

type linkedNode struct {
	data interface{}
	prev *linkedNode
	next *linkedNode
}

type LinkedList struct {
	size  int
	head  *linkedNode
	tail  *linkedNode
	mutex *sync.Mutex
}

func NewLinkedList() *LinkedList {
	return &LinkedList{
		size:  0,
		head:  nil,
		tail:  nil,
		mutex: &sync.Mutex{},
	}
}

2.2.2 尾部追加数据

func (l *LinkedList) Append(data interface{}) {

	l.mutex.Lock()
	defer l.mutex.Unlock()
	node := &linkedNode{
		data: data,
	}
	if l.tail == nil {
		l.head = node
		l.tail = node
	} else {
		l.tail.next = node
		node.prev = l.tail
		l.tail = node
	}
	l.size += 1
}

2.2.3 头部追加数据

//从头部添加节点
func (l *LinkedList) AddHead(data interface{}) {
	l.mutex.Lock()
	defer l.mutex.Unlock()
	node := &linkedNode{
		data: data,
	}
	if l.head == nil {
		l.head = node
		l.tail = node
	} else {
		l.head.prev = node
		node.next = l.head
		l.head = node
	}
    l.size += 1
}

2.2.4 index查找节点数据

func (l *LinkedList) GetNode(index int) *linkedNode {
	l.mutex.Lock()
	defer l.mutex.Unlock()
	if l.size == 0 || index >= l.size {
		return nil
	}

	if index == 0 {
		return l.head
	}

	node := l.head
	for i := 0; i < index; i++ {
		node = node.next
	}
	return node
}

2.2.5 从任意位置插入

//从任意位置插入
func (l *LinkedList) Insert(data interface{}, index int) {
	l.mutex.Lock()
	defer l.mutex.Unlock()
	node := &linkedNode{
		data: data,
	}
	if l.size == 0 || index >= l.size {
		l.Append(data)
	} else {
		oldNode := l.GetNode(index)

		node.prev = oldNode.prev
		node.next = oldNode

		oldNode.prev.next = node
		oldNode.prev = node

		l.size++
	}
}

2.2.6 从头部出队列

//从头部出队列
func (l *LinkedList) LPop() interface{} {
	if l.size == 0 {
		return nil
	}

	l.mutex.Lock()
	defer l.mutex.Unlock()

	data := l.head.data
	l.head = l.head.next
	if l.head != nil {
		l.head.prev = nil
	} else {
		l.tail = nil
	}
	l.size -= 1
	return data
}

2.2.7 从尾部出队列

//从尾部出队
func (l *LinkedList) RPop() interface{} {
	if l.size == 0 {
		return nil
	}

	l.mutex.Lock()
	defer l.mutex.Unlock()

	data := l.tail.data
	l.tail = l.tail.prev
	if l.tail != nil {
		l.tail.next = nil
	} else {
		l.head = nil
	}

	l.size--
	return data
}

2.2.8 删除指定位置元素

//删除指定位置元素
func (l *LinkedList) RemoveByIndex(index int) error {

	if index >= l.size || index < 0 {
		return ERROR_OUT_OF_RANGE
	}

	l.mutex.Lock()
	defer l.mutex.Unlock()

	if index == 0 {
		l.head = l.head.next
		if l.head != nil {
			l.head.prev = nil
		} else {
			//如果删除后head为nil，则说明链表只有一个元素,将tail设为nil
			l.tail = nil
		}
		l.size--
		return nil
	}

	if index == l.size-1 {
		l.tail = l.tail.prev
		if l.tail != nil {
			l.tail.next = nil
		}
		l.size--
		return nil
	}

	curr := l.head
	for i := 0; i < index; i++ {
		curr = curr.next
	}
	curr.prev.next = curr.next
	curr.next.prev = curr.prev
	l.size--
	return nil
}

2.2.9 删除元素

//删除元素
func (l *LinkedList) Remove(data interface{}) int {
	if l.size == 0 || !l.Contain(data) {
		return -1
	}

	l.mutex.Lock()
	defer l.mutex.Unlock()

	if l.head.data == data {
		l.head = l.head.next
		if l.head != nil {
			l.head.prev = nil
		} else {
			//如果删除后head为nil，则说明链表只有一个元素,将tail设为nil
			l.tail = nil
		}
		l.size--
		return 0
	}

	if l.tail.data == data {
		l.tail = l.tail.prev
		if l.tail != nil {
			l.tail.next = nil
		}
		l.size--
		return l.size
	}

	curr := l.head
	index := 0
	for curr != nil {
		if curr.data == data {
			curr.prev.next = curr.next
			curr.next.prev = curr.prev
			l.size--
			break
		}
		curr = curr.next
		index++
	}
	return index
}

2.2.10 检查是否包含数据

func (l *LinkedList) Contain(data interface{}) bool {
	if l.size == 0 {
		return false
	}

	curr := l.head
	for curr != nil {
		if curr.data == data {
			return true
		}
		curr = curr.next
	}
	return false
}

2.2.11 获取链表长度

func (l *LinkedList) GetSize() int {
	l.mutex.Lock()
	defer l.mutex.Unlock()
	return l.size
}

2.2.12 打印所有节点数据

//打印所有元素
func (l *LinkedList) PrintAll() {
	if l.head == nil {
		return
	}
	i := 1
	curr := l.head
	for curr != nil {
		fmt.Printf("%d => %+v\n", i, curr.data)
		i++
		curr = curr.next
	}
}

3.测试代码

3.1 init 测试数据方法

//init 测试数据
func initLinkedListData() *LinkedList {
	l := NewLinkedList()
	data := "A"
	l.Append(data)

	data = "B"
	l.Append(data)

	data = "C"
	l.Append(data)
	return l
}

3.2 Remove

func TestList_Remove(t *testing.T) {
	l := initLinkedListData()
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("---------remove------")
	i := l.Remove("B")
	l.PrintAll()
	fmt.Println("remove index = ", i, " size = ", l.GetSize())
}

//结果 
=== RUN   TestList_Remove
1 => A
2 => B
3 => C
size =  3
---------remove------
1 => A
2 => C
remove index =  1  size =  2
--- PASS: TestList_Remove (0.00s)
PASS

3.3 RemoveAtIndex

func TestList_RemoveAtIndex(t *testing.T) {
	assert := require.New(t)
	l := initLinkedListData()
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("---------remove------")
	err := l.RemoveByIndex(2)
	assert.NoError(err)

	l.PrintAll()
	fmt.Println("size = ", l.GetSize())
}

=== RUN   TestList_RemoveAtIndex
1 => A
2 => B
3 => C
size =  3
---------remove------
1 => A
2 => B
size =  2
--- PASS: TestList_RemoveAtIndex (0.00s)
PASS

3.4 Lpop

func TestList_Lpop(t *testing.T) {
	l := initLinkedListData()
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("----lpop--")
	r1 := l.LPop()
	fmt.Println("r1 = ", r1)
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("----lpop--")
	r2 := l.LPop()
	fmt.Println("r2 = ", r2)
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("----lpop--")
	r3 := l.LPop()
	fmt.Println("r3 = ", r3)
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

}

=== RUN   TestList_Lpop
1 => A
2 => B
3 => C
size =  3
----lpop--
r1 =  A
1 => B
2 => C
size =  2
----lpop--
r2 =  B
1 => C
size =  1
----lpop--
r3 =  C
size =  0
--- PASS: TestList_Lpop (0.00s)
PASS

3.4 Rpop

func TestList_Rpop(t *testing.T) {
	l := initLinkedListData()
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("----lpop--")
	r1 := l.RPop()
	fmt.Println("r1 = ", r1)
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())
}

=== RUN   TestList_Rpop
1 => A
2 => B
3 => C
size =  3
----lpop--
r1 =  C
1 => A
2 => B
size =  2
--- PASS: TestList_Rpop (0.00s)
PASS

3.5 并发操作

func TestGr(t *testing.T) {
	l := initLinkedListData()
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())

	fmt.Println("-----start go---")
	wg := &sync.WaitGroup{}
	for i := 0; i < 100; i++ {
		wg.Add(1)
		go func(num int, wg *sync.WaitGroup) {
			defer wg.Done()
			l.LPop()
			l.Append(fmt.Sprintf("n-%d", num))
		}(i, wg)
	}
	wg.Wait()

	fmt.Println("-----end res---")
	l.PrintAll()
	fmt.Println("size = ", l.GetSize())
}

=== RUN   TestGr
1 => A
2 => B
3 => C
size =  3
-----start go---
-----end res---
1 => n-79
2 => n-17
3 => n-85
size =  3
--- PASS: TestGr (0.00s)

4.结束

学习交流，如果有不当之处，欢迎留言指正。感谢！

1.链表

1.1常见的链表

1.1.1单向链表

1.1.2单向循环链表

1.1.2双向链表

2.双向链表

2.1 双向链表节点示意图

2.2 双向链表实现

2.2.1 数据结构

2.2.2 尾部追加数据

2.2.3 头部追加数据

2.2.4 index查找节点数据

2.2.5 从任意位置插入

2.2.6 从头部出队列

2.2.7 从尾部出队列

2.2.8 删除指定位置元素

2.2.9 删除元素

2.2.10 检查是否包含数据

2.2.11 获取链表长度

2.2.12 打印所有节点数据

3.测试代码

3.1 init 测试数据方法

3.2 Remove

3.3 RemoveAtIndex

3.4 Lpop

3.4 Rpop

3.5 并发操作

4.结束

知秋君

相关推荐