Структуры данных Go: связанный список

Анализ и реализация структуры данных Linked List в Go

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

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

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

Выполнение

Связанный список предоставит следующие методы:

  • Append(t)добавляет элемент t в конец связанного списка
  • Insert(i, t)добавляет Предмет t в позицию i
  • RemoveAt(i)удаляет узел в позиции i
  • IndexOf()возвращает позицию элемента t
  • IsEmpty()возвращает истину, если список пуст
  • Size()возвращает размер связанного списка
  • String()возвращает строковое представление списка
  • Head()возвращает первый узел, поэтому мы можем перебирать его

Я создамItemLinkedListуниверсальный тип, безопасный для параллелизма, который может создавать связанные списки, содержащие любой тип, с помощьюgenny, чтобы создать реализацию связанного списка для конкретного типа, инкапсулирующую фактическую структуру данных для конкретного значения, содержащую данные.

// Package linkedlist creates a ItemLinkedList data structure for the Item type
package linkedlist

import ( “fmt” “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the linked list type Item generic.Type

// Node a single node that composes the list type Node struct { content Item next *Node }

// ItemLinkedList the linked list of Items type ItemLinkedList struct { head *Node size int lock sync.RWMutex }

// Append adds an Item to the end of the linked list func (ll *ItemLinkedList) Append(t Item) { ll.lock.Lock() node := Node{t, nil} if ll.head == nil { ll.head = &node } else { last := ll.head for { if last.next == nil { break } last = last.next } last.next = &node } ll.size++ ll.lock.Unlock() }

// Insert adds an Item at position i func (ll *ItemLinkedList) Insert(i int, t Item) error { ll.lock.Lock() defer ll.lock.Unlock() if i < 0 || i > ll.size { return fmt.Errorf(“Index out of bounds”) } addNode := Node{t, nil} if i == 0 { addNode.next = ll.head ll.head = &addNode return nil } node := ll.head j := 0 for j < i-2 { j++ node = node.next } addNode.next = node.next node.next = &addNode ll.size++ return nil }

// RemoveAt removes a node at position i func (ll ItemLinkedList) RemoveAt(i int) (Item, error) { ll.lock.Lock() defer ll.lock.Unlock() if i < 0 || i > ll.size { return nil, fmt.Errorf(“Index out of bounds”) } node := ll.head j := 0 for j < i-1 { j++ node = node.next } remove := node.next node.next = remove.next ll.size return &remove.content, nil }

// IndexOf returns the position of the Item t func (ll *ItemLinkedList) IndexOf(t Item) int { ll.lock.RLock() defer ll.lock.RUnlock() node := ll.head j := 0 for { if node.content == t { return j } if node.next == nil { return -1 } node = node.next j++ } }

// IsEmpty returns true if the list is empty func (ll *ItemLinkedList) IsEmpty() bool { ll.lock.RLock() defer ll.lock.RUnlock() if ll.head == nil { return true } return false }

// Size returns the linked list size func (ll *ItemLinkedList) Size() int { ll.lock.RLock() defer ll.lock.RUnlock() size := 1 last := ll.head for { if last == nil || last.next == nil { break } last = last.next size++ } return size }

// Insert adds an Item at position i func (ll *ItemLinkedList) String() { ll.lock.RLock() defer ll.lock.RUnlock() node := ll.head j := 0 for { if node == nil { break } j++ fmt.Print(node.content) fmt.Print(" ") node = node.next } fmt.Println() }

// Head returns a pointer to the first node of the list func (ll ItemLinkedList) Head() Node { ll.lock.RLock() defer ll.lock.RUnlock() return ll.head }

Тесты

Тесты описывают использование вышеупомянутой реализации.

package linkedlist

import ( “fmt” “testing” )

var ll ItemLinkedList

func TestAppend(t *testing.T) { if !ll.IsEmpty() { t.Errorf(“list should be empty”) }

<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"first"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">IsEmpty</span>() {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"list should not be empty"</span>)
}

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">1</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 1 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"second"</span>)
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"third"</span>)

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">3</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 3 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

func TestRemoveAt(t *testing.T) { _, err := ll.RemoveAt(1) if err != nil { t.Errorf(“unexpected error %s”, err) }

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">2</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 2 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

func TestInsert(t *testing.T) { //test inserting in the middle err := ll.Insert(2, “second2”) if err != nil { t.Errorf(“unexpected error %s”, err) } if size := ll.Size(); size != 3 { t.Errorf(“wrong count, expected 3 and got %d”, size) }

<span style="color:#75715e">//test inserting at head position

err = ll.Insert(0, “zero”) if err != nil { t.Errorf(“unexpected error %s”, err) } }

func TestIndexOf(t *testing.T) { if i := ll.IndexOf(“zero”); i != 0 { t.Errorf(“expected position 0 but got %d”, i) } if i := ll.IndexOf(“first”); i != 1 { t.Errorf(“expected position 1 but got %d”, i) } if i := ll.IndexOf(“second2”); i != 2 { t.Errorf(“expected position 2 but got %d”, i) } if i := ll.IndexOf(“third”); i != 3 { t.Errorf(“expected position 3 but got %d”, i) } }

func TestHead(t *testing.T) { ll.Append(“zero”) h := ll.Head() if “zero” != fmt.Sprint(h.content) { t.Errorf(“Expected zero but got %s”, fmt.Sprint(h.content)) } }

Создание конкретной структуры данных связанного списка

Вы можете использовать эту универсальную реализацию для создания связанных списков для конкретных типов, используя

//generate a `IntLinkedList` linked list of `int` values
genny -in linkedlist.go -out linkedlist-int.go gen "Item=int"

//generate a </span>StringLinkedList<span style="color:#e6db74"> linked list of </span>string<span style="color:#e6db74"> values genny -in linkedlist.go -out linkedlist-string.go gen “Item=string”


Больше руководств по go: