Go语言数据结构和算法-LinkedList(链表)

Prepend(item)       //  在链表头新增一个元素Append(item)        //  在链表尾追加一个元素InsertAt(i,item)    //  在索引i处插入一个元素RemoveAt(i)         //  删除再索引i处的一个元素Remove(item)        //  删除item元素IndexOf(item)       //  返回item的索引IsEmpty()           //  链表是否为空Size()              //  链表的大小Head()              //  链表的头节点Tail()              //  链表的尾节点String()            //  遍历链表复制代码

节点和链表数据结构

type Node struct {	item interface{}	next *Node}type LinkedList struct {	head *Node	size int  lock sync.RWMutex}复制代码

Prepend(item) 在链表头新增一个元素

func (list *LinkedList) Prepend(item interface{}) {  list.lock.Lock()	defer list.lock.Unlock()	node := &Node{item,nil}	if list.head == nil{		list.head = node	}else{		node.next = list.head		list.head = node	}	list.size += 1}复制代码

Append(item) 在链表尾追加一个元素

func (list *LinkedList) Append(item interface{}) {  list.lock.Lock()	defer list.lock.Unlock()	node := &Node{item, nil}	if list.head == nil {		list.head = node	} else {		cur := list.head		for cur.next != nil {			cur = cur.next		}		cur.next = node	}	list.size += 1}复制代码

InsertAt(i,item) 在索引i处插入一个元素

func (list *LinkedList) InsertAt(i int, item interface{}) error {	list.lock.Lock()	defer list.lock.Unlock()	if i > list.size || i < 0 {		return fmt.Errorf("index error")	}	node := &Node{item, nil}	if i == 0 {		node.next = list.head		list.head = node		list.size += 1		return nil	}	cur := list.head	for cur.next != nil && i != 1 {		i -= 1		cur = cur.next	}	node.next = cur.next	cur.next = node	list.size += 1	return nil}复制代码

RemoveAt(i) 删除再索引i处的一个元素

func (list *LinkedList) RemoveAt(i int) bool {	list.lock.Lock()	defer list.lock.Unlock()	if i < 0 || i >= list.size {		return false	}	if list.head == nil {		return false	}	if i == 0 {		list.head = list.head.next		list.size -= 1		return true	}	cur := list.head	for cur.next != nil && i != 1 {		i -= 1		cur = cur.next	}	cur.next = cur.next.next	list.size -= 1	return true}复制代码

Remove(item) 删除item元素

func (list *LinkedList) Remove(item interface{}) bool {	list.lock.Lock()	defer list.lock.Unlock()	if list.head == nil {		return false	}	if list.head.item == item {		list.head = list.head.next		list.size -= 1		return true	}	cur := list.head	for cur.next != nil {		if cur.next.item == item {			cur.next = cur.next.next			list.size -= 1			return true		}		cur = cur.next	}	return false}复制代码

IndexOf(item) 返回item的索引,如果不存在就返回-1

func (list *LinkedList) IndexOf(item interface{}) int {  list.lock.Lock()	defer list.lock.Unlock()	cur := list.head	index := -1	for cur != nil {		index += 1		if item == cur.item {			return index		}		cur = cur.next	}	return -1}复制代码

IsEmpty() 链表是否为空

func (list *LinkedList) IsEmpty() bool {  list.lock.Lock()	defer list.lock.Unlock()	return list.size == 0}复制代码

Size() 链表的大小

func (list *LinkedList) Size() int {  list.lock.Lock()	defer list.lock.Unlock()	return list.size}复制代码

Head() 链表头节点

func (list *LinkedList) Head() *Node {  list.lock.Lock()	defer list.lock.Unlock()	return list.head}复制代码

Tail() 链表尾节点

func (list *LinkedList) Tail() *Node {  list.lock.Lock()	defer list.lock.Unlock()	cur := list.head	for cur.next != nil {		cur = cur.next	}	return cur}复制代码

String() 遍历真个链表

func (list *LinkedList) String() {  list.lock.Lock()	defer list.lock.Unlock()	cur := list.head	for cur != nil {		fmt.Print(cur.item, "->")		cur = cur.next	}}复制代码