Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to use the Go container package". The content in the article is simple and clear, easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use the Go container package".

1. Brief introduction

Container-Container data type: this package implements three complex data structures: heap, linked list, and ring

Implementation of linked list in List:Go, where List: bi-directional linked list, Element: elements in linked list

Ring: implements a circular linked list, which is commonly known as a ring

Implementation of heap in Heap:Go

2.list

Simple and practical:

Func main () {/ / initialize bi-directional linked list l: = list.New () / / chain header insert l.PushFront (1) / chain footer insert l.PushBack (2) l.PushFront (3) / / traverse for head: = l.Front (); head! = nil;head = head.Next () {fmt.Println (head.Value)}}

List of methods:

Type Element func (e * Element) Next () * Element / / returns the next element of the element, or nil func (e * Element) Prev () * Element / / returns the previous element of the element if there is no next element If there is no previous element, return niltype List func New () * List / / return an initialized list func (l * List) Back () * Element / / get the last one of list l Element func (l * List) Front () * Element / / get the first element of list l func (l * List) Init () * List / / list l initialize or clear list l func (l * List) InsertAfter (v interface {}) Mark * Element) * Element / / insert an element with a value of v after the element mark in list l If mark is not an element in list, list does not change func (l * List) InsertBefore (v interface {}, mark * Element) * Element / / inserts an element with a value of v before element mark in list l, and returns it, if mark is not an element in list Then list does not change func (l * List) Len () int / / get the length of list l func (l * List) MoveAfter (e, mark * Element) / / move element e after element mark, if element e or mark does not belong to list l, or e==mark Then list l does not change func (l * List) MoveBefore (e, mark * Element) / / moves element e before element mark, if element e or mark does not belong to list l, or e==mark, then list l does not change func (l * List) MoveToBack (e * Element) / / moves element e to the end of list l, if e does not belong to list l Then list does not change func (l * List) MoveToFront (e * Element) / / moves element e to the beginning of list l. If e does not belong to list l, list does not change func (l * List) PushBack (v interface {}) * Element / / inserts an element with a value of v at the end of list l. And return the element func (l * List) PushBackList (other * List) / / insert another list at the end of list l, where l and other can be equal to func (l * List) PushFront (v interface {}) * Element / / insert an element with a value of v at the beginning of list l And return the element func (l * List) PushFrontList (other * List) / / insert another list at the beginning of list l, where l and other can be equal to func (l * List) Remove (e * Element) interface {} / / if element e belongs to list l, delete it from list And returns the value 2.1 data structure of element e

Node definition:

Type Element struct {/ / successor pointer, forward pointer next, prev * Element / / linked list pointer, which linked list list * List / / node value Value interface {}}

Two-way linked list definition:

Type List struct {/ / root element root Element / / sentinel list element, only & root, root.prev, and root.next are used / / actual number of nodes len int / / current list length excluding (this) sentinel element}

Initialize:

/ / return list pointer func New () * List {return new (List) .Init ()} func (l * List) Init () * List {l.root.next = & l.root l.root.prev = & l.root l.len = 0 return l} via factory method

Here you can see that the root node, as a root node, does not bear the data, nor is it the actual linked list node. The number of nodes len does not include it. When initializing, the root node will become a ring with only one node (both pointers before and after pointing to themselves).

2.2 insert element

Head insertion:

Func (l * List) Front () * Element {if l.len = = 0 {return nil} return l.root.next} func (l * List) PushFront (v interface {}) * Element {l.lazyInit () return l.insertValue (v, & l.root)}

Tail insertion:

Func (l * List) Back () * Element {if l.len = = 0 {return nil} return l.root.prev} func (l * List) PushBack (v interface {}) * Element {l.lazyInit () return l.insertValue (v, l.root.prev)}

Add an element after the specified element:

Func (l * List) insert (e, at * Element) * Element {e.prev = at e.next = at.next e.prev.next = e e.next.prev = e e.list = l .lenient + return e}

Here is a logic for delaying initialization: lazyInit, deferring initialization only when it is actually needed

Func (l * List) lazyInit () {if l.root.next = = nil {l.Init ()}}

Remove elements:

/ / remove removes an element e from the two-way linked list, decrements the length of the linked list, and returns the element e func (l * List) remove (e * Element) * Element {e.prev.next = e.next e.next.prev = e.prev e.next = nil / / prevent memory leaks e.prev = nil / / prevent memory leaks e.list = nil l.len-- return e} 3.ring

Ring provided in Go is a two-way circular linked list, which is different from list in that it has no header and footer. Ring header and footer are connected to form a ring.

Use demo:

Func main () {/ / initializes the ring with three elements, and returns the header node r: = ring.New (3) / / to fill the ring with the value for I: = 1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.