链表

链表由一个个数据节点组成，是一个递归结构，要么为空，要么存在就是只想另一个数据节点的引用

package main
import(
	"fmt"
)

type LinkNode struct { 
  Data int64 
  NextNode *LinkNode 
}


func main() { 
  // 新的节点 
  node := new(LinkNode) 
  node.Data = 2 
  // 新的节点 
  node1 := new(LinkNode) 
  node1.Data = 3 
  node.NextNode = node1 
  // node1 链接到 node 节点上
  // 新的节点 
  node2 := new(LinkNode) 
  node2.Data = 4 
  node1.NextNode = node2 // node2 链接到 node1 节点上 
  // 按顺序打印数据
  nowNode := node 
  for {
    if nowNode != nil { 
      // 打印节点值 
      fmt.Println(nowNode.Data) 
      // 获取下一个节点 
      nowNode = nowNode.NextNode }
    // 如果下一个节点为空，表示链表结束了 
    break 
  } 
}

结构体 LinkNode 有两个字段，一个字段存放数据Data ，另一个字典指向下一个节点 NextNode。这种从一个数据节点指向下一个数据节点的结构，都可以叫做链表。

分类

1. 单链表，就是链表是单向的，像我们上面这个结构一样，可以一直往下找到下一个数据节点，它只有一个方向，它不能往回找。

2. 双链表，每个节点既可以找到它之前的节点，也可以找到之后的节点，是双向的。

3. 循环链表，就是它一直往下找数据节点，最后回到了自己那个节点，形成了一个回路。循环单链表和循环双链表的区别就是，一个只能一个方向走，一个两个方向都可以走。

循环链表

1.初始化循环链表

package main 
import ( "fmt" )
// 初始化空的循环链表，前驱和后驱都指向自己，因为是循环的 
func (r *Ring) init() *Ring { 
  r.next = r
  r.prev = r 
  return r 
}
func main() { 
  r := new(Ring) 
  r.init() 
}

创建一个指定大小 N 的循环链表，值全为空:

// 创建N个节点的循环链表 
func New(n int) *Ring { 
  if n <= 0 { 
    return nil 
  }
  r := new(Ring) 
  p := r 
  for i := 1; i < n; i++ { 
    p.next = &Ring{
      prev: p
    } 
    p = p.next 
  }
  p.next = r 
  r.prev = p

2.获取上一个或下一个节点

// 获取下一个节点 
func (r *Ring) Next() *Ring { 
  if r.next == nil { 
    return r.init() 
  }
  return r.next 
}
// 获取上一个节点 
func (r *Ring) Prev() *Ring { 
  if r.next == nil { 
    return r.init() 
  }return 
  r.prev 
}

3.获取第n个节点

因为链表是循环的，当 n 为负数，表示从前面往前遍历，否则往后面遍历：

func (r *Ring) Move(n int) *Ring { 
  if r.next == nil { 
    return r.init() 
  }
  switch { 
    case n < 0: 
    	for ; n < 0; n++ {
        r = r.prev 
      } 
  	case n > 0: 
    for ; n > 0; n-- { 
      r = r.next 
    } 
  }
  return r
}

4.添加节点

// 往节点A，链接一个节点，并且返回之前节点A的后驱节点 
func (r *Ring) Link(s *Ring) *Ring { 
  n := r.Next() 
  if s != nil { 
    p := s.Prev() 
    r.next = s 
    s.prev = r 
    n.prev = p 
    p.next = n 
  }
  return n 
}

添加节点的操作比较复杂，如果节点 s 是一个新的节点。那么也就是在 r 节点后插入一个新节点 s ，而 r 节点之前的后驱节点，将会链接到新节点后面，并返回 r 节点之前的第一个后驱节点 n 。

package main 
import ("fmt")
ffunc linkNewTest() { 
  // 第一个节点 
  r := &Ring{Value: -1} 
  // 链接新的五个节点 
  r.Link(&Ring{Value: 1}) 
  r.Link(&Ring{Value: 2}) 
  r.Link(&Ring{Value: 3}) 
  r.Link(&Ring{Value: 4}) 
  node := r 
  for {
    // 打印节点值 
    fmt.Println(node.Value) 
    // 移到下一个节点 
    node = node.Next() 
    // 如果节点回到了起点，结束 
    if node == r { 
      return 
    } 
  } 
}
func main() { 
  linkNewTest() 
}

5.删除节点

// 删除节点后面的 n 个节点 
func (r *Ring) Unlink(n int) *Ring { 
  if n < 0 { 
    return nil 
  }
  return r.Link(r.Move(n + 1)) 
}

将循环链表的后面几个节点删除。

package main 
import ("fmt")
func deleteTest() { 
  // 第一个节点 
  r := &Ring{Value: -1} 
  // 链接新的五个节点 
  r.Link(&Ring{Value: 1}) 
  r.Link(&Ring{Value: 2}) 
  r.Link(&Ring{Value: 3}) 
  r.Link(&Ring{Value: 4}) 
  temp := r.Unlink(3) // 解除了后面两个节点 
  // 打印原来的节点 
  node := r for {
    // 打印节点值 
    fmt.Println(node.Value) 
    // 移到下一个节点 
    node = node.Next() 
    // 如果节点回到了起点，结束 
    if node == r { 
      break 
    } 
  }
  fmt.Println("------")
  // 打印被切断的节点 
  node = temp for {
    // 打印节点值 
    fmt.Println(node.Value) 
    // 移到下一个节点 node = node.Next()
    // 如果节点回到了起点，结束 
    if node == temp { 
      break 
    } 
  } 
}

6.获取链表长度

// 查看循环链表长度 
func (r *Ring) Len() int { 
  n := 0 
  if r != nil {
    n = 1 
    for p := r.Next(); p != r; p = p.next { 
      n++ 
    } 
  }
  return n 
}

题目

1. 新建一个链表ChainList，输入一组数据，并输入m，实现从第m个数及往后数据的倒序(不允许使用数组，不允许新建链表，在原有链表上实现逆置)

//示例
输入数的个数：9
数据为：1 2 3 4 5 6 7 8 9
m值为：5
倒叙后输出：1 2 3 4 9 8 7 6 5

1. 链表排序

   

2. 使用单链表实现集合的交、并、差运算

   //示例
   Set1 = 1 7 4 9 0 6
   Set1 = 1 3 8 5 6 4
   Set1∩Set2 = 1 4 6
   Set1∪Set2 = 1 7 4 9 0 6 3 8 5 
   Set1-Set2 = 7 9 0
   Set2-Set1 = 3 8 5