【Go】单链表

node.go

// 链表节点

type Node struct {

	data interface{}

	next *Node

}

// 构造一个节点

func NewNode(data interface{}) *Node {

	return &Node{data: data, next: nil}

}

list.go

package single_linked_list

import (

	"fmt"

)

type SingleLinked interface {

	Add(node *Node)                            // 在链表前面插入节点

	Append(node *Node)                         // 在链表后面插入节点

	Delete(node *Node)                         // 删除节点

	DeleteByIndex(index int)                   // 根据索引删除节点

	InsertBefore(data interface{}, node *Node) // 在xx之前插入节点

	InsertAfter(data interface{}, node *Node)  // 在xx之后插入节点

	Get(index int) interface{}

	Length() int

	String() string

	Reverse() // 反转链表

}

type List struct {

	head   *Node // 链表头结点

	length int   // 链表长度

}

func NewList() *List {

	head := NewNode(nil)

	return &List{head: head, length: 0}

}

// 在链表前面插入节点

func (list *List) Add(node *Node) {

	if list.head == nil {

		list.head.next = node

		node.next = nil

		list.length++

	} else {

		temp := list.head     // 保存头结点

		node.next = temp.next // 新节点指向的节点就是原先头结点指向的节点

		temp.next = node      // 头结点指向新节点

		list.length++

	}

}

// 在链表后面插入节点

func (list *List) Append(node *Node) {

	if list.head == nil {

		list.head.next = node

		node.next = nil

		list.length++

	} else {

		temp := list.head

		for temp.next != nil { // 一直循环到链表最后一个节点

			temp = temp.next

		}

		temp.next = node

		list.length++

	}

}

// 在xx之前插入节点

func (list *List) InsertBefore(data interface{}, node *Node) {

	temp := list.head

	isFind := false

	for temp.next != nil {

		if temp.next.data == data { // 根据data找到其节点，在该节点之前插入新节点

			isFind = true

			break

		}

		temp = temp.next

	}

	if isFind {

		node.next = temp.next

		temp.next = node

		list.length++

	}

}

// 在xx之后插入节点

func (list *List) InsertAfter(data interface{}, node *Node) {

	temp := list.head

	isFind := false

	for temp.next != nil {

		if temp.data == data {

			isFind = true

			break

		}

		temp = temp.next

	}

	if isFind {

		node.next = temp.next

		temp.next = node

		list.length++

	}

}

// 删除节点

func (list *List) Delete(node *Node) {

	if node == nil {

		return

	}

	temp := list.head

	// 如果下一个节点不等于要删除的节点，则循环找下去

	for temp.next != nil && temp.next != node {

		temp = temp.next

	}

	if temp.next == node {

		// temp指向 要删除节点指向 的节点

		temp.next = temp.next.next

		list.length--

	}

}

// 根据索引删除节点

func (list *List) DeleteByIndex(index int) {

	if index > list.length-1 || index < 0 {

		return

	}

	temp := list.head

	for index > 0 {

		temp = temp.next

		index--

	}

	temp.next = temp.next.next

	list.length--

}

func (list *List) Get(index int) interface{} {

	if index > list.length-1 || index < 0 {

		return nil

	}

	temp := list.head

	for index > -1 {

		temp = temp.next

		index--

	}

	return temp.data

}

func (list *List) Length() int {

	return list.length

}

// 打印链表

func (list *List) String() string {

	var str string

	node := list.head

	for node.next != nil {

		str += fmt.Sprintf("%v-->", node.next.data)

		node = node.next

	}

	str = fmt.Sprintf("head-->%snil", str)

	return str

}

// 反转链表

func (list *List) Reverse() {

	// 链表为空或只有1个节点

	if list.head == nil || list.head.next == nil {

		return

	} else {

		/*

								 ------	       ------		  ------

			   head.next -> 0x01|	   |  0x02|      |   0x03| 	    |

								|  aa  |   '  |  bb  |	  '	 |  cc  |

								|	   |  '   |      |	 '	 |      |

								| 0x02 | '    | 0x03 |  '	 |  nil |

								 ------		   ------		  ------

								 ------	       ------		 ------

								|	   |0x01  |      |0x02  | 	   |0x03 <- head.next

								|  aa  |  '	  |  bb  |	' 	|  cc  |

								|	   |   '  |      |	 '	|      |

								|  nil |    ' | 0x01 |	  '	| 0x02 |

								 ------		   ------		 ------

		*/

		// prev ----> curr ----> currNext

		var prev *Node                  // 前一个节点（初始时即为 空节点）

		var curr *Node = list.head.next // 当前节点（初始时即为 第1个节点）

		for curr != nil {

			currNext := curr.next // 暂存当前节点的下一个节点（初始时即为 第2个节点）

			curr.next = prev      // 当前节点指向前一个节点（初始时即让 第1个节点指向空节点；... 那么 1 <- 2  2 <- 3）

			// 持续推进（循环到最后）

			prev = curr			  // 前一个节点变成了当前节点（初始时理解为 第1个节点跑到空节点位置）

			curr = currNext       // 当前节点变成了下一个节点（初始时理解为 第2个节点跑到第1个节点位置）

		}

		list.head.next = prev

	}

}

main.go

// 单链表

func main() {

	var list single_linked_list.SingleLinked = single_linked_list.NewList()

	n1 := single_linked_list.NewNode(1)

	n2 := single_linked_list.NewNode(2)

	n3 := single_linked_list.NewNode(3)

	n4 := single_linked_list.NewNode(4)

	n5 := single_linked_list.NewNode(5)

	list.Add(n1)

	list.Add(n2)

	list.Add(n3)

	list.Append(n4)

	list.Append(n5)

	fmt.Println(list) // head-->3-->2-->1-->4-->5-->nil

	list.Delete(n1)

	fmt.Println(list) // head-->3-->2-->4-->5-->nil

	list.DeleteByIndex(2)

	fmt.Println(list) // head-->3-->2-->5-->nil

	list.InsertBefore(2, n1)

	fmt.Println(list) // head-->3-->1-->2-->5-->nil

	list.InsertAfter(2, n4)

	fmt.Println(list)          // head-->3-->1-->2-->4-->5-->nil

	fmt.Println(list.Length()) // 5

	fmt.Println(list.Get(0))   // 3

	fmt.Println(list.Get(10))  // nil

	list.Reverse()

	fmt.Println(list) // head-->5-->4-->2-->1-->3-->nil

}

巴特西

【Go】单链表

最新文章

热门文章