Go Basis: Introduction and use of list

introduce

The Go built-in container List is a bidirectional linked list (actually a ring). In the package list.

Structure definition

The core structure of a list consists of two lists and elements.

List

The structure of List is as follows:

type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}
Copy the code

The structure of the List contains two parts:

• root: the type ofElementThe structure of.
• len: Used for recordingListLength (excluding sentinel nodes).

The first node of the List is the sentinel node and does not store any information. The head of the List starts at the next sentinel node.

Element

The structure of elements in the List is as follows:

type Element struct {
	list *List
	Value interface{}
   	   next, prev *Element
}
Copy the code

As can be seen from the structure of the node, a node in the list contains four elements:

• list: point toListPointer to the LIST to which the current node belongs
• Value: Used to store the value of an element.
• next.prev: point toElementPointer to locate the next node and the previous node.

To simplify the implementation, the internal implementation of the List is a ring, such that L.root is both the next element of the last List element (l.back ()) and the previous element of the first List element (l.front ()).

Methods in

The methods are divided into six categories:

• Initialization method
• Basic method
• Insert elements
• Remove elements
• Mobile elements
• Merge list

Initialize the

There are two methods of initialization: Init() and lazyInit().

The Init() method can be used to initialize a linked list, or to clear it.

The lazyInit() method lazily initializes a list with a zero value. From the implementation, we can see that the list is initialized only if the next node of the sentinel is empty.

func (l *List) Init(a) *List {
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

func (l *List) lazyInit(a) {
	if l.root.next == nil {
		l.Init()
	}
}
Copy the code

Basic method

• Next()Returns theThe current nodeNext node of or nil. As you can see from the implementation, whenlistIs empty orThe next node is the sentinel nodeWhen to return tonil.
• Prev()Returns theThe current nodeOr nil, similar to above.
• New(): Returns an initialized list.
• Len(): Indicates the number of elements in the linked list. The time complexity is O(1).
• Front(): returns the first element of the list. Returns nil when the list is empty.
• Back(): returns the last element of the list. Returns nil when the list is empty.

func (e *Element) Next(a) *Element {
	ifp := e.next; e.list ! =nil&& p ! = &e.list.root {return p
	}
	return nil
}

func (e *Element) Prev(a) *Element {
	ifp := e.prev; e.list ! =nil&& p ! = &e.list.root {return p
	}
	return nil
}

func New(a) *List { return new(List).Init() }

func (l *List) Len(a) int { return l.len }

func (l *List) Front(a) *Element {
	if l.len= =0 {
		return nil
	}
	return l.root.next
}

func (l *List) Back(a) *Element {
	if l.len= =0 {
		return nil
	}
	return l.root.prev
}
Copy the code

Insert elements

• insert():Underived function. The elementatInsert an element after the position of, add one to the list length, and return the inserted element.
• insertValue():Underived function. willValuePackaged inElementtheninsert().
• InsertBefore(): callinsertValue()The elementmarkBefore inserting. Required elementsmarkThe linked list object that belongs to the call and is notnil.
• InsertAfter()And:InsertBefore()Similarly, in the elementmarkAfter inserted.
• PushFront(): callinsertValue()Method is inserted in the header of the table. Returns the inserted element.
• PushBack(): callinsertValue()Method is inserted at the end of the table. Returns the inserted 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
	l.len++
	return e
}

func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	ifmark.list ! = l {return nil
	}
	return l.insertValue(v, mark.prev)
}

func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	ifmark.list ! = l {return nil
	}
	return l.insertValue(v, mark)
}

func (l *List) PushFront(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

func (l *List) PushBack(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}
Copy the code

Remove elements

• remove():Underived function. Removes elements from the linked listeIf the list length is reduced by one, the deleted element is returned.
• Remove(): when elementeWhen an element belonging to the invoked list is calledremove()Function, returnse.Value.

func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil	 // Avoid memory leaks
	e.prev = nil	 // Avoid memory leaks
	e.list = nil
	l.len--
	return e
}

func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}
Copy the code

Mobile elements

• move():Underived function. The elementeTo the elementatAfter, returns the elemente.
• MoveToFront(): the elementeMove to top of table. Required elementseThe element belonging to the invoked linked list.
• MoveToBack(): the elementeMove to end of table. Required elementseThe element belonging to the invoked linked list.
• MoveBefore(): the elementeTo the elementmarkIn front of. Required elementseAn element that belongs to and is not an element in the invoked listmark.
• MoveAfter()And:MoveBefore()Similarly, move behind it.

func (l *List) move(e, at *Element) *Element {
	if e == at {
		return e
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e

	return e
}

func (l *List) MoveToFront(e *Element) {
	ife.list ! = l || l.root.next == e {return
	}
	l.move(e, &l.root)
}

func (l *List) MoveToBack(e *Element) {
	ife.list ! = l || l.root.prev == e {return
	}
	l.move(e, l.root.prev)
}

func (l *List) MoveBefore(e, mark *Element) {
	ife.list ! = l || e == mark || mark.list ! = l {return
	}
	l.move(e, mark.prev)
}

func (l *List) MoveAfter(e, mark *Element) {
	ife.list ! = l || e == mark || mark.list ! = l {return
	}
	l.move(e, mark)
}
Copy the code

Merge list

• PushBackList(): Put another linked listShallow copyTo the end of the current list. Neither list is required to benil.
• PushFronList(): Put another linked listShallow copyTo the beginning of the current list. Neither list is required to benil.

func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i- 1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}

func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i- 1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}
Copy the code

use

Here are three ways to explain the use of list:

• Basic operation
• Simulation of the stack
• Simulation of the queue

Basic operation

The following shows the basic use of linked lists:

l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)

// Iterate over the output list contents
fore := l.Front(); e ! =nil; e = e.Next() {
    fmt.Println(e.Value)
}
Copy the code

The following output is displayed:

1
2
3
4
Copy the code

The stack

We know that the stack has three basic operations: Push(), Pop() and Top(), which Push, Pop, and view the Top of the stack respectively. We can use the list method to simulate the three basic operations: s.pushback (), s.pack ().value, and s.emove (s.pack ()).

stack := list.New()
stack.PushBack(1)
stack.PushBack(2)
stack.PushBack(3)
stack.PushBack(4)
for stack.Len() > 0 {
    fmt.Println(stack.Remove(stack.Back()))
}
Copy the code

The output is as follows:

4
3
2
1
Copy the code

The queue

Similarly, we can also use q.pushback () and q.remove (q.front ()) to simulate the queue progress and queue exit operation.

queue := list.New()
queue.PushBack(1)
queue.PushBack(2)
queue.PushBack(3)
queue.PushBack(4)
for l.Len() > 0 {
    fmt.Println(l.Remove(l.Front()))
}
Copy the code

The output is as follows:

4
3
2
1
Copy the code