Xazina qidirish o'yinini o'ynaganmisiz? Birinchi maslahat sizni ikkinchi maslahat turgan joyga yetaklaydi, ikkinchisi — uchinchisiga, va hokazo, toki xazinaning o'ziga yetguningizcha. Har bir maslahatda faqat bitta narsa yozilgan: "keyingisi qayerda".

Linked List (bog'langan ro'yxat) — aynan shunday ishlaydi. Slice'dan farqli o'laroq (u yerda hamma element xotirada ketma-ket, bitta katta blokda turadi), bog'langan ro'yxatdagi har bir element — Node ("tugun") — o'zining qiymatini VA keyingi tugunga bo'lgan pointerni saqlaydi. Tugunlar xotiraning istalgan joyida bo'lishi mumkin — ularni bog'lab turadigan yagona narsa, aynan shu "keyingisi qayerda" ko'rsatmasi.

package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

type LinkedList struct {
	Head *Node
}

func (l *LinkedList) Append(v int) {
	node := &Node{Value: v}
	if l.Head == nil {
		l.Head = node
		return
	}
	cur := l.Head
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = node
}

func main() {
	var list LinkedList
	list.Append(1)
	list.Append(2)
	list.Append(3)

	cur := list.Head
	for cur != nil {
		fmt.Println(cur.Value)
		cur = cur.Next
	}
}

LinkedList o'zi faqat bitta narsani biladi: Head — ro'yxatning eng boshidagi tugun. Qolgan hamma narsa shu yerdan boshlab, "keyingisi"ni kuzatib borish orqali topiladi. Append metodi ro'yxat oxiriga yangi tugun qo'shish uchun avval boshidan boshlab yuradi (cur := l.Head), cur.Next != nil ekan — ya'ni "hali keyingisi bor" ekan — davom etadi, va oxiriga yetganda yangi tugunni ulaydi.

Nega umuman slice o'rniga bunday tuzilma kerak? Chunki ro'yxat o'rtasiga yangi element qo'shish yoki o'chirish kerak bo'lganda, bog'langan ro'yxat juda tez ishlaydi — atigi ikkita pointerni o'zgartirish kifoya, butun ro'yxatni siljitish shart emas (slice'da esa o'rtaga qo'shish uchun undan keyingi HAMMA elementni bir joyga siljitish kerak bo'lardi).