快捷導(dǎo)航

Golang使用切片實現(xiàn)單鏈表的示例代碼

更新時間：2024年05月21日 09:44:45 作者：不會前端的小李

單鏈表（Single?Linked?List）是鏈表數(shù)據(jù)結(jié)構(gòu)的一種實現(xiàn)方式,它包含一系列節(jié)點（Node）,每個節(jié)點都包含一個數(shù)據(jù)域和一個指向下一個節(jié)點的指針,本文給大家介紹了Golang使用切片實現(xiàn)單鏈表的操作,需要的朋友可以參考下

單鏈表（Single Linked List）是鏈表數(shù)據(jù)結(jié)構(gòu)的一種實現(xiàn)方式，它包含一系列節(jié)點（Node），每個節(jié)點都包含一個數(shù)據(jù)域和一個指向下一個節(jié)點的指針。與數(shù)組相比，鏈表的一個主要優(yōu)點是它們可以動態(tài)地進(jìn)行擴展和收縮，因為它們的元素在內(nèi)存中不是連續(xù)存儲的。

通過定義結(jié)構(gòu)體實現(xiàn)單鏈表的操作，no為鏈表中節(jié)點的id，name為節(jié)點id對應(yīng)的內(nèi)容，next為下一個節(jié)點的信息

type HeroNode struct {
	no   int
	name string
	next *HeroNode 
}

InputNode方法，為鏈表添加節(jié)點。通過定義輔助節(jié)點，找到鏈表的最后一個節(jié)點，并將要添加的節(jié)點添加到找到的節(jié)點的下一個節(jié)點。

func InputNode(head *HeroNode, hero *HeroNode) {
	text := head
	for {
		if text.next == nil {
			break
		}
		text = text.next
	}
	text.next = hero
}

InputNode2方法，為鏈表順序添加節(jié)點。首先還是定義一個輔助節(jié)點，這次還另外定義一個flag為了判斷要插入的節(jié)點是否已經(jīng)存在。通過輔助節(jié)點進(jìn)行判斷插入的節(jié)點的id，并進(jìn)行插入對應(yīng)位置。這里要注意的是需要先將要插入的節(jié)點的下一個節(jié)點改為輔助節(jié)點的下一個節(jié)點，然后再將輔助節(jié)點的下一個節(jié)點換為要插入的節(jié)點。一旦先將text.next=hero，原本text后面的節(jié)點將會失去前置節(jié)點，那么hero節(jié)點將添加失敗

func InputNode2(head *HeroNode, hero *HeroNode) {
	text := head
	flag := true
	//讓插入的節(jié)點的no，和text的下一個節(jié)點的no進(jìn)行比較
	for {
		if text.next == nil {
			break
		} else if text.next.no > hero.no {
			//說明hero應(yīng)該插入到text后面
			break
		} else if text.next.no == hero.no {
			flag = false
			break
		}
		text = text.next
	}
	if !flag {
		fmt.Println("已經(jīng)存在", hero.no)
		return
	} else {
		hero.next = text.next
		text.next = hero
	}
}

DelectNode方法，刪除鏈表中的節(jié)點。通過定義輔助節(jié)點和flag進(jìn)行對要刪除節(jié)點的查詢，查詢后將text的下一個節(jié)點指向text下一個節(jié)點的下一個節(jié)點即可完成節(jié)點的刪除。

func DelectNode(hero *HeroNode, id int) {
	text := hero
	flag := false
	for {
		if text.next == nil {
			break
		} else if text.next.no == id {
			//說明找到了
			flag = true
			break
		}
		text = text.next
	}
	if flag {
		text.next = text.next.next
	} else {
		fmt.Println("刪除id不存在", id)
	}
}

ShowNode方法，實現(xiàn)顯示鏈表中的節(jié)點。先判斷鏈表是否為空鏈表然后進(jìn)行鏈表的打印輸出，直到鏈表為空。

func ShowNode(head *HeroNode) {
	//	創(chuàng)建一個輔助節(jié)點
	text := head
	//	判斷是否為空鏈表
	if text.next == nil {
		fmt.Println("空鏈表")
		return
	}
	for {
		fmt.Printf("[%d ,%s ]==>", text.next.no, text.next.name)
		text = text.next
		if text.next == nil {
			break
		}
	}
}

主函數(shù)。定義了一個根節(jié)點head，定義了5個要添加的節(jié)點，并將他們按照順序添加，之后打印顯示出整個鏈表，然后刪除掉節(jié)點id為"1"的數(shù)據(jù)，并再次打印顯示鏈表。

func main() {
	//	創(chuàng)建根節(jié)點
	head := &HeroNode{}
	hero1 := &HeroNode{
		no:   1,
		name: "張明",
	}
	hero2 := &HeroNode{
		no:   2,
		name: "李華",
	}
	hero3 := &HeroNode{
		no:   3,
		name: "王五",
	}
	hero4 := &HeroNode{
		no:   4,
		name: "張三",
	}
	hero5 := &HeroNode{
		no:   5,
		name: "花花",
	}
	InputNode2(head, hero1)
	InputNode2(head, hero2)
	InputNode2(head, hero3)
	InputNode2(head, hero4)
	InputNode2(head, hero5)
	ShowNode(head)
	fmt.Println()
	DelectNode(head, 1)
	ShowNode(head)
}

整體代碼的實現(xiàn)