Daftar tertaut adalah salah satu struktur data yang paling umum digunakan untuk tunjangan memori dinamis. Di sini, daftar satu set elemen jadi dibuat, yang berisi setidaknya dua lokasi memori: satu untuk elemen data dan satu lagi untuk pointer yang menghubungkan set elemen berikut. Tutorial ini menjelaskan bagaimana daftar tertaut yang berbeda dapat diimplementasikan menggunakan pointer dan jenis struktur di GO.

Struktur Data di Go

Memori akses acak (RAM) dapat dilihat sebagai tabel, matriks atau kisi lokasi yang dapat dialamatkan. Untuk menyimpan nilai dalam tabel, programmer GO harus menunjuknya Struktur sewa. Struktur sewa ini menerima nama praktis yang disebut nama variabel. Pahami bahwa nama yang diberikan kepada suatu variabel hanya untuk kenyamanan programmer; Setelah program dikompilasi, nama variabel digantikan oleh a referensi (atau alamat memori, seperti 0x78bac).

Dalam bentuk paling sederhana, nama variabel dapat merujuk pada sel tunggal, tetapi dalam situasi yang rumit, itu bisa menjadi lokasi memori yang berdekatan atau matriks dengan garis dan kolom yang disebut a lukisan. Tabel dapat diakses dengan program dengan itu petunjukseperti Array_name[2][4]yang bisa berarti elemen Di kolom kedua dan baris keempat.

Namun, dalam situasi lain yang rumit, hubungan struktural antara elemen data mungkin tidak disimpan secara berdekatan. Sebaliknya, mereka dapat disimpan secara acak, seperti dalam struktur pohon yang mewakili hubungan hierarkis, hubungan bercabang atau struktur multitiliner yang kompleks dengan banyak interkoneksi.

Akibatnya, untuk menyimpan hubungan struktural yang ada dalam data, pengembang GO harus mendefinisikan penyediaan strategi memori dan akses sesuai dengan kebutuhan spesifik mereka.

Tunjangan memori statis dan dinamis di Go

Fakta penting tentang alokasi memori adalah properti yang disebut dinamis Dan statis alam. Ukuran dan lokasi struktur data statis telah ditentukan sebelumnya, sedangkan dalam struktur data dinamis, ukuran dan lokasi tidak ditentukan atau diputuskan pada saat eksekusi.

Misalnya, ketika pengembang GO mendefinisikan tabel, mereka memberikan nilai statis dari ukurannya sehingga kompiler tahu persis ke lokasi mana yang mereka rujuk ketika mereka memberikan nilai indeks. Dalam struktur data yang dinamis, seperti daftar tertaut, lokasi data berikut diputuskan hanya Saat dibuat selama fase eksekusi. Ukuran struktur data dinamis dapat tumbuh atau menyusut pada saat eksekusi. Karena struktur data statis disimpan di lokasi memori yang berdekatan, mereka beroperasi dengan cara linier, di mana elemen data disimpan secara berurutan.

Dasar struktur data dinamis disebut a Daftar Tertaut (Meskipun perhatikan bahwa tunjangan memori dinamis tidak terbatas pada daftar yang ditautkan). Di sini, elemen data disimpan di lokasi acak dalam memori dengan tautan untuk mengakses masing -masing elemen. Akibatnya, daftar tertaut berisi setidaknya dua elemen: satu yang mewakili elemen data dan tautan lain ke struktur berikut.

Perbandingan tunjangan berurutan dan terhubung dalam GO

Tidak seperti struktur berurutan (misalnya, tabel), tunjangan tertaut memerlukan memori tambahan untuk menyimpan tidak hanya elemen data, tetapi juga elemen untuk menyimpan tautan ke elemen berikut. Ini bisa menjadi faktor dominan dalam situasi tertentu, tetapi efisiensi yang diperoleh berkat tunjangan terkait berlaku dari jauh pada kelemahannya. Misalnya, ukuran yang dialokasikan oleh memori ditetapkan dalam tabel; Oleh karena itu, sebagian besar dapat tetap tidak digunakan. Dalam tunjangan terkait, pertanyaan tentang tunjangan yang tidak digunakan tidak muncul karena sebuah simpul dibuat hanya jika perlu.

Sangat mudah untuk menghapus elemen dalam daftar yang ditautkan, tetapi dalam tunjangan berurutan, penghapusan umumnya melibatkan memindahkan sebagian besar elemen data ke lokasi yang berbeda. Selain itu, penyisipan data cepat dalam tunjangan terkait. Namun, mengacu pada bagian acak dari daftar ini jauh lebih cepat jika terjadi tunjangan berurutan.

Setiap metode penyimpanan memiliki kelebihan dan kekurangannya. Memilih struktur yang tepat adalah atas kebijaksanaan programmer GO.

Jenis Daftar Tertaut

Ada tiga cara dasar yang dapat mewakili Daftar Tertaut: linear,, bundar,, menggandakanDan menggandakan.

Di sebuah linear Atau Daftar yang ditautkan secara individualHanya ada satu elemen tautan yang menunjuk ke simpul berikut dalam daftar. Elemen berikutnya dari node tautan terakhir menunjuk nilJadi saat daftar disilangkan dari awal hingga akhir, daftar tersebut diwakili secepatnya nil terpenuhi.

ITU Daftar terkait melingkar sama dengan daftar linier, kecuali bahwa simpul terakhir menunjuk ke simpul pertama. Persilangan dapat terjadi sampai elemen berikut berisi alamat node pertama. Karena simpul terakhir menunjuk ke yang pertama, penyeberangan melingkar dimungkinkan.

Di sebuah Sebutkan ditautkan gandaDua alamat tertaut disediakan: satu yang berikatan dengan simpul sebelumnya dan lainnya yang menghubungkan ke simpul berikutnya. Tidak seperti daftar linier, ini jelas merupakan keuntungan karena penyeberangan dapat terjadi di kedua arah. Pencarian elemen data bisa cepat.

A Daftar terkait ganda melingkar sama dengan daftar yang ditautkan ganda, kecuali bahwa elemen berikut dari simpul terakhir berasal dari simpul pertama dan elemen sebelumnya terkait dengan simpul terakhir. Ini memungkinkan penyeberangan melingkar di kedua arah.

Perhatikan bahwa fleksibilitas meningkat saat kita beralih dari daftar individual ke daftar melingkar yang terhubung ganda dan melingkar. Mari kita terapkan masing -masing jenis daftar ini yang ditautkan dengan beberapa contoh di bawah ini. Untuk menjaga hal -hal sederhana, kita terutama akan membatasi diri kita pada pembuatan dan mencoret daftar saja.

Contoh daftar yang ditautkan secara individual di GO

Anda akan menemukan contoh cara membuat daftar yang ditautkan secara individual di Go:

package main

import (
	"fmt"
	"math/rand"
)

type Node struct {
	info interface{}
	next *Node
}

type List struct {
	head *Node
}

func (l *List) Insert(d interface{}) {
	list := &Node{info: d, next: nil}
	if l.head == nil {
		l.head = list
	} else {
		p := l.head
		for p.next != nil {
			p = p.next
		}
		p.next = list
	}
}

func Show(l *List) {
	p := l.head
	for p != nil {
		fmt.Printf("-> %v ", p.info)
		p = p.next
	}
}

func main() {
	sl := List{}
	for i := 0; i < 5; i++ {
		sl.Insert(rand.Intn(100))
	}
	Show(&sl)
}

Keluar yang diharapkan dari pelaksanaan kode Golang ini di lingkungan pengembangan terintegrasi Anda adalah:

-> 81 -> 87 -> 47 -> 59 -> 81

Contoh kode daftar tertaut melingkar di Go

Kami dapat dengan mudah mengonversi satu daftar tunggal yang terhubung ke surat edaran. Jadi, tanpa memodifikasi kode di atas, tambahkan dua fungsi ini: ConvertSinglyToCircular Dan ShowCircular. Memohon dua fungsi ini mainItu saja.

Berikut adalah dua fungsi:

func ShowCircular(l *List) {
	p := l.head
	for {
		if p.next == l.head {
			fmt.Printf("-> %v ", p.info)
			break
		}
		fmt.Printf("-> %v ", p.info)
		p = p.next
	}
}

func ConvertSinglyToCircular(l *List) {
	p := l.head
	for p.next != nil {
		p = p.next
	}
	p.next = l.head
}

Catatan: Meskipun diasumsikan bahwa daftar ini sudah melingkar (artinya, p.next Akhirnya, arahkan ke arah l.head), jika l.head Timur nil (Daftar Kosong), fungsi ini akan macet dengan kesalahan dereferensi dari penunjuk nol.

Sekarang memohon fungsi main sebagai berikut:

func main() {
	sl := List{}
	for i := 0; i < 5; i++ {
		sl.Insert(rand.Intn(100))
	}
	ConvertSinglyToCircular(&sl)
	fmt.Println()
	ShowCircular(&sl)
}

Contoh daftar ganda yang dihubungkan ganda di Go

Berikut adalah contoh kode yang menunjukkan cara membuat daftar ditautkan ganda di Golang:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type Node struct {
	info interface{}
	prev *Node
	next *Node
}

type List struct {
	head *Node
	tail *Node
}

func (l *List) Insert(d interface{}) {
	list := &Node{info: d, prev: nil, next: nil}
	if l.head == nil {
		l.head = list
		l.tail = list
	} else {
		p := l.head
		for p.next != nil {
			p = p.next
		}
		list.prev = p
		p.next = list
		l.tail = list
	}
}

func Show(l *List) {
	p := l.head
	for p != nil {
		fmt.Printf("-> %v ", p.info)
		p = p.next
	}
}

func ReverseShow(l *List) {
	r := l.tail
	for r != nil {
		fmt.Printf("-> %v ", r.info)
		r = r.prev
	}
}

func main() {
	sl := List{}
	seed := rand.NewSource(time.Now().UnixNano())
	rnd := rand.New(seed)
	for i := 0; i < 10; i++ {
		sl.Insert(rnd.Intn(100))
	}
	Show(&sl)
	fmt.Println("n----------------------------")
	ReverseShow(&sl)
}

Output yang diharapkan dari eksekusi contoh kode GO ini di editor kode Anda adalah:

-> 11 -> 17 -> 56 -> 71 -> 39 -> 44 -> 18 -> 78 -> 25 -> 19 
----------------------------
-> 19 -> 25 -> 78 -> 18 -> 44 -> 39 -> 71 -> 56 -> 17 -> 11

Contoh daftar ganda melingkar di Go

Seperti daftar terkait melingkar, daftar melingkar ganda dapat dengan mudah dikonversi dari daftar yang ditautkan ganda. Kami hanya akan menambahkan dua fungsi ke kode di atas. Sisa kode tetap sama, kecuali sedikit modifikasi di main Fungsi, seperti yang telah kita lihat dalam kasus contoh daftar kami yang terhubung ke surat edaran:

func ConvertDoublyToDoublyCircular(l *List) {
	l.head.prev = l.tail
	l.tail.next = l.head
}

func ShowDoublyCircular(l *List) {
	p := l.head
	for {
		if p.next == l.head {
			fmt.Printf("-> %v ", p.info)
			break
		}
		fmt.Printf("-> %v ", p.info)
		p = p.next
	}
}

func ReverseShowDoublyCircular(l *List) {
	r := l.tail
	for {
		if r.prev == l.tail {
			fmt.Printf("-> %v ", r.info)
			break
		}
		fmt.Printf("-> %v ", r.info)
		r = r.prev
	}
}

func main() {
	sl := List{}
	seed := rand.NewSource(time.Now().UnixNano())
	rnd := rand.New(seed)
	for i := 0; i < 10; i++ {
		sl.Insert(rnd.Intn(100))
	}
	ConvertDoublyToDoublyCircular(&sl)
	ShowDoublyCircular(&sl)
	fmt.Println("n----------------------------")
	ReverseShowDoublyCircular(&sl)

}

Refleksi akhir pada linen Programming Go Listes

Seperti yang dapat kita lihat, daftar yang ditautkan cukup mudah diimplementasikan di Go. Tunjangan terkait digunakan untuk memodelkan berbagai jenis data, baik nilai unik atau struktur data yang kompleks dengan banyak bidang. Akses sangat cepat dalam pencarian berurutan saat digunakan dengan pointer. Ada beberapa teknik optimasi yang terkait dengan daftar tertaut. Daftar yang terhubung ganda memiliki efisiensi yang lebih tinggi daripada tunjangan terkait tunggal, dan penyeberangan dapat cepat di kedua arah.

Catatan Penerbit: Gambar bintang artikel ini (gopher) dibuat oleh Renee Prancisberlisensi di bawah Penugasan Creative Commons 4.0 lisensi, dan juga aktif GOT GITHUB.