Двусвязный список изучения исходного кода Go

задняя часть Go исходный код Element

Определение двусвязного списка

Двусвязный список также называетсядвусвязный список, представляет собой тип связанного списка, каждый из его узлов данных имеет двауказатель, которые указывают на непосредственного преемника и непосредственного предшественника соответственно. Поэтому, начиная с любого узла в двусвязном списке, легко получить доступ к его узлам-предшественникам и узлам-последователям. Как правило, мы строим двусторонниеКруговой связанный список.

Вот запись процесса обучения и понимания

диаграмма

Doubly linked list - wikipedia

Идтиисходный кодвыполнить

1. Сначала посмотрите на определение элемента (Element), хранящегося в связанном списке:

// 双向链表的一个元素 
type Element struct {
  // 前驱指针和后继指针
  prev, next *Element

  // 该元素属于哪个链表list
  list *List

  // 该元素存储的值
  Value interface{} 
}

2. Определите два метода для структуры Element:

// Next 返回元素e的后一个元素 
func (e *Element) Next() *Element {
  if p := e.next; e.list != nil && &e.list.root != p {
  	return p
  }
  return nil 
}

// Prev 返回元素e的前一个元素 
func (e *Element) Prev() *Element {
  if p := e.prev; e.list != nil && &e.list.root != p {
  	return p
  }
  return nil 
}

3. Посмотрите на определение списка связанных списков:

// List 代表一个双向链表 
// List的零值是一个空的列表 
type List struct {
  // 根节点
  root Element
  
  // 当前链表的长度
  len int 
}

4. Определите метод инициализации для связанного списка List

// Init 初始化一个链表，或者重置一个链表 
func (l *List) Init() (*List) {
  l.root.prev = &l.root
  l.root.next = &l.root
  l.len = 0
  return l 
}

5. Определите фабричный метод для связанного списка List, чтобы сгенерировать связанный список:

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

6. Давайте рассмотрим два основных метода связанного списка: вставка и удаление.Другие операции связанного списка в основном основаны на этих двух методах.

// insert 在元素at后面插入元素e，将list的长度递增，返回该元素 
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 从双向链表中移除一个元素e，递减链表的长度，返回该元素e 
func (l *List) remove(e *Element) *Element {
  e.prev.next = e.next
  e.next.prev = e.prev
  e.next = nil // 防止内存泄漏
  e.prev = nil // 防止内存泄漏
  e.list = nil
  l.len --
  return e 
}

doubly linked list insert operate

Операция вставки:

  • Сначала удалите указатель преемника элемента b и указатель предшественника элемента c.
  • Затем укажите указатель преемника элемента b на новый элемент new и укажите указатель предшественника нового элемента new на элемент b
  • Давайте поговорим о том, что указатель-предшественник элемента c указывает на новый элемент new, а указатель-преемник нового элемента new указывает на элемент c
  • Наконец, добавьте единицу к длине связанного списка.

double linked list remove operate

Удалить операцию:

  • Теперь указатель-преемник элемента b указывает на элемент d, а указатель-предшественник элемента d указывает на b.
  • Давайте поговорим об удалении указателя-предшественника и указателя-преемника элемента c.
  • Уменьшить длину связанного списка на единицу

7. Поняв операции вставки и удаления связанных списков, вы можете инкапсулировать функции работы с расширенными связанными списками на этой основе:

// insertValue 是对l.insert(&Element{Value:v}, at)的包装
func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// Remove 如果元素e是链表l的一个元素，则移除e
// 返回元素e的值e.Value
// 该元素e不能为nil
func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}

Вставьте элемент в начало или конец связанного списка:

// PushFront 插入一个包含值v的新元素e到链表l的头部，并返回该元素e
func (l *List) PushFront(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

// PushBack 插入一个包含值v的新元素e到链表l的尾部，并返回这个新元素e
func (l *List) PushBack(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

Вставьте новый элемент до или после элемента:

// InsertBefore 在元素mark之前插入一个值为v的新元素
// 如果mark不属于链表l，则不会更新链表l，mark也不能为nil
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	return l.insertValue(v, mark.prev)
}

// InsertAfter 在元素mark之后插入一个值为v的新元素
// 如果mark不属于链表l，则不会更新链表l，mark也不能为nil
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	return l.insertValue(v, mark)
}

Переместите элемент в начало или конец связанного списка:

// MoveToFront 将元素e移动到链表头部
// 如果元素e不是链表的元素，则不会更新链表
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	l.insert(l.remove(e), &l.root)
}

// MoveToBack 将元素e移动到链表尾部
// 如果元素e不是链表的元素，则不会更新链表
func (l *List) MoveToBack(e *Element) {
	if e.list != l || e == l.root.prev {
		return
	}
	l.insert(l.remove(e), l.root.prev)
}

Переместите элемент A до или после элемента B:

// MoveBefore 移动元素e到元素mark之前
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || mark.list != l || e == mark {
		return
	}
	l.insert(l.remove(e), mark.prev)
}

// MoveAfter 移动元素e到元素mark之后
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.insert(l.remove(e), mark)
}

Приведенные выше коды взяты из исходного кода golang, см. подробности.Go Doc

Суммировать

Двусвязный список несложно понять, если вы понимаете его структуру данных и принципы вставки и удаления, вы сможете быстро его освоить.

Ссылаться на:

Оригинальный адрес:поп Walker.GitHub.IO/article/from78…

Категории