21
文章
7
分类
13
标签

链表-go语言实现

最近复习数据结构与算法，正好也顺带练习下go语言。

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
type node struct {
	value int
	next  *node
}

func (node *node) setValue(value int) {
	node.value = value
}

func (node *node) getValue(value int) int {
	return node.value
}

首先定义链表的结点并定义与其关联的getset方法用来操作结点的值。此处和java等面向对象的语言有些不同，go语言方法接收一个定义的结点类型的变量，并修改其值，由于go本身是值传递，此处接收者定义为指针。

相关操作方法定义

对于一个链表来说，自然对其少不了增删改查的操作故定义以下五个方法：

方法名 声明
创建新链表 newList()
增加链表值 add()
删除链表值 delete(index int)
修改链表值 update(index int,value int)
查找链表值 find(value int) int

  • 创建新链表

    1
    2
    3
    4
    5
    6
    func newList() node {
     return node{
      value: -1,
      next:  nil,
     }
    }

这个方法做的操作很简单，主要是初始化了链表的头节点并返回头节点的实例，表示该链表建立以便进行后续的增删改查等操作。

  • 给链表增加值
1
2
3
4
5
6
7
8
9
10
11
12
func (list *node) add(value int) {

	var temp *node = nil

	newNode := new(node)
	newNode.value = value
	newNode.next = nil

	temp = list.next
	list.next = newNode
	newNode.next = temp
}

当需要给链表中插入新值时，首先需要申请容纳新值的空间，如代码中第5行所示，其申请了一个node类型的空间并将新值放进去。接下来采用头插法node插入链表，操作完成。

  • 删除链表值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (list *node) delete(index int) error {
	var temp *node = nil

	temp = list;
	for i := 1; i <= index; i++ {
		if (i == index && temp.next != nil) {
			temp.next = temp.next.next;
			return nil

		} else {
			temp = temp.next
		}

	}
	return errors.New("删除失败")
}

个人感觉这种实现方式有点low，但是如果在结构体中设置下标，维护下标又需要成本，且按位置删除总要先找到位置，在列表无序的情况下这样做也还算清晰，但还是low。（其实也可以按值删除，第一个符合的删去）重点理解删除思想。
将待删节点的前一个节点的next指向待删节点的下一个节点，就算ok。

  • 更新链表指定位置的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (list *node) update(index int, value int) error {
	var temp *node = nil

	temp = list;
	for i := 1; i <= index; i++ {
		if (i == index && temp.next != nil) {
			temp.next.value = value;
			return nil

		} else {
			temp = temp.next
		}

	}
	return errors.New("更新失败")
}

此处和删除逻辑流程差不多，都是先找到需要操作的节点，不同的是一个删除，一个仅仅是更新value。

  • 查找链表值
1
2
3
4
5
6
7
8
9
10
11
12
13
func (list *node) find(value int) (index int) {

	list = list.next
	for i := 1; list != nil; i++ {
		if list.value == value {
			index = i
			return
		}
		list = list.next
	}
	index = -1
	return
}

此处主要是在匹配值，如果匹配则返回元素所在的位置找不到则返回-1，下标从1开始，头结点不存储值所以去除。这里也可以看出go语言返回值的特色，可以在函数签名中进行返回值变量的声明，这样就可以直接在代码中yin引用，最后return即可，个人觉得这个特性有利于代码的整洁度。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

type node struct {
	value int
	next  *node
}

func (node *node) setValue(value int) {
	node.value = value
}

func (node *node) getValue(value int) int {
	return node.value
}

func newList() node {
	return node{
		value: -1,
		next:  nil,
	}
}

func (list *node) add(value int) {

	var temp *node = nil

	newNode := new(node)
	newNode.value = value
	newNode.next = nil

	temp = list.next
	list.next = newNode
	newNode.next = temp
}

func (list *node) delete(index int) error {

	for i := 1; i <= index; i++ {
		if (i == index && list.next != nil) {
			list.next = list.next.next;
			return nil

		} else {
			list = list.next
		}

	}
	return errors.New("删除失败")
}

func (list *node) update(index int, value int) error {

	for i := 1; i <= index; i++ {
		if (i == index && list.next != nil) {
			list.next.value = value;
			return nil

		} else {
			list = list.next
		}

	}
	return errors.New("更新失败")
}

func (list *node) find(value int) (index int) {

	list = list.next
	for i := 1; list != nil; i++ {
		if list.value == value {
			index = i
			return
		}
		list = list.next
	}
	index = -1
	return
}

以上就是这次所定义的链表，以及对其所定义的一系列操作，下面运行看看我们的程序是否可以正常运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func main() {
	var list Node
	list = NewList()
	list.add(1)
	list.add(2)
	list.add(3)
	println(list.find(1), list.find(2), list.find(3))
	err := list.delete(1)
	if err != nil {
		println(err)
	}
	println(list.find(3))

	err = list.update(2, 9)
	if err != nil {
		println(err)
	}

	println(list.find(9))

}

运行结果：
image.png-9.2kB

可以看到结果正如我们所期待的那样，先给链表中插入三个值，1，2，3.由于是按照头插法插入的，所以输出顺序为逆序。紧接着删除掉第一个位置的元素3，然后3不存在结果输出-1。然后再更新第二个位置的元素为9，输出9确实在第二个位置。

最后

链表其本质上就是一组离散结构的顺序表，使用任何语言都可以实现，其类型包括单向链表，双向链表，单向循环链表，双向循环链表等。在日常编程中具有相当广的应用范围，本次我们仅仅是用其完成了一个具有简单增删改查功能的列表容器结构，算是简单的小回顾复习了下吧。