# Golang 单链表基本操作
---

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)。

元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

:::success

package main

import "fmt"

//创建结点 结构体
type ListNode struct {
	Value interface{}
	Next  *ListNode
}

//链表 结构体
type LinkList struct {
	Head   *ListNode
	Length int
}

// 创建链表结点
func NewListNode(v interface{}) *ListNode {
	return &ListNode{v, nil}
}

// 获取链表Next域
func (list *ListNode) GetNext() *ListNode {
	return list.Next
}

// 获取链表的Value域
func (list *ListNode) GetValue() interface{} {
	return list.Value
}

// 创建空链表
func NewLinkedList() *LinkList {
        // return &LinkList{NewListNode(nil), 0} 
        // return &LinkList{nil, 0} 
	return &LinkList{NewListNode(0), 0}
}

// 判断链表是否为空
func (list *LinkList) isNulLinkList() bool {
	return list.Head.Next == nil
}

//返回链表长度
func (list *LinkList) GetLength() int {
	return list.Length
}

//打印链表
func (list *LinkList) PrintLinkList() {
	cur := list.Head.Next
	format := ""
	for cur != nil {
		format += fmt.Sprintf("%v", cur)
		cur = cur.Next
		if cur != nil {
			format += "->"
		}
	}

	fmt.Println("LinkList length:", list.GetLength(), "\n", format)
}

//在i处插入节点（前插）
func (list *LinkList) Insert(i int, v interface{}) {
	s := NewListNode(v)
	pre := list.Head
	for count := 1; count <= i; count++ {
		if count == i {
			s.Next = pre.Next
			pre.Next = s
			list.Length++
		}
		pre = pre.Next
	}
}

// 在指定节点后插入数据
func (list *LinkList) InsertAfterNode(p *ListNode, v interface{}) (bool, *ListNode) {
	if p == nil {
		return false, &ListNode{}
	}
	node := NewListNode(v)
	prev := p.Next
	p.Next = node
	node.Next = prev
	list.Length++
	return true, node
}

// 在指定节点前插入数据
func (list *LinkList) InsertBeforeNode(p *ListNode, v interface{}) bool {
	if p == nil || p == list.Head {
		return false
	}
	cur := list.Head.Next
	prev := list.Head
	for cur != nil {
		if cur == p {
			break
		}
		prev = cur
		cur = cur.Next
	}
	if cur == nil {
		return false
	}
	node := NewListNode(v)
	prev.Next = node
	node.Next = cur
	list.Length++
	return true
}

// 表头插入数据
func (list *LinkList) InsertToHead(v interface{}) (bool, *ListNode) {
	return list.InsertAfterNode(list.Head, v)
}

// 表尾插入数据
func (list *LinkList) InsertToTail(v interface{}) (bool, *ListNode) {
	cur := list.Head
	for cur.Next != nil {
		cur = cur.Next
	}
	return list.InsertAfterNode(cur, v)
}

// 删除指定结点
func (list *LinkList) DeleteNodeByNode(p *ListNode) bool {
	if nil == p {
		return false
	}
	cur := list.Head.Next
	pre := list.Head
	for cur != p {
		if cur == nil {
			return false
		}
		pre = cur
		cur = cur.Next
	}
	pre.Next = cur.Next
	list.Length--
	return true
}

// 删除指定位置的节点(从1开始算)
func (list *LinkList) DeleteNodeByIndex1(i int) {
	pre := list.Head
	for count := 1; count < list.Length; count++ {
		s := pre.Next
		if count == i {
			pre.Next = s.Next
			list.Length--
		}
		pre = pre.Next
	}
}

// 删除指定位置的节点
func (list *LinkList) DeleteNodeByIndex2(v int) bool {
	if v > list.Length {
		return false
	}
	cur := list.Head.Next
	pre := list.Head

	for i := 1; i < v; i++ {
		pre = cur
		cur = cur.Next
	}

	pre.Next = cur.Next
	list.Length--

	return true
}

//删除指定位置的节点(从1开始算)
func (list *LinkList) DeleteNodeByIndex3(index int) {
	if index > list.Length {
		return
	} else {
		pre := list.Head
		if index == 1 {
			list.Head = pre.Next
			return
		}
		for i := 1; i < index-1; i++ {
			pre = pre.Next
		}
		pre.Next = pre.Next.Next
		list.Length--
	}
}

//查值v所在位置
func (list *LinkList) Search(key int) int {
	pre := list.Head.Next
	for i := 1; i <= list.Length; i++ {
		if pre.Value == key {
			return i
		}
		pre = pre.Next
	}
	return -1
}

// 通过index查找结点,查找指定位置的结点
func (list *LinkList) FindNodeByIndex(index int) *ListNode {
	if index > list.Length {
		return nil
	}
	cur := list.Head.Next
	for i := 1; i < index; i++ {
		cur = cur.Next
	}
	return cur
}

// 通过index查找结点,查找指定位置的data
func (list *LinkList) FindDataByIndex(index int) interface{} {
	if index > list.Length {
		return nil
	}
	cur := list.Head.Next
	for i := 1; i < index; i++ {
		cur = cur.Next
	}
	return cur.Value
}

// 返回所有结点的内容
func (list *LinkList) AllLinkListData() (data []interface{}) {
	node := list.Head
	if node == nil {
		return nil
	}
	for {
		data = append(data, node.Value)
		if node.Next != nil {
			node = node.Next
		} else {
			break
		}
	}
	return data
}

// 查询链表中是否包含某数据
func (list *LinkList) Contains(data interface{}) bool {
	pre := list.Head.Next
	for i := 1; i <= list.Length; i++ {
		if pre.Value == data {
			return true
		}
		pre = pre.Next
	}
	return false
}

//根据索引更新数据(从1开始算)
func (list *LinkList) UpdateLinkListByIndex(index int, data interface{}) *ListNode {
	if index > list.Length {
		return nil
	}
	cur := list.Head.Next
	for i := 1; i < index; i++ {
		cur = cur.Next
	}
	cur.Value = data
	return cur
}

func main() {
	node := NewListNode(0)
	fmt.Println(node.GetValue())
	fmt.Println(node.GetNext())
	linkList := NewLinkedList()
	fmt.Println("List is Null:", linkList.isNulLinkList())
	fmt.Println("List length is:", linkList.Length)
	var M *LinkList
	M = linkList
	// 添加链表结点数据
	M.Insert(1, 9)
	M.Insert(2, 8)
	M.Insert(1, 7)
	M.Insert(2, 8)
	M.PrintLinkList()
	b1, node1 := M.InsertToHead(3)
	fmt.Println(b1, node1)
	M.PrintLinkList()
	b2, node2 := M.InsertToTail(4)
	fmt.Println(b2, node2)
	M.PrintLinkList()
	M.InsertAfterNode(node1, 1)
	M.PrintLinkList()
	M.InsertBeforeNode(node2, 2)
	M.PrintLinkList()
	b3, node3 := M.InsertToTail(5)
	fmt.Println(b3, node3)
	M.PrintLinkList()
	fmt.Println("List is Null:", linkList.isNulLinkList())
	fmt.Println("List length is:", linkList.GetLength())

	// 查找链表数据
	fmt.Println("元素7在位置  ", M.Search(8))
	fmt.Println("元素10在位置  ", M.Search(10))
	fmt.Println("all link list of data", M.AllLinkListData())
	fmt.Println("链表包含数据5", M.Contains(5))
	fmt.Println("链表位置1的数据为", M.FindDataByIndex(2))
	fmt.Println("链表位置1的结点为", M.FindNodeByIndex(2))

	// 删除链表结点
	fmt.Println("all link list of data", M.AllLinkListData())
	M.PrintLinkList()
	fmt.Println("删除node1", M.DeleteNodeByNode(node1))
	M.PrintLinkList()
	fmt.Println("删除node2", M.DeleteNodeByNode(node2))
	M.PrintLinkList()
	M.DeleteNodeByIndex1(3)
	M.PrintLinkList()
	M.DeleteNodeByIndex2(4)
	M.PrintLinkList()
	M.DeleteNodeByIndex3(5)
	M.PrintLinkList()
	M.DeleteNodeByIndex3(6)
	M.PrintLinkList()
    
        // 更新链表结点
    	M.UpdateLinkListByIndex(1, 2)
	M.PrintLinkList()
	M.UpdateLinkListByIndex(1, 3)
	M.PrintLinkList()
	M.UpdateLinkListByIndex(4, 7)
	M.PrintLinkList()
	M.UpdateLinkListByIndex(5, 7)
	M.PrintLinkList()
}

:::

- 结果输出

0
<nil>
List is Null: true
List length is: 0
LinkedList length: 4 
 &{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 <nil>}
true &{3 0xc000004500}
LinkedList length: 5 
 &{3 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 <nil>}
true &{4 <nil>}
LinkedList length: 6 
 &{3 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000046a0}->&{4 <nil>}
LinkedList length: 7 
 &{3 0xc0000047a0}->&{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000046a0}->&{4 <nil>}
LinkedList length: 8 
 &{3 0xc0000047a0}->&{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000046a0}->&{4 <nil>}
true &{5 <nil>}
LinkedList length: 9 
 &{3 0xc0000047a0}->&{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000046a0}->&{4 0xc0000049c0}->&{5 <nil>}
List is Null: false
List length is: 9
元素7在位置   4
元素10在位置   -1
all link list of data [0 3 1 7 8 9 8 2 4 5]
链表包含数据5 true
链表位置1的数据为 1
链表位置1的结点为 &{1 0xc000004500}
all link list of data [0 3 1 7 8 9 8 2 4 5]
LinkedList length: 9 
 &{3 0xc0000047a0}->&{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000046a0}->&{4 0xc0000049c0}->&{5 <nil>}
删除node1 true
LinkedList length: 8 
 &{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000046a0}->&{4 0xc0000049c0}->&{5 <nil>}
删除node2 true
LinkedList length: 7 
 &{1 0xc000004500}->&{7 0xc000004520}->&{8 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000049c0}->&{5 <nil>}
LinkedList length: 6 
 &{1 0xc000004500}->&{7 0xc0000044c0}->&{9 0xc0000044e0}->&{8 0xc0000048a0}->&{2 0xc0000049c0}->&{5 <nil>}
LinkedList length: 5 
 &{1 0xc000004500}->&{7 0xc0000044c0}->&{9 0xc0000048a0}->&{2 0xc0000049c0}->&{5 <nil>}
LinkedList length: 4 
 &{1 0xc000004500}->&{7 0xc0000044c0}->&{9 0xc0000049c0}->&{5 <nil>}
LinkedList length: 4 
 &{1 0xc000004500}->&{7 0xc0000044c0}->&{9 0xc0000049c0}->&{5 <nil>}
 LinkList length: 4 
 &{2 0xc00005a4c0}->&{7 0xc00005a480}->&{9 0xc00005a980}->&{5 <nil>}
LinkList length: 4 
 &{3 0xc00005a4c0}->&{7 0xc00005a480}->&{9 0xc00005a980}->&{5 <nil>}
LinkList length: 4 
 &{3 0xc00005a4c0}->&{7 0xc00005a480}->&{9 0xc00005a980}->&{7 <nil>}
LinkList length: 4 
 &{3 0xc00005a4c0}->&{7 0xc00005a480}->&{9 0xc00005a980}->&{7 <nil>}

###### tags: `Golang`