遍历元素
假设 head 指针指向链表的第一个节点，为了遍历整个链表，我们需要进行如下几步操作：
- 跟随每个指针
- 随着每次遍历，记录下每个节点的数据（或者 count 计数）
- 当最后一个指针为空
nil时，停止遍历
图解如下：
网络异常，图片无法展示
|
函数如下：
func (linkedList *LinkedList) Traverse() { if linkedList.isNull() { fmt.Println("The LinkedList is empty") } currNode := linkedList.headNode for currNode != nil { fmt.Printf("%v -> ", currNode.data) currNode = currNode.next } fmt.Println() }
删除元素
- 头部删除
图解
网络异常，图片无法展示
|
函数如下：
func (linkedList *LinkedList) DeleteFirst() interface{} { if linkedList.isNull() { fmt.Println("deleteFirst: List is empty") } data := linkedList.headNode.data linkedList.headNode = linkedList.headNode.next linkedList.size-- return data }
- 中间删除
图解：
网络异常，图片无法展示
|
函数如下：
func (linkedList *LinkedList) Delete(pos int) interface{} { if pos < 1 || pos > linkedList.size+1 { fmt.Println("delete: Index out of bounds") } var prev, current *Node prev = nil current = linkedList.headNode p := 0 if pos == 1 { linkedList.headNode = linkedList.headNode.next } else { for p != pos-1 { p = p + 1 prev = current current = current.next } if current != nil { prev.next = current.next } } linkedList.size-- return current.data }
- 尾部删除
图解：
网络异常，图片无法展示
|
函数如下：
func (linkedList *LinkedList) DeleteLast() interface{} { if linkedList.isNull() { fmt.Println("deleteLast: List is empty") } var prev *Node current := linkedList.headNode for current.next != nil { prev = current current = current.next } if prev != nil { prev.next = nil } else { linkedList.headNode = nil } linkedList.size-- return current.data }
总结
好了有了上述函数，我们可以汇总到一起来检验我们的函数是否正确，创建一个 main.go 文件：
package main import "fmt" type Node struct { data interface{} next *Node } type LinkedList struct { headNode *Node // 头节点 size int // 存储链表的长度 } func CreateLinkList() *LinkedList { // 创建一个空的头节点 node := new(Node) l := new(LinkedList) l.headNode = node return l } // 返回链表的长度 func (linkedList *LinkedList) Length() int { return linkedList.Count() } func (linkedList *LinkedList) Count() int { size := 0 currNode := linkedList.headNode for currNode != nil { size++ currNode = currNode.next } return size } func (linkedList *LinkedList) isNull() bool { return linkedList.size == 0 } func (linkedList *LinkedList) Traverse() { if linkedList.isNull() { fmt.Println("The LinkedList is empty") } currNode := linkedList.headNode for currNode != nil { fmt.Printf("%v -> ", currNode.data) currNode = currNode.next } fmt.Println() return } func (linkedList *LinkedList) InsertHead(v interface{}) { node := &Node{data: v} if linkedList.isNull() { linkedList.headNode = node linkedList.size++ return } else { node.next = linkedList.headNode linkedList.headNode = node } linkedList.size++ return } func (linkedList *LinkedList) Append(v interface{}) { node := &Node{data: v} if linkedList.isNull() { linkedList.headNode = node } else { currNode := linkedList.headNode for currNode.next != nil { currNode = currNode.next } currNode.next = node } linkedList.size++ } // Insert adds an item at position i func (linkedList *LinkedList) Insert(pos int, v interface{}) { // 先检查待插入的位置是否正确 if pos < 1 || pos > linkedList.size+1 { fmt.Println("Index out of bounds") } newNode := &Node{data: v} var prev, current *Node prev = nil current = linkedList.headNode for pos > 1 { prev = current current = current.next pos = pos - 1 } if prev != nil { prev.next = newNode newNode.next = current } else { newNode.next = current linkedList.headNode = newNode } linkedList.size++ } func (linkedList *LinkedList) DeleteFirst() interface{} { if linkedList.isNull() { fmt.Println("deleteFirst: List is empty") } data := linkedList.headNode.data linkedList.headNode = linkedList.headNode.next linkedList.size-- return data } func (linkedList *LinkedList) DeleteLast() interface{} { if linkedList.isNull() { fmt.Println("deleteLast: List is empty") } var prev *Node current := linkedList.headNode for current.next != nil { prev = current current = current.next } if prev != nil { prev.next = nil } else { linkedList.headNode = nil } linkedList.size-- return current.data } func (linkedList *LinkedList) Delete(pos int) interface{} { if pos < 1 || pos > linkedList.size+1 { fmt.Println("delete: Index out of bounds") } var prev, current *Node prev = nil current = linkedList.headNode p := 0 if pos == 1 { linkedList.headNode = linkedList.headNode.next } else { for p != pos-1 { p = p + 1 prev = current current = current.next } if current != nil { prev.next = current.next } } linkedList.size-- return current.data } func main() { linkedList := CreateLinkList() fmt.Println("初始化创建一个链表，是否为空：", linkedList.isNull()) nums := []int{1, 2, 3, 4, 5} for i := range nums { linkedList.Append(nums[i]) } fmt.Println("****************尾部插入[1,2,3,4,5]****************") linkedList.Traverse() fmt.Print("链表的长度为：") fmt.Println(linkedList.Length()) fmt.Println("****************往头部插入6****************") linkedList.InsertHead(6) linkedList.Traverse() fmt.Println("****************第二个位置插入2022****************") linkedList.Insert(2, 2022) linkedList.Traverse() fmt.Println("****************删除最后一个元素****************") last := linkedList.DeleteLast() fmt.Println("删除最后一个元素为：", last) fmt.Println("****************删除第一个元素****************") first := linkedList.DeleteFirst() fmt.Println("删除第一个元素为：", first) fmt.Println("****************删除位置1的元素****************") deleteData := linkedList.Delete(1) fmt.Println("删除位置1的元素为:", deleteData) fmt.Println("****************最后的链表为：") linkedList.Traverse() }
运行这个方法的结果为：
初始化创建一个链表，是否为空： true ****************尾部插入[1,2,3,4,5]**************** 1 -> 2 -> 3 -> 4 -> 5 -> 链表的长度为：5 ****************往头部插入6**************** 6 -> 1 -> 2 -> 3 -> 4 -> 5 -> ****************第二个位置插入2022**************** 6 -> 2022 -> 1 -> 2 -> 3 -> 4 -> 5 -> ****************删除最后一个元素**************** 删除最后一个元素为： 5 ****************删除第一个元素**************** 删除第一个元素为： 6 ****************删除位置1的元素**************** 删除位置1的元素为: 2022 ****************最后的链表为： 1 -> 2 -> 3 -> 4 ->
至此，我们把基本操作做完成了，为了避免文章过于繁琐，决定把查找的操作放到链表的相关算法问题中再作说明。下一篇文章见！
