GO开发：链表

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

链表

type Student struct {
       Name string
       Next* Student
}

每个节点包含下一个节点的地址，这样把所有的节点串起来了，通常把链表中的第一个节点叫做链表头

package main

import (
   "fmt"
)

type Student struct {
   Id int
   Name  string
   Age   int
   next  *Student
}

func trans(p *Student){
   for p != nil {
      fmt.Println(*p)
      p = p.next
   }
   fmt.Println()
}

func main() {
   var head Student
   head.Id = 0
   head.Name = "head"
   head.Age = 18

   var s1 Student
   s1.Id = 1
   s1.Name = "stu1"
   s1.Age = 20
   head.next=&s1

   var s2 Student
   s2.Id = 2
   s2.Name = "stu2"
   s2.Age = 20
   s1.next=&s2
   trans(&head)

   var s3 Student
   s3.Id = 3
   s3.Name = "stu3"
   s3.Age = 20
   s2.next=&s3
   trans(&head)
}

插入节点：尾部插入

package main

import (
   "fmt"
   "math/rand"
)

type Student struct {
   Id int
   Name  string
   Age   int
   next  *Student
}

func trans(p *Student){
   for p != nil {
      fmt.Println(*p)
      p = p.next
   }
   fmt.Println()
}

func insertTail(p *Student) {
   var tail = p
   for i := 0; i < 10; i++ {
      stu := Student{
         Id: rand.Intn(10),
         Name:  fmt.Sprintf("stu%d", i),
         Age:   rand.Intn(100),
      }
      tail.next = &stu
      tail = &stu
   }
}

func main() {
   var head Student
   head.Id = 0
   head.Name = "head"
   head.Age = 18
   insertTail(&head)
   trans(&head)
}

插入节点：头部插入

package main

import (
	"fmt"
	"math/rand"
)

type Student struct {
	Id int
	Name  string
	Age   int
	next  *Student
}

func trans(p *Student){
	for p != nil {
		fmt.Println(*p)
		p = p.next
	}
	fmt.Println()
}

func insertTail(p *Student) {
	var tail = p
	for i := 0; i < 10; i++ {
		stu := Student{
			Id: rand.Intn(10),
			Name:  fmt.Sprintf("stu%d", i),
			Age:   rand.Intn(100),
		}
		tail.next = &stu
		tail = &stu
	}
}

func insertHead(p **Student) {
	//var tail = p
	for i := 0; i < 10; i++ {
		stu := Student{
			Id:    rand.Intn(10),
			Name:  fmt.Sprintf("stu%d", i),
			Age:   rand.Intn(100),
		}
		stu.next = *p
		*p = &stu
	}
}

func main() {
	//var head *Student = &Student{}
	var head *Student = new(Student)
	head.Id = 0
	head.Name = "head"
	head.Age = 18
	insertTail(head)
	insertHead(&head)
	trans(head)
}

添加和删除

package main

import (
   "fmt"
)

type Student struct {
   Id int
   Name  string
   Age   int
   next  *Student
}

func trans(p *Student) {
   for p != nil {
      fmt.Println(*p)
      p = p.next
   }
   fmt.Println()
}

func delNode(p *Student) {
   var prev *Student = p
   for p != nil {
      if p.Id == 100 {
         prev.next = p.next
         break
      }
      prev = p
      p = p.next
   }
}

func addNode(p *Student, newNode *Student) {
   for p != nil {
      if p.Name == "head" {
         newNode.next = p.next
         p.next = newNode
         break
      }
      p = p.next
   }
}

func main() {
   var head *Student = new(Student)
   head.Id = 0
   head.Name = "head"
   head.Age = 18

   var s1 Student
   s1.Id = 1
   s1.Name = "stu1"
   s1.Age = 20
   head.next=&s1

   var s2 Student
   s2.Id = 2
   s2.Name = "stu2"
   s2.Age = 20
   s1.next=&s2

   var newNode *Student = new(Student)
   newNode.Name = "greg"
   newNode.Age = 18
   newNode.Id = 100

   addNode(head, newNode)
   trans(head)

   delNode(head)
   trans(head)
}

双链表定义

type Student struct {
       Name string
       Next* Student
       Prev* Student
}

如果有两个指针分别指向前一个节点和后一个节点，我们叫做双链表

二叉树

type Student struct {
  	   Id int
       Name string
       left* Student
       right* Student
}

如果每个节点有两个指针分别用来指向左子树和右子树，我们把这样的结构叫做二叉树

package main

import "fmt"

type Student struct {
	Id int
	Name  string
	Age   int
	left  *Student
	right *Student
}

func trans(root *Student) {
	if root == nil {
		return
	}
	
	//前序遍历
	fmt.Println(root)
	trans(root.left)
	trans(root.right)
	
	//中序遍历
	//trans(root.left)
	//fmt.Println(root)
	//trans(root.right)

	//后续遍历
	//trans(root.left)
	//trans(root.right)
	//fmt.Println(root)
}

func main() {
	var root *Student = new(Student)
	root.Id = 1
	root.Name = "s1"
	root.Age = 18

	var left1 *Student = new(Student)
	left1.Id = 2
	left1.Name = "s2"
	left1.Age = 18
	root.left = left1

	var right1 *Student = new(Student)
	right1.Id = 4
	right1.Name = "s4"
	right1.Age = 18
	root.right = right1

	var left2 *Student = new(Student)
	left2.Id = 3
	left2.Name = "s3"
	left2.Age = 18
	left1.left = left2

	trans(root)
}

用接口实现一个通用链表

package main

import "fmt"

type LinkNode struct {
   data interface{}
   next *LinkNode
}

type Link struct {
   head *LinkNode
   tail *LinkNode
}

func (p *Link) InsertHead(data interface{}) {
   node := &LinkNode{
      data: data,
      next: nil,
   }

   if p.tail == nil && p.head == nil {
      p.tail = node
      p.head = node
      return
   }

   node.next = p.head
   p.head = node
}

func (p *Link) InsertTail(data interface{}) {
   node := &LinkNode{
      data: data,
      next: nil,
   }

   if p.tail == nil && p.head == nil {
      p.tail = node
      p.head = node
      return
   }

   p.tail.next = node
   p.tail = node
}

func (p *Link) Trans() {
   q := p.head
   for q != nil {
      fmt.Println(q.data)
      q = q.next
   }
}

func main() {
   var link Link
   for i := 0; i < 10; i++ {
      //intLink.InsertHead(i)
      link.InsertTail(fmt.Sprintf("str %d", i))
   }
   link.Trans()
}