Golang 链表

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

单链表

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

存储格式如下：

说明：一般来说，为了比较好的对单链表进行增删改查的操作，我们都会给他设置一个头结点，头结点的作用主要是用来表示链表头，本身这个节点不存放数据。

代码实现

package main

import "fmt"

// 定义一个 HeroNode
type HeroNode struct {
  No       int
  Name     string
  NickName string
  Next     *HeroNode
}

// 在链表尾部加入数据
func AddTail(head *HeroNode, newHeroNode *HeroNode) {
  // 找到链表的最后一个节点
  tmp := head
  for {
    if tmp.Next == nil { // 表示找到最后一个节点
      break
    }
    tmp = tmp.Next // 让tmp不断的指向下一个节点
  }
  //将newHeroNode 加入到尾部
  tmp.Next = newHeroNode
}

// 根据编号大小插入节点
func Insert(head *HeroNode, newHeroNode *HeroNode) {
  tmp := head
  flag := true
  for {
    if tmp.Next == nil { // 说明到链表的最后
      break
    } else if tmp.Next.No > newHeroNode.No {
      // 说明 newHeroNode 应该插入到 head的后面
      break
    } else if tmp.Next.No == newHeroNode.No {
      // 已存在no，不允许加入
      flag = false
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("添加失败，已存在no=", newHeroNode.No)
    return
  }
  newHeroNode.Next = tmp.Next
  tmp.Next = newHeroNode
}

// 显示链表所有节点信息
func List(head *HeroNode) {
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    tmp = tmp.Next
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)

    if tmp.Next == nil { // 判断是否到链表的最后
      break
    }
  }
  fmt.Println()
}

// 删除节点
func Del(head *HeroNode, no int) {
  tmp := head
  flag := false

  for {
    if tmp.Next == nil {
      break
    } else if tmp.Next.No == no {
      // 说明找到了要删除的节点
      flag = true
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("要删除的no不存在，no=", no)
    return
  }
  tmp.Next = tmp.Next.Next
}

func main() {
  // 创建头节点
  head := &HeroNode{}

  // 创建新的节点
  hero1 := &HeroNode{
    No:       1,
    Name:     "宋江",
    NickName: "及时雨",
  }
  hero2 := &HeroNode{
    No:       2,
    Name:     "卢俊义",
    NickName: "玉麒麟",
  }
  hero3 := &HeroNode{
    No:       3,
    Name:     "林冲",
    NickName: "豹子头",
  }

  // 尾部添加节点
  AddTail(head, hero1)
  AddTail(head, hero3)

  // 显示节点信息
  List(head)

  // 中间插入节点
  Insert(head, hero2)

  // 显示节点信息
  List(head)

  // 删除节点
  Del(head, 1)

  // 显示节点信息
  List(head)

}

运行结果：

[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->
[1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->
[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

示意图：

代码实现：

package main

import "fmt"

// 定义一个 HeroNode
type HeroNode struct {
  No       int
  Name     string
  NickName string
  Pre      *HeroNode
  Next     *HeroNode
}

// 在链表尾部加入数据
func AddTail(head *HeroNode, newHeroNode *HeroNode) {
  // 找到链表的最后一个节点
  tmp := head
  for {
    if tmp.Next == nil { // 表示找到最后一个节点
      break
    }
    tmp = tmp.Next // 让tmp不断的指向下一个节点
  }
  //将newHeroNode 加入到尾部
  tmp.Next = newHeroNode
  newHeroNode.Pre = tmp
}

// 根据编号大小插入节点
func Insert(head *HeroNode, newHeroNode *HeroNode) {
  tmp := head
  flag := true
  for {
    if tmp.Next == nil { // 说明到链表的最后
      break
    } else if tmp.Next.No > newHeroNode.No {
      // 说明 newHeroNode 应该插入到 head的后面
      break
    } else if tmp.Next.No == newHeroNode.No {
      // 已存在no，不允许加入
      flag = false
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("添加失败，已存在no=", newHeroNode.No)
    return
  }
  newHeroNode.Next = tmp.Next
  newHeroNode.Pre = tmp
  if tmp.Next != nil { // 判断插入是是否是尾部插入
    tmp.Next.Pre = newHeroNode
  }
  tmp.Next = newHeroNode
}

// 显示链表所有节点信息
func List(head *HeroNode) {
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    tmp = tmp.Next
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)

    if tmp.Next == nil { // 判断是否到链表的最后
      break
    }
  }
  fmt.Println()
}

// 逆序显示链表所有节点信息
func ListReverse(head *HeroNode) {
  fmt.Println("逆序显示节点信息：")
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    if tmp.Next == nil {
      break
    }
    tmp = tmp.Next
  }
  for {
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)
    tmp = tmp.Pre
    if tmp.Pre == nil { // 判断是否到链表的 head 节点
      break
    }
  }
  fmt.Println()
}

// 删除节点
func Del(head *HeroNode, no int) {
  tmp := head
  flag := false

  for {
    if tmp.Next == nil {
      break
    } else if tmp.Next.No == no {
      // 说明找到了要删除的节点
      flag = true
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("要删除的no不存在，no=", no)
    return
  }
  tmp.Next = tmp.Next.Next
  if tmp.Next != nil { // 判断删除的是否是最后一个节点
    tmp.Next.Pre = tmp
  }
}

func main() {
  // 创建头节点
  head := &HeroNode{}

  // 创建新的节点
  hero1 := &HeroNode{
    No:       1,
    Name:     "宋江",
    NickName: "及时雨",
  }
  hero2 := &HeroNode{
    No:       2,
    Name:     "卢俊义",
    NickName: "玉麒麟",
  }
  hero3 := &HeroNode{
    No:       3,
    Name:     "林冲",
    NickName: "豹子头",
  }

  // 尾部添加节点
  AddTail(head, hero1)
  AddTail(head, hero3)

  // 显示节点信息
  List(head)
  // 逆序显示节点信息
  ListReverse(head)

  // 中间插入节点
  Insert(head, hero2)

  // 显示节点信息
  List(head)

  // 逆序显示节点信息
  ListReverse(head)

  // 删除节点
  Del(head, 2)

  // 显示节点信息
  List(head)

}

运行结果：

[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->
逆序显示节点信息：
[3, 林冲, 豹子头]-->[1, 宋江, 及时雨]-->
[1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->
逆序显示节点信息：
[3, 林冲, 豹子头]-->[2, 卢俊义, 玉麒麟]-->[1, 宋江, 及时雨]-->
[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->

环形链表

环形链表，也叫循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

示意图：

代码实现：

package main

import "fmt"

type Person struct {
  Id   int
  Name string
  Next *Person
}

// 插入
func Insert(head *Person, newPerson *Person) {
  // 判断是不是第一个人
  if head.Next == nil {
    head.Id = newPerson.Id
    head.Name = newPerson.Name
    head.Next = head
    fmt.Println("加入环形链表成功")
    return
  }

  // 定义一个临时变量，帮助找到环形列表的最后节点
  tmp := head
  for {
    if tmp.Next == head {
      break
    }
    tmp = tmp.Next
  }

  // 加入到链表中
  tmp.Next = newPerson
  newPerson.Next = head
}

// 输出环形链表
func List(head *Person) {
  fmt.Println("环形链表详情：")
  tmp := head
  if tmp.Next == nil {
    fmt.Println("环形链表为空")
    return
  }

  for {
    fmt.Printf("[person id=%d, name=%s] -->", tmp.Id, tmp.Name)
    if tmp.Next == head {
      break
    }
    tmp = tmp.Next
  }
  fmt.Println()
}

// 删除链表节点, 这里需要返回haed节点，因为删除的可能就是head节点，导致head节点变化
func Del(head *Person, id int) *Person {
  tmp := head
  helper := head

  // 判断是否是空链表
  if tmp.Next == nil {
    fmt.Println("要删除的链表为空")
    return head
  }

  // 如果只有一个节点
  if tmp.Next == head {
    if tmp.Id == id {
      tmp.Next = nil
    }
    return head
  }

  // 将helper 定位到链表的最后
  for {
    if helper.Next == head {
      break
    }
    helper = helper.Next
  }

  // 如果链表是两个及两个以上的节点
  flag := true
  for {
    if tmp.Next == head { // 如果到这里，说明比较到了最后一个，但是最后一个还没有比较
      break
    } else if tmp.Id == id {
      if tmp == head { // 说明删除的是head节点
        head = head.Next
      }
      helper.Next = tmp.Next
      fmt.Println("删除节点id=", id)
      flag = false
      break
    }

    tmp = tmp.Next
    helper = helper.Next
  }

  // 这里还需要比较一次
  if flag {
    if tmp.Id == id {
      helper.Next = tmp.Next
      fmt.Println("删除节点id=", id)
    } else {
      fmt.Println("未找到要删除的节点")
    }
  }
  return head
}

func main() {
  head := &Person{}
  p1 := &Person{
    Id:   1,
    Name: "tom",
  }
  p2 := &Person{
    Id:   2,
    Name: "gopher",
  }
  p3 := &Person{
    Id:   3,
    Name: "jackey",
  }

  Insert(head, p1)
  Insert(head, p2)
  Insert(head, p3)

  List(head)

  head = Del(head, 1)

  List(head)
}