Golang List implementation example details

preface

In order to quickly review the basic syntax of Go, we intend to use the basic syntax and features of Go to implement 1 common data structure and sorting algorithm. By analyzing how to implement 1 basic data structure, you can quickly learn the syntax features of Go. The memory is deeper and the mastery faster. This is the best way for me to get started with a new language. This is also a good way to prepare yourself for writing with Go in the future, so you don't have to go through a few tutorials. The first article in this series starts with how to implement List.

demand

It is well known that the basic linked list has the following characteristics: the initialization of the list, the length of the list, the insertion, deletion, search and so on. As for testing, I wrote about it in the Go series of notes, and I won't repeat it.

implementation

Initialize the

As anyone with a language background knows, linked lists are made up of nodes that define an Node data structure in addition to an List data structure. First of all, the data structure of Node type should be able to store the basic type of data according to the normal design of List, which requires that the type of Value in Node cannot be fixed. At this point, you may reply: In Java, can't we pass the types of Int and String to List? You're going off the rails. The job is to implement the List data structure. So there are no restrictions of any kind on its Value range, and in Go the 'empty interface' fits this requirement perfectly. In addition, one Node in List requires two pointer fields, pointing to the addresses of the nodes before and after. In Go, this requirement can be implemented by *, which is simply understood to be able to store addresses. For example *Int is an address of type int. Look at the implementation:

type Node struct {
 Value interface{} 
 next, prev *Node 
}

The following is the definition of THE List structure. With the above analysis, the definition of the List structure is well implemented:

type List struct {
 root Node //  Head node 
 length int // list The length of the 
}

So how do you get an List object once you've built the basic data structure? Take your time and think about how it works in Java:

Person p = new Man();

As shown above, first get an instance of the Man class, then there is the address/reference of the object in p. From this analysis we have a rough idea of how to create an list object. The final result is to get the reference/address of an List with a length of 0. In addition, the case of empty List needs to be handled well:

//  return List A pointer to the 
func New() *List {
 l := &List{}//  To obtain List{} The address of the 
 l.length = 0// list The initial length is 0
 l.root.next = &l.root
 l.root.prev = &l.root
 return l
}

Nulls and lengths

The null and fetch length of List is also very basic and important, judging whether it is null and returning a Boolean data type. When is List empty? According to the previous definition, the next pointer field of the header node is null if it points to the address of the header node itself. In addition, null function is written, can not be all types of data to call this function, we need to specify the call data type, in this case, of course, is the type of List, to facilitate the operation, passed in an ADDRESS of List.

func (l *List) IsEmpty() bool {
 return l.root.next == &l.root
}

After the analysis, it is much easier to obtain the length of list:

func (l *List) Length() int {
 return l.length
}

Head and tail

When you define the List data structure, you define an root header node. So at this point, it is very convenient to implement header insertion and tail insertion. Considering that multiple /1 Node nodes can be inserted at the same time, the variable length parameter in Go is used to realize this feature. The inserted Node node is cycled. The pointer field of the new node and the pointer field of the root node are changed accordingly. The specific implementation method and instructions are explained in the code:

func (l *List) PushFront(elements ...interface{}) {
 for _, element := range elements {
 n := &Node{Value: element} //  annotation 1
 n.next = l.root.next //  The new node next is root The node's next
 n.prev = &l.root //  The new node prev The store is root The address of the 
 l.root.next.prev = n //  The original root The node's next the prev Is the new node 
 l.root.next = n //  The first interpolation  root  After that is always the new node 
 l.length++ // list  The length of the add 1
 }
}

Note 1: Structure initialization method Node{Value: element} & Is the way to get the address of a structure. You need a variable of address type to store the address of the structure, and you can see that it is declared as n. Here's how temporary variables are declared in Go. And the temporary variable does not need to indicate the data type. The tail interpolation method is simple, as shown in the following code:

func (l *List) PushBack(elements ...interface{}) {
 for _, element := range elements {
 n := &Node{Value: element}
 n.next = &l.root // since n is the last element, its next should be the head
 n.prev = l.root.prev // n's prev should be the tail
 l.root.prev.next = n // tail's next should be n
 l.root.prev = n // head's prev should be n
 l.length++
 }
}

To find the

The final effect of the lookup is to return the index of the specified value, or -1 if it does not exist. The search for the linked list is a traversal process, at this point need to consider the beginning and end of the traversal interval, can not be wrong. Because it's a circular list, terminating nodes are easy. The specific code is as follows:

func (l *List) Find(element interface{}) int {
 index := 0
 p := l.root.next
 for p != &l.root && p.Value != element {
 p = p.next
 index++
 }
 // p not root
 if p != &l.root {
 return index
 }

 return -1
}

delete

The deletion logic of the linked list is very clear. It is enough to disconnect one Node node from the front and rear nodes. Meanwhile, the front and rear nodes and the pointer field of Node node itself should be modified accordingly.

func (l *List) remove(n *Node) {
 n.prev.next = n.next
 n.next.prev = n.prev
 n.next = nil
 n.prev = nil
 l.length--
}

Delete and return the first data in List:

type List struct {
 root Node //  Head node 
 length int // list The length of the 
}

0

traverse

The following normalIndex function returns a normal logical Index, for example, to handle some out-of-bounds problems:

type List struct {
 root Node //  Head node 
 length int // list The length of the 
}

1

In order to get the data in the specified range, the following function specifies start and end according to the parameters passed in. The final return should be 1 slice or array, the specific type is unknown:

type List struct {
 root Node //  Head node 
 length int // list The length of the 
}

2

ok, the above is the implementation of List data structure in Go, through this section, you can learn a lot of grammar features of Go. Personally, I think learning programming grammar is the simplest and should be mastered in the shortest time.

conclusion