Definition of a bidirectional linked list

Two-way linked list, also known as double linked list, is a kind of linked list, it has two Pointers in each data node, respectively pointing to the direct successor and direct precursor. Therefore, starting from any node in the bidirectional linked list, it is easy to access its predecessors and successors. In general, we construct two-way circular lists.

Here is a record of the process of learning and understanding

The illustration

The GoThe source codeimplementation

1. First look at the definition of an Element stored in a linked list:

// An element of a bidirectional list
type Element struct {
  // Precursor and successor Pointers
  prev, next *Element

  // Which list does the element belong to
  list *List

  // The value stored by this element
  Value interface{}}Copy the code

2. Define two methods for the Element structure:

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

// Prev returns the element preceding e
func (e *Element) Prev(a) *Element {
  ifp := e.prev; e.list ! =nil&& &e.list.root ! = p {return p
  }
  return nil 
}
Copy the code

3. Look at the definition of list again:

// List represents a two-way linked List
// The null value of List is an empty List
type List struct {
  / / the root node
  root Element
  
  // The length of the current list
  len int 
}
Copy the code

4. Define an initialization method for the List

// Init initializes a list, or resets a list
func (l *List) Init(a) (*List) {
  l.root.prev = &l.root
  l.root.next = &l.root
  l.len = 0
  return l 
}
Copy the code

5. Define a factory method for List to generate a linked List:

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

6. Let’s look at the core of the list of two methods: insert and delete, the list of other operations are based on these two methods

// insert e after at, incrementing the length of the list, and return that element
func (l *List) insert(e, at *Element) *Element {
  n := at.next
  at.next = e
  e.prev = at
  e.next = n
  n.prev = e
  e.list = l
  l.len ++
  return e 
}

// remove removes an element e from the list, decrement the length of the 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 
}
Copy the code

Insert operation:

  • Delete the successor pointer to element b and the precursor pointer to element C
  • We then point the successor pointer to element B to the new element, and the precursor pointer to the new element to element B
  • Let’s say that the precursor pointer to c points to the new element, and the successor pointer to new points to c
  • Finally, add one to the list length

Delete operation:

  • We now point the successor pointer to element B to element d, and the precursor pointer to element D to element B
  • Let’s talk about the precursor pointer and the subsequent pointer deletion of element C
  • Subtract one from the list length

7. Understand the insertion and deletion of the list, we can encapsulate a rich list operation function on this basis:

// insertValue is a wrapper for l.insert(&element {Value:v}, at)
func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// Remove if e is an element of the list L, Remove e
// Return the value e. value of element e
// The element e cannot be nil
func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}
Copy the code

To insert an element at the top or bottom of a list:

// PushFront inserts a new element e containing the value v into the head of the list l and returns the element e
func (l *List) PushFront(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

// PushBack insert a new element e containing the value v to the end of the list l and return the new element e
func (l *List) PushBack(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}
Copy the code

Insert a new element before or after an element:

// InsertBefore inserts a new element with the value v before the element mark
// If mark does not belong to list L, list L will not be updated, and mark cannot be nil
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	ifmark.list ! = l {return nil
	}
	return l.insertValue(v, mark.prev)
}

// InsertAfter inserts a new element with the value v after mark
// If mark does not belong to list L, list L will not be updated, and mark cannot be nil
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	ifmark.list ! = l {return nil
	}
	return l.insertValue(v, mark)
}
Copy the code

To move an element to the top or bottom of a list:

// MoveToFront Moves e to the top of the list
// If e is not an element of the list, the list will not be updated
func (l *List) MoveToFront(e *Element) {
	ife.list ! = l || l.root.next == e {return
	}
	l.insert(l.remove(e), &l.root)
}

// MoveToBack Moves e to the end of the list
// If e is not an element of the list, the list will not be updated
func (l *List) MoveToBack(e *Element) {
	ife.list ! = l || e == l.root.prev {return
	}
	l.insert(l.remove(e), l.root.prev)
}
Copy the code

Move element A before or after element B:

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

// MoveAfter moves element e after element mark
func (l *List) MoveAfter(e, mark *Element) {
	ife.list ! = l || e == mark || mark.list ! = l {return
	}
	l.insert(l.remove(e), mark)
}
Copy the code

The above code is from the Golang source code, see Go Doc

conclusion

Two-way linked list is not difficult to understand, as long as you understand the data structure and insert, delete the principle, you can quickly grasp.

Reference:

  • Doubly linked list – wikipedia
  • container/list – Go Doc
  • Arrays, single and double linked lists and bidirectional linked lists C/C++/Java implementation

The original address: popwalker. Making. IO/article/c78…